Thread: std::list<*> sorting

  1. #1
    Registered User
    Join Date
    Oct 2002
    Posts
    2

    Angry std::list<*> sorting

    please could some one explain to me how i implement sorting code for the following:

    #include <iostream>
    #include <list>

    void main(void)
    {
    list<int *> intPtrList;
    int a = 3, b = 7, c = 5;

    intPtrList.push_back(&a);
    intPtrList.push_back(&b);
    intPtrList.push_back(&c);

    intPtrList.sort(); // doesnt work (it will sort the pointers)
    }

    as you see in the code intPtrList.sort() wount work,
    but list has an overloded version of sort that takes an parameter
    but i dont under stand how to use it. so could some one tell me what that parameter should me to allow me to sort the data correct...

    \\dummy

  2. #2
    Registered User
    Join Date
    Nov 2001
    Posts
    1,348
    One solution is a predicate.

    Code:
    // Predicate dereferences the elements and compare them.
    std::sort(list.begin(), list.end, Predicate);
    
    // Ttry this solution.  I am not completely sure it works as it is a 
    // feature of the STL.
    
    std::sort(listl.begin(), list.end, std::greater<int *>());
    One solution for a predicate is a function object.

    Kuphryn

  3. #3
    Registered User
    Join Date
    Oct 2002
    Posts
    2

    Angry

    sorry, your solutions didnt work =(
    they didnt even compile =(

    .ziruz

  4. #4
    Registered User
    Join Date
    Nov 2001
    Posts
    1,348
    What is the error message?

    Add #include <algorithm>

  5. #5
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Here's the solution

    Code:
    bool myCompare(int* a, int* b)
    {
        return *a < *b;
    }
    
    
    int main()
    {
      //...
      myIntList.sort(myCompare);
      //...
    }
    Or perhaps more general:

    Code:
    template<typename T>
    class myPtrCompare
    {
        public:
        bool operator ()(T* a, T* b)
        {
            return *a < *b;
        }
    };
    
    int main()
    {
      //...
      myIntList.sort(myPtrCompare<int>());
      //...
    }
    Last edited by Sang-drax; 10-04-2002 at 11:26 AM.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  6. #6
    Registered User
    Join Date
    Oct 2002
    Posts
    30
    wrong thread
    Last edited by Jan79; 06-23-2003 at 10:59 AM.

  7. #7
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    Probably need to include <functional> in there to for kuphryn's (for greate<T>).
    The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.

  8. #8
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    You're using new-style headers, but you forgot about namespaces.

    >>void main(void)
    No. Bad. Very bad. Use int main( void ).
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  9. #9
    Registered User
    Join Date
    May 2003
    Posts
    1,619
    Originally posted by Sang-drax
    Here's the solution

    Code:
    bool myCompare(int* a, int* b)
    {
        return *a < *b;
    }
    
    
    int main()
    {
      //...
      myIntList.sort(myCompare);
      //...
    }
    That won't work without ptr_fun() around it; myCompare is not a functor here.

    The other code works much better, but a few changes to make it const-correct (you can get a lot of bizarre error messages if it's not):

    Code:
    template<typename T>
    class myPtrCompare
    {
        public:
        bool operator ()(const T* a, const T* b) const
        {
            return *a < *b;
        }
    };
    
    int main()
    {
      //...
      myIntList.sort(myPtrCompare<int>());
      //...
    }

  10. #10
    Registered User
    Join Date
    May 2003
    Posts
    148
    Originally posted by Cat
    That won't work without ptr_fun() around it; myCompare is not a functor here.
    No it is correct (try it).
    You only need to 'wrap' the pointer in ptr_fun,if you need binder (bind2nd for example).

  11. #11
    Registered User
    Join Date
    Jan 2003
    Posts
    311
    sorting a list is also painfully slow, If I may suggest vector and std::sort(begin,end,cmp) or a sorted container like set/multiset.

  12. #12
    Registered User
    Join Date
    May 2003
    Posts
    148
    Originally posted by grib
    sorting a list is also painfully slow,
    Why?
    Both sorts (list.sort and sort) run in O(n*log(n)).
    list.sort is a mergesort,and sort is introsort.

  13. #13
    Registered User
    Join Date
    Jun 2003
    Posts
    15
    Hmm... Maybe I am remembering incorrectly here, but doesn't the sort function not work on pointers?

    I was required to write 5 or 6 sort algorithms and we had to re-write the swap function (part of the sort function) to work with pointers.

    Of course, that was a while ago...
    /*When all else fails, Immortality can be achieved through Massive Failure*/

  14. #14
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    >> Hmm... Maybe I am remembering incorrectly here, but doesn't the sort function not work on pointers?

    It will work. If you are using pointers though, the default behavior of the sorting algorithms will be to compare the pointers (i.e. the memory addresses), and sort those, rather than sorting the data by value.

    >>you can get a lot of bizarre error messages if it's not

    I ran into some of those last week... They drove me insane for about half an hour.

    >>No it is correct (try it).

    Probably a default template argument.
    The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.

  15. #15
    Registered User
    Join Date
    Jun 2003
    Posts
    15
    It will work. If you are using pointers though, the default behavior of the sorting algorithms will be to compare the pointers (i.e. the memory addresses), and sort those, rather than sorting the data by value.
    Exactly. how does one fix that? Like I mentioned, we rewrote the swap function, but we also had to change the operator<

    - SB
    /*When all else fails, Immortality can be achieved through Massive Failure*/

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sorting algorithms, worst-case input
    By Leftos in forum C++ Programming
    Replies: 17
    Last Post: 06-15-2009, 01:33 PM
  2. Replies: 26
    Last Post: 06-11-2009, 11:27 AM
  3. Need help with linked list sorting function
    By Jaggid1x in forum C Programming
    Replies: 6
    Last Post: 06-02-2009, 02:14 AM
  4. sorting structure members using pointers
    By robstr12 in forum C Programming
    Replies: 5
    Last Post: 07-25-2005, 05:50 PM
  5. Still Needing Help : selection sorting
    By Unregistered in forum C Programming
    Replies: 6
    Last Post: 10-14-2001, 08:41 PM