why std::sort take no template parameter to swap?

[panzhiyong]

Hi there! I wonder why there is no such a overload version of sort
function in STL:

template<class RandomAccessIterator, class Pr, class IterSwap>
void sort(
RandomAccessIterator _First,
RandomAccessIterator _Last,
BinaryPredicate _Comp,
IterSwap _Swap
);

It seems that std::sort works only with "simple" element, which has
default constructor and value semantics. So the problem rises when I
want to sort a collection of point coordinates, like:

// sort 2D points, note that I use double(*)[2] to hold points'
coordinates.
void SortPoint(double coords[][2], int n)
{
sort(coords, coords + n, PointLess()); // compile error in
std::swap, require l-value.
}

What I want is somthing like:

void SortPoint(double coords[][2], int n)
{
sort(coords, coords + n, PointLess(), PointSwap());
}

Wish somebody to share his(her) thought about this!

// compare points
class PointLess
{
public:
bool operator() (double* a, double* b)
{
if(abs(a[0] - b[0]) > tolerance)
return a[0] < b[0];

return a[1] < b[1];
}
};

// swap points
class PointSwap
{
public:
void operator() (double* a, double* b)
{
swap(a[0], b[0]);
swap(a[1], b[1]);
}
};

 

[Kai-Uwe Bux]

Hi there! I wonder why there is no such a overload version of sort
function in STL:

template<class RandomAccessIterator, class Pr, class IterSwap>
void sort(
RandomAccessIterator _First,
RandomAccessIterator _Last,
BinaryPredicate _Comp,
IterSwap _Swap
);

It seems that std::sort works only with "simple" element, which has
default constructor and value semantics. So the problem rises when I
want to sort a collection of point coordinates, like:

// sort 2D points, note that I use double(*)[2] to hold points'
coordinates.
void SortPoint(double coords[][2], int n)
{
sort(coords, coords + n, PointLess()); // compile error in
std::swap, require l-value.
}

What I want is somthing like:

void SortPoint(double coords[][2], int n)
{
sort(coords, coords + n, PointLess(), PointSwap());
}

Wish somebody to share his(her) thought about this!

// compare points
class PointLess
{
public:
bool operator() (double* a, double* b)
{
if(abs(a[0] - b[0]) > tolerance)
return a[0] < b[0];

return a[1] < b[1];
}
};

// swap points
class PointSwap
{
public:
void operator() (double* a, double* b)
{
swap(a[0], b[0]);
swap(a[1], b[1]);
}
};

You might consider using std::tr1::array instead of built-in arrays:

#include <algorithm>
#include <tr1/array>

typedef std::tr1::array< double, 2 > Point;
typedef Point * matrix;

int main ( void ) {
matrix from = 0;
matrix to = 0;
std::sort( from, to, PointLess() );
}


Note, however, that your comparison function looks fishy. In particular, the
result of std::sort used with that comparison function might very well
depend on the order in which elements are compared and therefore it will
depend on the sorting algorithm that is used. For illustration consider
tolerance == 2 and the sequence

(5,1) (4,2) (3,3) (2,4) (1,5)

If the algorithm only compares adjacent slots and swaps if the order is
violated, this sequence will be considered sorted. Different sorting
algorithms, however, will reorder.

You might want to use ordinary lexicographic comparison (which would be used
with std::tr1::array by default).


Best

Kai-Uwe Bux

 

[Michael DOUBEZ]

panzhiyong a écrit :

Hi there! I wonder why there is no such a overload version of sort
function in STL:

template<class RandomAccessIterator, class Pr, class IterSwap>
void sort(
RandomAccessIterator _First,
RandomAccessIterator _Last,
BinaryPredicate _Comp,
IterSwap _Swap
);

It seems that std::sort works only with "simple" element, which has
default constructor and value semantics. So the problem rises when I
want to sort a collection of point coordinates, like:

// sort 2D points, note that I use double(*)[2] to hold points'
coordinates.
void SortPoint(double coords[][2], int n)
{
sort(coords, coords + n, PointLess()); // compile error in
std::swap, require l-value.
}

What I want is somthing like:

void SortPoint(double coords[][2], int n)
{
sort(coords, coords + n, PointLess(), PointSwap());
}

Wish somebody to share his(her) thought about this!

// compare points
class PointLess
{
public:
bool operator() (double* a, double* b)
{
if(abs(a[0] - b[0]) > tolerance)
return a[0] < b[0];

return a[1] < b[1];
}
};

// swap points
class PointSwap
{
public:
void operator() (double* a, double* b)
{
swap(a[0], b[0]);
swap(a[1], b[1]);
}
};

You could use an iterator_facade.Boost provides an implmentation but it
is included in TR1 so it is next to standard.

You basically wrap a double* pointer but:
* iterator increments are done by twos
* distance is given divided by two
* return type is a struct { double& x; double& y;}; to allow copy

Seems a bit of a pain but you only need to implement it once. I have
very little experience about it so I cannot evaluate if it is worth the
trouble.

Here is the example from Boost:
http://boost.org/libs/iterator/doc/iterator_facade.html#tutorial-example


Michael

 

[James Kanze]

Hi there! I wonder why there is no such a overload version of sort
function in STL:

template<class RandomAccessIterator, class Pr, class IterSwap>
void sort(
RandomAccessIterator _First,
RandomAccessIterator _Last,
BinaryPredicate _Comp,
IterSwap _Swap
);

Because the correct solution here is to provide an appropriate
swap action for the object in question.

It seems that std::sort works only with "simple" element, which has
default constructor and value semantics.

It definitly requires value semantics. You can't move elements
around unless they have value semantics, and you can't sort
unless you can move elements around. There's no requirement
for a default constructor, however. And the elements can be as
complicated as you want: you can sort an array of std::map, for
example (provided you define an appropriate ordering criteria).

So the problem rises when I want to sort a collection of point
coordinates, like:

// sort 2D points, note that I use double(*)[2] to hold points'
coordinates.
void SortPoint(double coords[][2], int n)
{
sort(coords, coords + n, PointLess()); // compile error in
std::swap, require l-value.
}

C style arrays are broken. In C++, this would probably be
written more like:

void SortPoint( std::vector< Point >& coords )
{
std::sort( coords.begin(). coords.end(), PointLess() ) ;
}

There are very few practical reasons to ever use a C style
array, and from what I've seen, boost::array subsumes them all.

What I want is somthing like:

void SortPoint(double coords[][2], int n)
{
sort(coords, coords + n, PointLess(), PointSwap());
}

Wish somebody to share his(her) thought about this!

Write it correctly, using a Point class, and it should work.