Link to home
Start Free TrialLog in
Avatar of martie
martie

asked on

sort a list of pointer with STL::list

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!
Avatar of LoungeLizard
LoungeLizard

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;
}



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.
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.

Avatar of Axter
//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.....
Should have tried it before posting! :)

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

A.
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;
     }
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;
}

Should have tried it before posting! :)

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

A.
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.
> 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).
>>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.
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.
Avatar of martie

ASKER

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
     {.....}
}
Avatar of martie

ASKER

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..
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;
}

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;
}

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

That should give access to myObject to the std::greater functor.
Avatar of martie

ASKER

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......

> 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.

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;
}

ASKER CERTIFIED SOLUTION
Avatar of Axter
Axter
Flag of United States of America image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Avatar of martie

ASKER

thanks you deserve it.. but i prefer placing the list within private of ProcessOrder..
Avatar of martie

ASKER

thanks, you deserve it, but i prefer placing the list(definition and declaration) within the protected or private of ProcessOrder
Avatar of martie

ASKER

Axter :
Oh, no, i got internal compiler error for the last program you posted..
> 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...
 
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.
Avatar of martie

ASKER

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.