Algorithm and sort

This is a discussion on Algorithm and sort within the C++ Programming forums, part of the General Programming Boards category; Hi. I have a vector with pointers to objects (vector<X*> ) that I would like to sort. How can I ...

  1. #1
    Registered User
    Join Date
    Jul 2005
    Posts
    14

    Algorithm and sort

    Hi.
    I have a vector with pointers to objects (vector<X*> ) that I would like to sort.
    How can I do that with the sort that is in the STL algorithm package?

    vector<X*> v;
    sort(v.begin(),v.end(), .....)

    but I'm not sure how I write the comparison function.
    How do I do that?

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,650
    Something like this might work:
    Code:
    bool compareX(const X* a, const X* b) {
    	return *a < *b;
    }
    
    // ...
    vector<X*> v;
    sort(v.begin(), v.end(), compareX);
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,799
    Assuming you've got the less-than operator (<) defined for your X objects, then it would be this...
    Code:
    class my_sort
    {
    public:
        inline bool operator()(const X* lhs,const X* rhs)
        {
            return *lhs < *rhs;
        }
    };
    
    ...
    
    sort(v.begin(),v.end(),my_sort());
    That should sort them in ascending order.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  4. #4
    Registered User
    Join Date
    Jul 2005
    Posts
    14
    Is it not possible to do without the extra class?

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,650
    Is it not possible to do without the extra class?
    Yes, if you use my version, which uses a function pointer instead. A function object is better (e.g. more flexible) in some cases, especially if it inherits from std::unary_function or std::binary_function. I am not too sure of this myself, but compilers may decide to inline the comparison made via a function object, and may be less likely to do so for a function pointer.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    Registered User
    Join Date
    Jul 2005
    Posts
    14
    Does your version also work if the class X is abstract?

    It turns out that X is abstract and that the values of two X objects are calculated by the function
    Code:
    class X{
       virtual int value()=0;
    };
    that then should be implemented in a subclass.

    so your compare function should change to
    return a->value() < b->value()



    Will this work? I'm getting the error
    passing `const X' as `this' argument of `virtual
    int X::value()' discards qualifiers

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,650
    If X::value() does not logically modify the state of X, then it should be a const member function.
    Code:
    class X{
       virtual int value() const = 0;
    };
    Alternatively, you can make bool operator< a friend function, and then implement the concept of "less than" as pertains to X.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #8
    Registered User
    Join Date
    Jul 2005
    Posts
    14
    Ah, great, it worked. Very big thank you!

  9. #9
    Registered User
    Join Date
    Jul 2005
    Posts
    14
    Btw, can I skip the const? Even if it's better to have itperhaps.

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,650
    Btw, can I skip the const? Even if it's better to have itperhaps.
    Yes, though I would be disturbed if the expression (a < b) modified the state of a or b.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. JavaScript like sort algorithm?
    By audinue in forum C Programming
    Replies: 2
    Last Post: 07-28-2008, 12:27 AM
  2. help with debug (bubble sort algorithm)
    By lbraglia in forum C Programming
    Replies: 5
    Last Post: 10-19-2007, 05:24 PM
  3. choosing right sort algorithm
    By Micko in forum C++ Programming
    Replies: 15
    Last Post: 05-29-2006, 10:38 AM
  4. Replies: 2
    Last Post: 05-06-2003, 08:34 AM
  5. Sort algorithm and an ugly error
    By Trauts in forum C++ Programming
    Replies: 7
    Last Post: 02-25-2003, 11:36 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21