list::sort

My list contains pointers, not the actual objects. How to sort this?

Code:

---

// compiler error generated on this class because it does not
// have a class-specific parameter.
int operator<(MyClass*n1, MyClass*n2)
{
 return n1->x < n2->x;
}


// If I define it like this, no compiler errors but it is never called.
int operator<(MyClass& n1, MyClass& n2)
{
 return n1.x < n2.x;
}

list<MyClass*> theList;

MyClass *item = new MyClass;
theList.push_back(item);
item = new MyClass;
theList.push_back(item);
// etc. etc for the remaining items

// now sort the list

theList.Sort(); // error

---

After the above unsuccessful attempts to sort the list, I tried to use the second form of list::sort, which has a parameter. I THINK the parameter is to a comparison function. but that doesn't work either

Code:

---


int compare(MyClass*n1, MyClass*n2)
{
 return n1.x < n2.x;
}

// next line produces compile error
theList.sort(compare);

---

So, how to sort a list of pointers??????

Thanks

The comparison function should return bool and be const.

Try the following:

Code:

---

struct MyClassCompare
{
  const bool operator()(const MyClass *n1, const MyClass *n2) const
  {
    return n1->x < n2->x;
  }
};
// ...
theList.Sort(MyClassCompare())

---

That produces errors too (VC++ 6.0)

:\DVLP\test6\test6.cpp(36) : error C2664: 'void __thiscall std::list<class MyClass *,class std::allocator<class MyClass *> >::sort(struct std::greater<class MyClass *>)' : cannot convert parameter 1 from 'struct MyClassCompare' to 's
truct std::greater<class ListItemType *>'
No constructor could take the source type, or constructor overload resolution was ambiguous
Error executing cl.exe.

Code:

---

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <list>
using namespace std;
#include <time.h>

class MyClass
{
public:
        int x;
};


struct MyClassCompare
{
  const bool operator()(const MyClass *n1, const MyClass *n2) const
  {
    return n1->x < n2->x;
  }
};

MyClassCompare compare;
typedef int listtype;



int main(int argc, char* argv[])
{
        list<MyClass*> theList;
        list<MyClass*>::iterator it;
        srand(time(0));
        MyClass items[5];       
        for(int i = 0; i < 5; i++)
                items[i].x = rand();
        theList.push_back(&items[0]);
        theList.push_back(&items[1]);
        theList.push_back(&items[2]);
        theList.push_back(&items[3]);
        theList.push_back(&items[4]);

// ***** compiler error on the next line
        theList.sort(MyClassCompare());

        for(it = theList.begin(); it != theList.end(); it++)
        {
                MyClass* n = *it;
                cout << n->x << endl;
        }
        cin.ignore();
        return 0;
}

---

You must be using VC 6.0. There is a bug in the std::list::sort function in that you need a greater<> template to satisfy the compiler. This has been corrected (or should be corrected) in VC 7.0.

Here is the workaround:

Code:

---

#include <iostream>
#include <vector>
#include <list>

#include <time.h>

class MyClass
{
  public:
        int x;
};

template <>
struct std::greater<MyClass*>
{
  bool operator()(const MyClass *n1, const MyClass *n2) const
  {
    return n1->x < n2->x;
  }
};

typedef int listtype;

using namespace std;

int main(int argc, char* argv[])
{
  list<MyClass*> theList;
  list<MyClass*>::iterator it;
  srand(time(0));
  MyClass items[5];
  for(int i = 0; i < 5; i++)
        items[i].x = rand();
 
  theList.push_back(&items[0]);
  theList.push_back(&items[1]);
  theList.push_back(&items[2]);
  theList.push_back(&items[3]);
  theList.push_back(&items[4]);

  theList.sort(greater<MyClass*>());
  for(it = theList.begin(); it != theList.end(); it++)
  {
      MyClass* n = *it;
      cout << n->x << endl;
  }
  cin.ignore();
  return 0;
}

---

You specialize on the greater<> template, and the compiler will now call the greater<MyClass*> instead of the default greater<> (which will just compare pointer values).

Again, the code that Yves posted works correctly and must work correctly on every STL implementation. The only implementation I know where Yves code does not work is on the VC 6.0 STL implementation provided by DinkumWare. I believe DinkumWare has corrected this issue, but you may have to pay for the upgrade.

Regards,

Paul McKenzie

Great! Yes, I am using VC++ 6.0. That worked perfectly.:)

Why is Dinkumware's list::sort taking greater as default ? Doesn't that sort in the reverse direction ? AFAIK, on STLPort you have to pass a less<T> comparison function to get the smaller -> bigger order.

I use VC .NET and has the same problem, I guess it is not fixed yet.

trying to use this workaround I got the following compilation error:

c:\Program Files\Microsoft Visual Studio .NET 2003\Vc7\include\list(760): error C2664: 'bool std::greater<CMyClass*>::operator ()(const CMyClass*,const CMyClass*) const' : cannot convert parameter 1 from 'std::allocator<_Ty>::value_type' to 'const CMyClass*'
with
[
_Ty=CMyClass
]

Quote:

---

Originally posted by Yves M
Why is Dinkumware's list::sort taking greater as default ? Doesn't that sort in the reverse direction ? AFAIK, on STLPort you have to pass a less<T> comparison function to get the smaller -> bigger order.

---

Yes, it's confusing. I guess they work on the second argument being greather than the first. It's the only way to get the compiler to work with that version of list::sort. Anyway, it's broken.

Regards,

Paul McKenzie

Quote:

---

Originally posted by avi123
I use VC .NET and has the same problem, I guess it is not fixed yet.

---

I just tried it, and it works correctly:

Code:

---

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>

#include <time.h>

class MyClass
{
  public:
        int x;
};

struct MyClassCompare
{
  const bool operator()(const MyClass *n1, const MyClass *n2) const
  {
    return n1->x < n2->x;
  }
};

typedef int listtype;

using namespace std;

int main(int argc, char* argv[])
{
  list<MyClass*> theList;
  list<MyClass*>::iterator it;
  srand(time(0));
  MyClass items[5];
  for(int i = 0; i < 5; i++)
        items[i].x = rand();
 
  theList.push_back(&items[0]);
  theList.push_back(&items[1]);
  theList.push_back(&items[2]);
  theList.push_back(&items[3]);
  theList.push_back(&items[4]);

  theList.sort(MyClassCompare());
  for(it = theList.begin(); it != theList.end(); it++)
  {
      MyClass* n = *it;
      cout << n->x << endl;
  }
  cin.ignore();
  return 0;
}

---

This code gave me no errors when compiled with VC Net 2002.

BTW, the code to make it run in VC 6.0 is a hack -- it isn't strict conforming C++ code. To specialize on the greater<> template, you have to define your specialization in the std:: namespace. So this is actually an error, and you should refrain from using the VC 6.0 workaround for any other compiler or compiler version. Only use if for VC 6.0.

Regards,

Paul McKenzie