x
• Status: Solved
• Priority: Medium
• Security: Public
• Views: 323

# Custom Sort Routine for an STL Container?

How do I pass a custom sort routine to an STL container in VC++?

I know that I can simply implement the < operator in my element class, but what if the element is a pointer and I want the ordering to be based on what that pointer points to?

My friend suggested the following code from GCC but I couldn't get it to work on VC++:

#include <iostream>
#include <list>
using namespace std;

typedef struct {
int a;
int b;
} X;

bool sortFunction(X* a, X* b)
{
if (a->b <= b->b)
return true;
return false;
}

int main()
{
X o1 = {1, 9};
X o2 = {2, 8};
X o3 = {3, 7};
list<*X> l;
l.push_back(&o1);
l.push_back(&o2);
l.push_back(&o3);
l.sort(sortFunction);
return 0;
}

Thanks!
Frank
0
magenta
• 17
• 10
• 3
• +2
1 Solution

Commented:
You can use the following method:

#include <iostream>
#include <list>
using namespace std;

typedef struct xx {
int a;
int b;
bool operator<(const xx& src)
{
if (b <= src.b)     return true;
return false;
}
} X;

int main()
{
X o1 = {1, 9};
X o2 = {2, 8};
X o3 = {3, 7};
list<X*> l;
l.push_back(&o1);
l.push_back(&o2);
l.push_back(&o3);
l.sort();
return 0;
}
0

Commented:
In order to use the list::sort function, you need to create an operator<() in your class/struct.

The list::sort function can accept classes like std::greater<X*>(), but this is not the sortting function, this is telling the list::sort in what order to sort the list to.

Example:

#include <iostream>
#include <list>
using namespace std;

typedef struct xx {
int a;
int b;
bool operator<(const xx& src)
{
if (b <= src.b)     return true;
return false;
}
} X;

int main()
{
X o1 = {1, 9};
X o2 = {2, 8};
X o3 = {3, 7};
list<X*> l;
l.push_back(&o1);
l.push_back(&o2);
l.push_back(&o3);
l.sort(std::greater<X*>());
return 0;
}

0

Commented:
Axter:
That would'nt work since std::greater<X*>() will comapre the pointers to the objects and not the objects themselves.
Also, std::greater<X>() calls  operator >  of X and not operator < .

--EC--
0

Commented:
itoa is not part of the ANSI C/C++ standards.
0

Commented:
Oops.  Sorry.
I posted the above comment in the wrong question.
0

Commented:
elcapitan,

You could try the following:

#include <iostream>
#include <algorithm>
#include <vector>
#include <list>
using namespace std;

typedef struct xx {
int a;
int b;
bool operator<(const xx& src) const;
bool operator>(const xx& src) const;
} X;

bool xx::operator<(const xx& src) const
{
if (b <= src.b)     return true;
return false;
}
bool xx::operator>(const xx& src) const
{
if (b > src.b)     return true;
return false;
}

template<typename T>
class PtrClass
{
public:
T *m_src;
PtrClass(T &src):m_src(&src)
{
}
bool operator<(const PtrClass& src) const
{
return m_src->operator<(*src.m_src);
}
bool operator>(const PtrClass& src) const
{
return m_src->operator>(*src.m_src);
}
};

int main()
{
X o1 = {1, 9};
X o2 = {2, 8};
X o3 = {3, 7};
list<PtrClass<X> > l;
l.push_back(o1);
l.push_back(o2);
l.push_back(o3);
l.sort();
return 0;
}

0

Commented:
The orignal code is fine, except that it makes us of a member template function in the list class.  The standard list::sort() is a template function.   Unfortuantely VC does not support member templates functions.  So this function was made a non-template in VC.  Axter's post that uses operator > will work on VC because it will use the one version of this function that VC supplies.

So this does not indicate that the orignal code was wrong, only that VC is not capable of handlign it.

Note that you could use the global sort() template function instead.

#include <iostream>
#include <list>
using namespace std;

// NOTE this is the C++ way to declare a structure. Its
// probably better to use if you will only be using it
// in C++.  The other way is for code that will be used
// in C.
struct X {
int a;
int b;
};

bool sortFunction(X* a, X* b)
{
return (a->b <= b->b);   // Note this simplification.
// Not needed, but its nice.
}

int main()
{
X o1 = {1, 9};
X o2 = {2, 8};
X o3 = {3, 7};
list<*X> l;
l.push_back(&o1);
l.push_back(&o2);
l.push_back(&o3);

// Here is the global sort.
sort(l.begin(),l.end(),sortFunction);

return 0;
}

NOTE that the global sort function does not require you to define operator >  (which is not a bad thing to define houever).   However, the global sort function might be slower than the member sort function.
0

Commented:
Hi Nietod,
would it be better to used the list's sort() instead of <algorithm>'s? ... since container methods are (should be) more efficient that those generic ones?

I realize both will do the trick...
0

Commented:
"Better" is in the eye of the beholder.  As I said in my last sentence, the member sort fucntion _might_ be faster than the global sort.  (Its never going to be slower.)  If speed is an issue, then the member function might be the way to go.   But if you don't want to add that interface class, or if you  cannot add operator > for the class, or if there is an usuitable operrator >, then can't use the fix Axter presented and the global sort may be the best choice.
0

Commented:
I don't think you can use the global std::sort function on a list container.
I don't remember what what is the restriction, but the restriction is the reason why list is the only container that has a built in sort function.
You'll notice that vector and deque don't have a sort function, and that's because you can use the global std::sort on both vector and deque, but you can't use it on list.
0

Commented:
random iterator... You must have them to "global sort", and I don't think list supports them. List only have bidirectional iterators.
0

Commented:
I don't know the restrictions on the glboal sort() iterators, the list has bidiretional iteators, which is the  2nd most powerful, the global sort might require random access iterators, which would be the most powerful.

>> random iterator... You must have them to "global sort"
If that is true, then you can't use global sort with a list  (or if you do, it might work but not be portable.).
0

Commented:
antoinebf,
>>random iterator... You must have them to "global sort",
>>and I don't think list supports them. List only
>>have bidirectional iterators.
You got it.  That's right.
That's also the reason why list has it's own merge member function as well.
0

Commented:
>>list  (or if you do, it might work but not be ortable.).
You can't use it at all.
The compiler won't even let you compile it.  You'll get a compile error.
0

Commented:
magenta,
I'm not sure why you picked the std::list container, but if you want to use the global std::sort, you might want to reconsier using vector or deque.
Both vector and deque will allow you to use the global std::sort
0

Commented:
FYI,
The std::sort function should be faster then the list::sort function, because the global std::sort function can use random iterator.
0

Commented:
Yes, sort does take a random access iterator, so it might not work with a list<>  And it would work it would be unwise to rely on it if it does.  so you are largely stuck with Axter's patch, or finding a new compiler

>> >>list  (or if you do, it might work but not be ortable.).
>> You can't use it at all.
>> The compiler won't even let you compile it.  You'll get
>>  a compile error.
That is not necessarly true. It will depend on the sort() algorithm.  There is no formal random access iterator type or bidirectionla iteraotr type.  They are defined by their behavior, if the sort algorithm does not use use any random-access operation, then it would compile and work correctly with a bidirectional iterator.  Not that it is a good thing to do, but it will work.
0

Commented:
>>That is not necessarly true. It will depend on the sort
>>() algorithm.
If you're talking about the ANSI C++ standard std::sort function, then it will always fail to compile.

Sort has the following interface:
template< class RandomAccessIterator>
void sort (RandomAccessIterator first, RandomAccessIterator last);

Meaning that sort requires two iterators, both of them random access category.

No matter the implementation, if you're using an ANSI C++ standard std::sort function, it will not compile with a list.
0

Commented:
>>then it would compile and work correctly with a
>>idirectional iterator.
A list will never compile with an ANSI C++ standard std::sort function.
0

Commented:
>> A list will never compile with an
>> ANSI C++ standard std::sort function.
Why?

Think about it.  There is no type associated with random iterator.  That is a convention we use to discuss them.  It describes the type of behavior that the iterator supplies.  That is all.  I can write

template <typename RanItr T>
void sort(RanItr Bgn, RanItr End)
{
// do bubble sort here.
}

this will work fine.  Addmitidly a bubble sort is a bad aproach, but the code will work fine with a bidirectional iterator.  In fact, it would work with a forward iterator.  the bubble sort doesn't use any random access or any reverse access--unless you write a weird one.

