Solved

Custom Sort Routine for an STL Container?

Posted on 2001-08-01
33
309 Views
Last Modified: 2013-12-14
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
Comment
Question by:magenta
  • 17
  • 10
  • 3
  • +2
33 Comments
 
LVL 30

Expert Comment

by:Axter
ID: 6343455
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
 
LVL 30

Expert Comment

by:Axter
ID: 6343471
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
 
LVL 3

Expert Comment

by:elcapitan
ID: 6343888
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
 
LVL 30

Expert Comment

by:Axter
ID: 6344098
itoa is not part of the ANSI C/C++ standards.
0
 
LVL 30

Expert Comment

by:Axter
ID: 6344102
Oops.  Sorry.
Please disregard my above comment.
I posted the above comment in the wrong question.
0
 
LVL 30

Expert Comment

by:Axter
ID: 6344158
elcapitan,
Your right.

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
 
LVL 22

Accepted Solution

by:
nietod earned 200 total points
ID: 6344505
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
 
LVL 2

Expert Comment

by:antoinebf
ID: 6345387
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
 
LVL 22

Expert Comment

by:nietod
ID: 6345462
"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
 
LVL 30

Expert Comment

by:Axter
ID: 6345836
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
 
LVL 2

Expert Comment

by:antoinebf
ID: 6345861
random iterator... You must have them to "global sort", and I don't think list supports them. List only have bidirectional iterators.
0
 
LVL 22

Expert Comment

by:nietod
ID: 6345888
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
 
LVL 30

Expert Comment

by:Axter
ID: 6345894
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
 
LVL 30

Expert Comment

by:Axter
ID: 6345903
>>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
 
LVL 30

Expert Comment

by:Axter
ID: 6345912
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
 
LVL 30

Expert Comment

by:Axter
ID: 6345924
FYI,
The std::sort function should be faster then the list::sort function, because the global std::sort function can use random iterator.
0
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 
LVL 22

Expert Comment

by:nietod
ID: 6345962
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
 
LVL 30

Expert Comment

by:Axter
ID: 6345993
>>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
 
LVL 30

Expert Comment

by:Axter
ID: 6346004
>>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
 
LVL 22

Expert Comment

by:nietod
ID: 6346073
>> 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
 
LVL 30

Expert Comment

by:Axter
ID: 6346130
>>// 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
 
LVL 22

Expert Comment

by:nietod
ID: 6346225
>> 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
 
LVL 22

Expert Comment

by:nietod
ID: 6346240
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
 
LVL 30

Expert Comment

by:Axter
ID: 6346324
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
 
LVL 30

Expert Comment

by:Axter
ID: 6346346
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
 
LVL 22

Expert Comment

by:nietod
ID: 6346375
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 Comment

by:magenta
ID: 6346382
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
 
LVL 30

Expert Comment

by:Axter
ID: 6346389
>>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
 
LVL 22

Expert Comment

by:nietod
ID: 6346414
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
 
LVL 30

Expert Comment

by:Axter
ID: 6346421
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.
Could you please help me to understand?
Thank you
0
 
LVL 22

Expert Comment

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

Author Comment

by:magenta
ID: 6347057
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 Comment

by:magenta
ID: 6347083
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

Featured Post

What Security Threats Are You Missing?

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

Join & Write a Comment

  Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and …
This article shows you how to optimize memory allocations in C++ using placement new. Applicable especially to usecases dealing with creation of large number of objects. A brief on problem: Lets take example problem for simplicity: - I have a G…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

757 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

21 Experts available now in Live!

Get 1:1 Help Now