list::sort
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 10 of 10

Thread: list::sort

  1. #1
    Join Date
    Jun 2002
    Posts
    1,417

    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

  2. #2
    Join Date
    Aug 2002
    Location
    Madrid
    Posts
    4,588
    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())
    Get this small utility to do basic syntax highlighting in vBulletin forums (like Codeguru) easily.
    Supports C++ and VB out of the box, but can be configured for other languages.

  3. #3
    Join Date
    Jun 2002
    Posts
    1,417
    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;
    }

  4. #4
    Join Date
    Apr 1999
    Posts
    27,434
    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

  5. #5
    Join Date
    Jun 2002
    Posts
    1,417

    Smile

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

  6. #6
    Join Date
    Aug 2002
    Location
    Madrid
    Posts
    4,588
    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.
    Get this small utility to do basic syntax highlighting in vBulletin forums (like Codeguru) easily.
    Supports C++ and VB out of the box, but can be configured for other languages.

  7. #7
    Join Date
    Sep 2003
    Posts
    815
    I use VC .NET and has the same problem, I guess it is not fixed yet.

  8. #8
    Join Date
    Sep 2003
    Posts
    815
    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*>:perator ()(const CMyClass*,const CMyClass*) const' : cannot convert parameter 1 from 'std::allocator<_Ty>::value_type' to 'const CMyClass*'
    with
    [
    _Ty=CMyClass
    ]

  9. #9
    Join Date
    Apr 1999
    Posts
    27,434
    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

  10. #10
    Join Date
    Apr 1999
    Posts
    27,434
    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

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center