So it could compile with a bidirectional or even just forward iterator.  That is not a portable assumption, but its not impossible.  This is a "problem" that comes up frequently because it allows programmers to write code that is not portable by mistake.  The classic problem is assuming that iterator converts implicitly to constant iterator.  This tends to be true for most iterators, but its not portable.  Same idea.
0

Commented:
>>// do bubble sort here.
The implementation can not use a bubble sort.
According to the standards, the std::sort function has to be able to perform on average N*log(N).
N Log N(Where N == Last - First) comparisons on average

You can not get that type of performance without using a Random-Access-Iterator

/////////////////////
>>template <typename RanItr T>
>>void sort(RanItr Bgn, RanItr End)
>>{
>>  // do bubble sort here.
>>}

That would not be a std::sort function.

You can make an application defined sort function that will take an std::list.  There's no problem with that.
If that's what you're trying to say, then I agree with that.

But you can not compile a std:list to an std::sort function.
It won't compile.
0

Commented:
>> The implementation can not use a bubble sort.
I never said it did.  i said I could write one that did.

>> You can not get that type of performance
>> without using a Random-Access-Iterator
Here you go again.

Is that based on your knowledge of all sort algorithms.  Not yest all know sort algorityhms, but all that will ever be known?

You cannot prove the NULL hypothesis unless you measure every single possble case and that is almost always an impossibility.

There may be algorithms that perform the sort using bi-directional iterators.

Note that new algorithms are found all the time.  the popular implimentation for the dequeue is realtively new and far faster than the traditional array based queue design.  I published a new algorithm for stirng classes that make them faster under sub-string ooperations.  New algorithms do appear.

>>That would not be a std::sort function.
That has the exact same format.  They point is that the interface to std::sort does not place _any_ restrictions on the values passed to sort().  You can call it like

sort(1.2 k 4.5)

and pass it doubles.  The restrictions are placed according to the behavor that the algorithm demands of the parameters.  If the algorithm doesn't demand random access, the iterators don't have to be random access.

>> But you can not compile a std:list to an std::sort >> function.  It won't compile.
It is an error to do so.  It is an error that might be caught by the compiler.  But it is not necessarily true that it won't compile.  And if it does compile it will work correctly, however that it is certainly not portable since many compilers won't allow it.
0

Commented:
In fact now that I think about it, any N*logN algorithm can be made to work with only forward iterators and work in N*logN time.  Its not necessarily smart, but it can be done.   so no new algorithms are even needed.  But of course their possibility shoudl not be dismissed.
0

Commented:
I'm sure you don't know of any compiler that can compile an std::list with an std::sort.
Absolutely none of the major compilers will allow this work, and I'm sure there's none that exist.

If you know of one, please feel free to post it, and prove me wrong.

If you can't find one, then this conversation is irrelevant, and serves no purpose.

What is important, is that the questioner should avoid using the suggested method of useing std::sort for an std::list.

According to "The C++ Programming Language" by Bjarne Stoustrup
Section 18.7.1 [Sorting]
The standard list does not provide random-access iterators, so lists should be sorted using the specific list operations.
0

Commented:
nietod,
Since I'm sure this questioner is not using one of your fancy make-believe non-existing compilers, I think we should set aside this argument, and get back to helping the questioner with his realistic real world problem.
0

Commented:
The fact that something doesn't currently exist doesn't mean it can't exist.

>> If you know of one, please feel
>> free to post it, and prove me wrong.
When will you get this?????

The only way to prove that something is impossible (by example) is by testing all possible examples.  No one can test all _possible_ compilers.  That does no mean all compilers in existance.  it includes all compilers that will be written in the future AND all compilers that could be written but will not be written.  Who can test all that.  Yet that is what you must do to proove your point by example.  That is why you never see anyone use examples to prove the NULL hypothesis!  its impossible.

On the other hand my point can be proven easily.  I don't have to proove that any such compiler does this.  The meer possiblity of the compiler doing it is sufficient proof.

this should be nearly self-evident.  Anyone taking an itroductory science course should know this.

>> the questioner should avoid using the
>> suggested method of useing std::sort
>> for an std::list.
That is true.

>> If you can't find one, then this conversation is >> irrelevant,
I don't know of a compiler that supports member templates. I don't know of one that supports exported templates.
I don't kow of any compiler that supposrts the C++ standard completely.

Would all conversations about these topics be irrelevant?  Of course not.

just because something doesn't exist, we don't rule out the possibility that it will exist in the future.  Otherwise how would any progress ever be mede?
0

Author Commented:
Nietod's code was almost there. I had to change it to use a deque (there was no real reason to use a list) and some other very minor changes.

Thanks to everyone though! I think that this was a very interesting discussion.

Here is the final code that does exactly what I need:

#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;

struct X
{
int a;
int b;
};

bool sortFunction(X* a, X* b)
{
return (a->b <= b->b);
}

void print( deque<X*>& d )
{
for ( size_t i = 0; i < d.size(); i++ )
cout << "(" << d[ i ]->a << "," << d[ i ]->b << ") ";
cout << endl;
}

int main()
{
X o1 = {1, 9};
X o2 = {2, 8};
X o3 = {3, 7};
deque<X*> l;
l.push_back(&o1);
l.push_back(&o2);
l.push_back(&o3);
print( l );
sort(l.begin(),l.end(),sortFunction);
print( l );
return 0;
}

0

Commented:
>>just because something doesn't exist, we don't rule out
>>the possibility that it will exist in the future.
>> Otherwise how would any progress ever be mede?

We can rule it out because we already know that we should not used your suggested method "sort(list)", even if your fantacy compiler did exist.
Since we can rule it out, there's no point in continuing this conversation.

Furthermore,
Since I'm sure this questioner is not using one of your fancy make-believe non-existing compilers, I think we should discontinue this point, and get back to helping the questioner with his realistic real world problem.
0

Commented:
magenta, do you understand that my suggestion of using the global sort was wrong.  Axter's code is the best you can do  (more or less) with VC.

You awarded the points to me, not to Axter.  That is your choice, but its a little surprising.

>> Since we can rule it out, there's no
>> point in continuing this conversation.
Since YOU have ruled it out.  There is no point.  There is never a point in trying to convince you of anything.  Certainly its is not rulled out.  how do you thik the C++ standard committee gets things done.  They don't talk about any feature that doesn't yet exist in a compiler?  Theyld get no where!
0

Commented:
magenta,
I'm ususally not one to complain about a questioner's decission, but I posted a workerable method.
It was the only method available that could work with the std::list functiion in the GCC compiler.

I also suggested that you change your container to vector or deque.

If you would have used nietod's posted code, the code would not have worked.

Since you did not provide feedback on my original posted method, and nieto's code does not work as-si, and you used my suggestion, I don't understand why you awarded nietod the answer, and I don't understand why you gave him the full amount.
Thank you
0

Commented:
Just the calrify,t he original worked with GCC.  It didn't work with VC. Axter's patch should work with both.
0

Author Commented:
Nietod's code was almost there. I had to change it to use a deque (there was no real reason to use a list) and some other very minor changes.

Thanks to everyone though! I think that this was a very interesting discussion.

Here is the final code that does exactly what I need:

#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;

struct X
{
int a;
int b;
};

bool sortFunction(X* a, X* b)
{
return (a->b <= b->b);
}

void print( deque<X*>& d )
{
for ( size_t i = 0; i < d.size(); i++ )
cout << "(" << d[ i ]->a << "," << d[ i ]->b << ") ";
cout << endl;
}

int main()
{
X o1 = {1, 9};
X o2 = {2, 8};
X o3 = {3, 7};
deque<X*> l;
l.push_back(&o1);
l.push_back(&o2);
l.push_back(&o3);
print( l );
sort(l.begin(),l.end(),sortFunction);
print( l );
return 0;
}

0

Author Commented:
Axter, the reason why I awarded the points to Nietod and not you is because his solution worked with pointers without the need for an addition pointer-holder class. However, I understand what you are saying that your solution would work and that Nietod's needed some work.

Ideally,  I would have given points to both of you, but since everyone was posting as comments, and I chose to work off of Nietod's code instead of yours, I just decided to give it to him. I'm not sure why everyone does that (that seems to be pretty commmon at least with my questions) but if you had felt that strongly about your solution, then I think you should have given it as an answer and not a comment.

Again, my decision wasn't based on much, and it certainly doesn't mean that your solution was wrong or that it wouldn't work.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.