C++Talk.NET

Frank Astier · Guest

Still working on this problem where I need to sort a small array (<16
elements), billions of times, so I want to use templates to completely
inline the code...

More about the problem: the data structure to sort is a
vector Contract1 price < Contract2 price, where price is a random double.

I tried to tweak the code contributed by David Abrahams, but I'm
running into compilation issues... I thought it would be efficient to
xorswap the pointers inline instead of relying on std::swap, but I get:

Compiling with Intel(R) C++ 8.1 ...(Intel C++ Environment)
std::vector::iterator,
Pred=CheapestFirst]" at line 56
instantiation of "void quicksort_impl<N, while_>::go(T,
const Pred &) [with N=8U, while_=true, T=std::vector<Contract *,
std::allocator::iterator, Pred=CheapestFirst]" at line 72
instantiation of "void quicksort(T, const Pred &) [with
T=std::vector<Contract *, std::allocator::iterator,
Pred=CheapestFirst]"

..MyQuicksort.cpp(14): error: no operator "^=" matches these operands
operand types are: std::vector<Contract *,
std::allocator::iterator ^= std::vector<Contract *,
std::allocator::iterator
inline void xorswap(T x1, T x2) { x1 ^= x2; x2 ^= x1; x1 ^= x2; }
^
detected during:
instantiation of "void xorswap(T, T) [with
T=std::vector<Contract *, std::allocator::iterator]" at
line 26
instantiation of "void QSpartition<N, last, i,
while_>::go(T, T, const Pred &) [with N=8U, last=0U, i=1U, while_=true,
T=std::vector<Contract *, std::allocator::iterator,
Pred=CheapestFirst]" at line 56
instantiation of "void quicksort_impl<N, while_>::go(T,
const Pred &) [with N=8U, while_=true, T=std::vector<Contract *,
std::allocator::iterator, Pred=CheapestFirst]" at line 72
instantiation of "void quicksort(T, const Pred &) [with
T=std::vector<Contract *, std::allocator::iterator,
Pred=CheapestFirst]"

How can I tell him that the vector<Contract*>::iterator *IS* a
Contract* that he can merrily xor??

My tweaked code below:

template <typename T>
inline void xorswap(T x1, T x2) { x1 ^= x2; x2 ^= x1; x1 ^= x2; }

template <size_t N, bool while_ = (N > 1)> struct quicksort_impl;

template <size_t N, size_t last = 0, size_t i = 1, bool while_ = (i <
N)>
struct QSpartition
{
template <typename T, typename Pred>
inline static void go(T a, T pivot, const Pred& p) {

if (p(a+i, pivot)) {

xorswap(a+last+1, a+i);
QSpartition<N, last+1, i+1, (i+1 < N)>::go(a, pivot, p);

} else

QSpartition<N, last, i+1, (i + 1 < N)>::go(a, pivot, p);
}
};

template <size_t N, size_t last, size_t i>
struct QSpartition<N, last, i, false>
{
template <typename T, typename Pred>
inline static void go(T a, T, const Pred& p)
{
xorswap(a, a+last);
size_t const pivotpos = last;
// Done partitioning; now recursively quicksort
quicksort_impl<pivotpos>::go(a, p);
size_t const start2 = pivotpos + 1;
quicksort_impl<N - start2>::go(a + start2, p);
}
};

template <size_t N, bool while_>
struct quicksort_impl
{
template <typename T, typename Pred>
inline static void go(T a, const Pred& p)
{
QSpartition<N>::go(a, a, p);
}
};

// Terminating case for the outer sort
template <size_t N>
struct quicksort_impl<N, false>
{
template <typename T, typename Pred>
inline static void go(T, const Pred&) {}
};

// A convenient wrapper for quicksort_impl
template <typename T, typename Pred>
inline void quicksort(T begin, const Pred& p)
{
quicksort_impl<8>::go(begin, p);
}

struct Contract {
double price;
Contract() : price(rand()) {}
};

struct Portfolio : vector<Contract*> {
Portfolio(size_t n) : vector<Contract*>(n) {
fill(begin(), end(), new Contract);
}
~Portfolio() { for (iterator i = begin(); i != end(); ++i) delete *i;
}
};

struct CheapestFirst {
bool inline operator()(Contract* c1, Contract* c2) {
return c1->price < c2->price;
}
};

int main(int argc, char** argv)
{
for (size_t i = 0; i < 100; ++i) {
Portfolio p( Cool

;
quicksort(p.begin(), CheapestFirst());
}

char c; cin >> c;

return 0;
}

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Andrew Koenig · Guest

"Frank Astier" <fastier (AT) yahoo (DOT) com> wrote

Andrei Alexandrescu (See · Guest

"Frank Astier" <fastier (AT) yahoo (DOT) com> wrote

David Abrahams · Guest

Frank Astier wrote:

kanze@gabi-soft.fr · Guest

David Abrahams wrote:

Frank Astier · Guest

David -

I'll switch over to insertion sort. What I am trying to do though, is
pass in a predicate that would take 2 pointers to objects and somehow
provide the strict weak ordering. I am also trying to tweak your code
to take in a range as 2 iterators for beginning and end of the range,
instead of specifying the container.

But specifying a predicate instance as we do in the STL sort would be a
runtime thing, therefore not "inline-able". Specifying a range is also
a runtime notion, rather than a compile time notion.

Is there any way the predicate itself can be inlined in the sorting
code? After all, the compiler just has to look up the definition of the
predicate and inline it?

Frank

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

David Abrahams · Guest

Frank Astier wrote: