Solved

sort a list of pointer with STL::list

Posted on 2002-05-27
27
978 Views
Last Modified: 2013-12-14
I have declared a list ..
class myObject{
public:
     myObject(){m_Val = 0;}
     int getVal{return Val;}
     setVal(int pVal){m_Val = pVal;}
     /* a list of operator like ==, !=, <=, >= */
private:
     m_Val;
}
typedef std::list<myObject *> MYLIST;
MYLIST myList;

But when i want to sort the objects in terms of m_Val of each object, i failed as i can't use myList.sort() as i believe it sorts the list in terms of pointer to myObject.
I also tried to use greater..    

std::greater<myObject *> pr;
myList.sort(pr);

it also failed, i didn' tknow why.. i have already defined the <=, >=, != and == operator for my object
So, how can I sort the order? If I use the algorithm sort, any hints, it is rather complicated for me, please also give me the code please.

Cheers!
0
Comment
Question by:martie
  • 12
  • 7
  • 4
  • +2
27 Comments
 
LVL 2

Expert Comment

by:LoungeLizard
ID: 7036768
You'll need to impliment the operator< for your class. The list.sort will use this to do sorting. If it cannot find it, it will use pointer (address) comparison. So, you need something like this...

int myObject::operator<(const myObject * rhs) const
{
  return m_Val < rhs->m_Val ? 1 : 0;
}



0
 
LVL 2

Expert Comment

by:antoinebf
ID: 7037302
The problem is that you are attempting to sort the element based on their values, but you stored their pointers...

In effect, you are sorting correctly the pointer values... and that not really what you want!

To correct that situation, I usually provide the sort method a "sort criteria". This criteria is a functor and will be called a number of times to adequatly sort the element based on your own criteria (and not the default one (<)).

Here is sample code:

struct STSortCriteria : std::binary_function<myObject*, myObject*, bool>
{
   inline bool operator() (const myObject*& lhs, const myObject*& rhs)
   {
      return lhs->getVal() < rhs->getVal();
   }
};

...
   myList.sort(STSortCriteria());
...

The functor STSortCriteria provides 3 params to its base class: two myObject pointers (the actual type that is stored in the list) and a bool (the comparison return type). The instance you provide sort() will then be called internally a number of times and wiil then dereference the pointers and compare the actual values stored in each of them and returns the according bool. (instead of simply comparing the pointers).

One important thing to ensure best performance and good results is to provide a criteria that will always yield the same result for the same comparison.

You can use this approach for many STL sorts (vector, deque).

Hope this helps! If you have any questions, do not hesitate!

A.
0
 
LVL 2

Expert Comment

by:antoinebf
ID: 7037318
BTW,
You can also use algorithm's sort with the above criteria, but the list's own sort should be more efficient. I would then recommend using it instead of the generic one.

Anywhow, this code will also work:

std::sort(myList.begin(), myList.end(), STSortCriteria());

This is actually the call when you want to sort a vector or a deque, who do not provide a sort member method.

A.

0
 
LVL 30

Expert Comment

by:Axter
ID: 7037638
//Anywhow, this code will also work:
//std::sort(myList.begin(), myList.end(), STSortCriteria());

That code will not work on a std::list.  One of the reasons that std::list has it's own sort member function is because the generic std::sort function will not work on an std::list.  It fails to work due to the iterator type.

Continue.....
0
 
LVL 2

Expert Comment

by:antoinebf
ID: 7037642
Should have tried it before posting! :)

You're absolutely right... because of the random iterators... thanks!

A.
0
 
LVL 30

Expert Comment

by:Axter
ID: 7037643
To use list::sort with pointers, you need to specialize the std::greater<>::operator() function.

Example:
template<>
struct std::greater<myObject*>
{
public:
     bool operator()(const myObject*& lhs, const myObject*& rhs)
     {
          return lhs->getVal() < rhs->getVal();
     }
};

Then call sort via the following syntax:
myList.sort(std::greater<myObject*>());

Make sure that the member function that is called in your object (getVal) is of a const type.
Example:
    int getVal() const //Constant here
     {
          return m_Val;
     }
0
 
LVL 30

Expert Comment

by:Axter
ID: 7037645
Full example:

class myObject{
public:
    myObject(){m_Val = 0;}
    int getVal() const //Constant here
     {
          return m_Val;
     }
    void setVal(int pVal){m_Val = pVal;}
private:
    int m_Val;
};

template<>
struct std::greater<myObject*>
{
public:
     bool operator()(const myObject*& lhs, const myObject*& rhs) const
     {
          return lhs->getVal() < rhs->getVal();
     }
};




typedef std::list<myObject *> MYLIST;
MYLIST myList;


int main(int argc, char* argv[])
{
     const Qty = 4;
     myObject My_myObject[Qty];
     int SomeNum[Qty] = {3, 8, 7, 2};
     for (int i = 0;i < Qty;++i)
     {
          My_myObject[i].setVal(SomeNum[i]);
          myList.push_back(&My_myObject[i]);
     }

     myList.sort(std::greater<myObject*>());
     
     
     for (MYLIST::iterator x = myList.begin();x != myList.end();++x)
     {
          std::cout << (*x)->getVal() << std::endl;
     }
     
     system("pause");
     return 0;
}

0
 
LVL 2

Expert Comment

by:antoinebf
ID: 7037650
Should have tried it before posting! :)

You're absolutely right... because of the random iterators... thanks!

A.
0
 
LVL 30

Expert Comment

by:Axter
ID: 7037670
FYI:
antoinebf's STSortCriteria should work on a compiler that fully adheres to the standard.
HOWEVER, we all know that most compilers don't.
This definitely applies to MSVC++.

STSortCriteria will not work on VC++ if you're using the build-in STL that comes with it, because the VC++ implementation requires a class that derives from std::greater.

Furthermore, I tried deriveing a class from std::greater, and much to my surprise, it also failed to work.  Although it did compile.
I'm not sure why the derive class does not work, but I think it has to do with the implementation taking the argument by value of (std::greater) type.

The only thing that seems to work with VC++ is specialization.
Of course this may be a non-issue if martie is using a compiler that can successfully implement antoinebf's method.
0
 
LVL 9

Expert Comment

by:jasonclarke
ID: 7037783
> HOWEVER, we all know that most compilers don't.

not strictly true,  I think virtually every decentt compiler other than MSVC 6 (and it's predecessors) will do a better job.

> This definitely applies to MSVC++.

This is also fixed in MSVC 7 (VC++ .NET).
0
 
LVL 30

Expert Comment

by:Axter
ID: 7037928
>>not strictly true,  I think virtually every decentt
>>compiler other than MSVC 6 (and it's predecessors)
>>will do a better job.
They may do a better job, but they most still don't fully adhere to the standard.

>>This is also fixed in MSVC 7 (VC++ .NET).
This particular problem may have been fixed with 7, but according to the information I've read, 7 still has not fixed all the issues required for it to be fully compatible with the standard.
0
 
LVL 30

Expert Comment

by:Axter
ID: 7037931
jasonclarke,
>>This is also fixed in MSVC 7 (VC++ .NET).

I've read the MSVC 7 (VC++ .NET) has not change the STL version that they're using.

Are you saying that it has been changed?

The above problem exist in the STL code, and not with the compiler itself.  So if it has been fixed with 7, then the STL has to have been modified.
0
 

Author Comment

by:martie
ID: 7038271
Thanks mates, I am sad to tell you guys that the codes i write have to be portable, in Windows(MSVC++6) and Solaris(ForteC). I have tried to derive from greater but i failed as i could'nt derive from a struct.. greater is a struct...

Axter: your code can be compiled but in fact the class  myObject is not defined in a global namespace, it is within a class.. so I cannot use the explicit specialization.... i have tried to put the template everywhere but i failed..so what should I do? The sorting is supposed to be done within a member function of ProcessOrder... for example...

class ProcessOrder
{
public:
....
private:
....
     class myObject
     {.....}
}
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

 

Author Comment

by:martie
ID: 7038281
1)
I put the class myObject in public and in the greater, i replace myObject by ProcessOrder::myObject and put the greater class in global namespace but I got:
error C2908: explicit specialization; 'greater<class GL_V5_CCMMsgBody::CCMField *>' has already been instantiated from the primary template!
2)
I put the greater within the the class ProcessOrder..together with the class myObject but I got internal compiler error!
... what should I do now? I am using VSC++6, if it works, i will put the code in solaris and compile it..
0
 
LVL 30

Expert Comment

by:Axter
ID: 7038282
Try the following example:

class ProcessOrder
{
public:
     void SomeFunction();
     class myObject{
     public:
          myObject(){m_Val = 0;}
          int getVal() const //Constant here
          {
               return m_Val;
          }
          void setVal(int pVal){m_Val = pVal;}
     private:
          int m_Val;
     };
private:
};


template<>
struct std::greater<ProcessOrder::myObject*>
{
public:
     virtual bool operator()(const ProcessOrder::myObject*& lhs, const ProcessOrder::myObject*& rhs) const
     {
          return lhs->getVal() > rhs->getVal();
     }
};

typedef std::list<ProcessOrder::myObject *> MYLIST;
MYLIST myList;

void ProcessOrder::SomeFunction()
{
     const Qty = 4;
     ProcessOrder::myObject My_myObject[Qty];
     int SomeNum[Qty] = {3, 8, 7, 2};
     for (int i = 0;i < Qty;++i)
     {
          My_myObject[i].setVal(SomeNum[i]);
          myList.push_back(&My_myObject[i]);
     }
     
     myList.sort(std::greater<ProcessOrder::myObject*>());
     
     
     for (MYLIST::iterator x = myList.begin();x != myList.end();++x)
     {
          std::cout << (*x)->getVal() << std::endl;
     }
}

int main(int argc, char* argv[])
{
     ProcessOrder MyProcessOrder;
     MyProcessOrder.SomeFunction();
     system("pause");
     return 0;
}

0
 
LVL 30

Expert Comment

by:Axter
ID: 7038285
If you want to keep your class private, try the following method:
class ProcessOrder
{
public:
     void SomeFunction();
private:
     class myObject{
     public:
          myObject(){m_Val = 0;}
          int getVal() const //Constant here
          {
               return m_Val;
          }
          void setVal(int pVal){m_Val = pVal;}
     private:
          int m_Val;
     };
     friend struct std::greater<myObject*>;
};


template<>
struct std::greater<ProcessOrder::myObject*>
{
public:
     virtual bool operator()(const ProcessOrder::myObject*& lhs, const ProcessOrder::myObject*& rhs) const
     {
          return lhs->getVal() > rhs->getVal();
     }
};

typedef std::list<ProcessOrder::myObject *> MYLIST;
MYLIST myList;

void ProcessOrder::SomeFunction()
{
     const Qty = 4;
     ProcessOrder::myObject My_myObject[Qty];
     int SomeNum[Qty] = {3, 8, 7, 2};
     for (int i = 0;i < Qty;++i)
     {
          My_myObject[i].setVal(SomeNum[i]);
          myList.push_back(&My_myObject[i]);
     }
     
     myList.sort(std::greater<ProcessOrder::myObject*>());
     
     
     for (MYLIST::iterator x = myList.begin();x != myList.end();++x)
     {
          std::cout << (*x)->getVal() << std::endl;
     }
}

int main(int argc, char* argv[])
{
     ProcessOrder MyProcessOrder;
     MyProcessOrder.SomeFunction();
     system("pause");
     return 0;
}

0
 
LVL 30

Expert Comment

by:Axter
ID: 7038287
Notice I added the following to your class:
friend struct std::greater<myObject*>;

That should give access to myObject to the std::greater functor.
0
 

Author Comment

by:martie
ID: 7038510
Axter:
I am sorry and i should have told you the details
The following definition and declaration are both within the private of the class....

typedef std::list<ProcessOrder::myObject *> MYLIST;
MYLIST myList;

And the error message 'error C2908: explicit specialization; 'greater<class GL_V5_CCMMsgBody::CCMField *>' has already been instantiated from the primary template' makes me confused..
where has it been instantiated?! And i really dont' want to put the myobject and the list out the private or protected of ProcessOrder class......

0
 
LVL 9

Expert Comment

by:jasonclarke
ID: 7038614
> I've read the MSVC 7 (VC++ .NET) has not change the STL
> version that they're using.
> Are you saying that it has been changed?

Absolutely,

Here is the declaration of list::sort from VC++ 7:

template<class _Pr3>
void sort(_Pr3 _Pred);

and from VC++ 6:

typedef greater<_Ty> _Pr3;
...
void sort(_Pr3 _Pr);

these are clearly very different in what they mean.  Basicallly the VC++ 7 STL version takes advantage of the  compiler's full support for member function templates.

0
 
LVL 30

Expert Comment

by:Axter
ID: 7039059
Try the following example:

class ProcessOrder
{
public:
     void SomeFunction();
private:
     class myObject{
     public:
          myObject(){m_Val = 0;}
          int getVal() const //Constant here
          {
               return m_Val;
          }
          void setVal(int pVal){m_Val = pVal;}
     private:
          int m_Val;
     };
     
     template<>
          struct std::greater<myObject*>
     {
     public:
          virtual bool operator()(const myObject*& lhs, const myObject*& rhs) const
          {
               return lhs->getVal() > rhs->getVal();
          }
     };
     typedef std::list<myObject *> MYLIST;
     MYLIST myList;
};



void ProcessOrder::SomeFunction()
{
     const Qty = 4;
     myObject My_myObject[Qty];
     int SomeNum[Qty] = {3, 8, 7, 2};
     for (int i = 0;i < Qty;++i)
     {
          My_myObject[i].setVal(SomeNum[i]);
          myList.push_back(&My_myObject[i]);
     }
     
     myList.sort(std::greater<myObject*>());
     
     
     for (MYLIST::iterator x = myList.begin();x != myList.end();++x)
     {
          std::cout << (*x)->getVal() << std::endl;
     }
}

int main(int argc, char* argv[])
{
     ProcessOrder MyProcessOrder;
     MyProcessOrder.SomeFunction();
     system("pause");
     return 0;
}

0
 
LVL 30

Accepted Solution

by:
Axter earned 200 total points
ID: 7039066
The above example encapsulates everything, so you have no outside exposure to neither myObject, nor to the typedef or std::greater specialization.
0
 

Author Comment

by:martie
ID: 7040799
thanks you deserve it.. but i prefer placing the list within private of ProcessOrder..
0
 

Author Comment

by:martie
ID: 7040801
thanks, you deserve it, but i prefer placing the list(definition and declaration) within the protected or private of ProcessOrder
0
 

Author Comment

by:martie
ID: 7040806
Axter :
Oh, no, i got internal compiler error for the last program you posted..
0
 
LVL 9

Expert Comment

by:jasonclarke
ID: 7041203
> i got internal compiler error for the last program you posted..

seems that MSVC 6 doesn't like the nested classes and the specialisation combination.

It does work if you take away the nesting:

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

class myObject{
public:
     myObject(){m_Val = 0;}
     int getVal() const //Constant here
     {
          return m_Val;
     }
     void setVal(int pVal){m_Val = pVal;}
private:
     int m_Val;
};

template<>
struct std::greater<myObject*>
{
public:
     virtual bool operator()(const myObject*& lhs, const myObject*& rhs) const
    {
          return lhs->getVal() > rhs->getVal();
    }
};

class ProcessOrder
{
public:
    void SomeFunction();
private:
   
    typedef std::list<myObject *> MYLIST;
    MYLIST myList;
};

void ProcessOrder::SomeFunction()
{
    const Qty = 4;
    myObject My_myObject[Qty];
    int SomeNum[Qty] = {3, 8, 7, 2};
    for (int i = 0;i < Qty;++i)
    {
         My_myObject[i].setVal(SomeNum[i]);
         myList.push_back(&My_myObject[i]);
    }
   
    myList.sort(std::greater<myObject*>());
   
   
    for (MYLIST::iterator x = myList.begin();x != myList.end();++x)
    {
         std::cout << (*x)->getVal() << std::endl;
    }
}

int main(int argc, char* argv[])
{
    ProcessOrder MyProcessOrder;
    MyProcessOrder.SomeFunction();
    system("pause");
    return 0;
}

You could probably achieve the same affect as you had before using namespaces instead.

However,  std::list is often not a good choice of data structure (sorting a linked list is, at least in principal, quite inefficient).   If you replaced your list with a vector, your life would be far, far simpler...
 
0
 
LVL 30

Expert Comment

by:Axter
ID: 7042187
martie,
FYI:
I notice you have a bad grading history:
B B C A A C B C B B

Most questions are give an 'A' grade.

'B' or 'C' grade should be reserved for less then satisfactory answer.
If you're dissatisfied with the answer, please give the expert a chance to give you 'A' valued answer by informing him/her of your dissatisfaction.

Many experts are not inclinde to give additional assistance after getting a poor grade.
0
 

Author Comment

by:martie
ID: 7043649
I didn't notice the grades i gave were considered as poor or dissatisfactory...i didn't know the rule here.
For the answer you gave, it's good
But for some other answers, probably the answers couldn't help me solve the problem completey and no more input i could get from them so i finally gave the best answer I got a grade and marks.
0

Featured Post

Enabling OSINT in Activity Based Intelligence

Activity based intelligence (ABI) requires access to all available sources of data. Recorded Future allows analysts to observe structured data on the open, deep, and dark web.

Join & Write a Comment

Many modern programming languages support the concept of a property -- a class member that combines characteristics of both a data member and a method.  These are sometimes called "smart fields" because you can add logic that is applied automaticall…
Update (December 2011): Since this article was published, the things have changed for good for Android native developers. The Sequoyah Project (http://www.eclipse.org/sequoyah/) automates most of the tasks discussed in this article. You can even fin…
This tutorial covers a step-by-step guide to install VisualVM launcher in eclipse.
The viewer will learn how to use and create keystrokes in Netbeans IDE 8.0 for Windows.

708 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

20 Experts available now in Live!

Get 1:1 Help Now