Sort vector of class in c++

Question

I am having some trouble with the sort function... here is my code:

class Parola {
public:
    string s;
    int repetition;
    bool operator()(const Parola *x, const Parola *y) {
        return x->repetition > y->repetition;
    }
};


int main(int argc, char** argv) {
    ...
    vector<Parola> p;
    ...
    some insertions here
    ...
    sort(p.begin(), p.end(), Parola());
    ...
    return 0;
}

Why I can't compile this without errors? Thanks a lot!

PS: I will show you only the first three lines of over fifty of errors:

/usr/include/c++/4.2.1/bits/stl_algo.h: In function 'const _Tp& std::__median(const _Tp&, const _Tp&, const _Tp&, _Compare) [with _Tp = Parola, _Compare = Parola]':
/usr/include/c++/4.2.1/bits/stl_algo.h:2795:   instantiated from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Parola*, std::vector<Parola, std::allocator<Parola> > >, _Size = long int, _Compare = Parola]'
/usr/include/c++/4.2.1/bits/stl_algo.h:2866:   instantiated from 'void std::sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Parola*, std::vector<Parola, std::allocator<Parola> > >, _Compare = Parola]'

Answer 1

Your immediate problem is that your comparison operator doesn't get passed Parola const* objects but Parola const& objects: the iterators get dereferenced to get a value which is actually compared.

The next problem is that you probably shouldn't try to bundle your comparison object into your actual objects: the comparison object doesn't really behave like a Parola object. You want to have a separate comparator which is then used with std::sort():

sturct ParolaCompare {
    bool operator()(Parola const& p0, Parola const& p1) const {
        // return something defining a strict weak order on Parola objects
    }
};
// ...
std::sort(v.begin(), v.end(), ParolaCompare());

Alternatively, you can define a suitable operator<() for your Parola objects:

bool operator< (Parola const& p0, Parola const& p1) {
    // again, a strict weak order on Parola objects
}

Answer 2

Giving the OP some options to choose from: (note: not exhaustive)

Option 1: Internal operator <()

class Parola {
public:
    string s;
    int repetition;
    bool operator<(const Parola& x) const  
    {
        return repetition < x.repetition;
    }
}

called using the default std::less<> template.

sort(p.begin(), p.end());

Option 2: Internal Functional operator()():

class Parola {
public:
    string s;
    int repetition;
    bool operator()(const Parola& x, const Parola& y) const  
    {
        return x.repetition < y.repetition;
    }
}

called with optional comparison object, as dasblinken pointed out, odd, but works:

std::sort(p.begin(), p.end(), Parola());

Option 3: External operator <()

bool operator <(const Parola& x, const Parola& y)
{
    x.repetition < y.repetition;
}

This, like (1), uses the default std::less<> comparator, but requires that the external operator also be a friend of class Parola to have access to the private data members if declared as such. Its use is the same as (1).

Option 4: External Functor

class CompareParola
{
public:
   bool operator ()(const Parola& x, const Parola& y) const
   {
      return x.repetition < right.repetition;
   }
};

And used by:

std::sort(p.begin(), p.end(), CompareParola());

Like (3), the CompareParola class must be friended to Parola if the members being accessed are private:

Option 5: External Function

bool ParolaLess(const Parola& x, const Parola& y)
{
    return x.repetition < y.repetition;
}

Similar to an external operator or external functional class, this also requires being friended to the object class to gain access to the private members. Invoked like such:

std::sort(p.begin(), p.end(), ParolaLess);

Option 6: Static Class Function

class Parola {
public:
    string s;
    int repetition;

    static bool Less(const Parola& x, const Parola& y)  
    {
        return x.repetition < y.repetition;
    }
};

This is often under-utilized, and has the very nice attribute of having access to all the object member variables, including private ones (obviously, its defined with the class). You can use this by doing:

std::sort(p.begin(), p.end(), Parola::Less)

Note that this, like (1) and (2), keeps everything in the class.

Of all of these I prefer (1) for its simplicity, and (4) for its independence, but everyone has their tastes. There are times that (5) or (6) really comes in handy (and I'm a personal fan of (6)).

If you can think of any more and have the rep to edit it, kindly update this as needed. Please do try to make them at least somewhat useful =P

Answer 3

Your comparator takes pointers, but the vector holds Parola instances. You need to change that. But the easiest would be to implement a less-than comparison operator.

class Parola {
public:
    string s;
    int repetition;
};

bool operator<(const Parola& x, const Parola& y) {
    return x.repetition < y.repetition;
}

Then you can call sort without a 3rd argument:

sort(p.begin(), p.end());

Answer 4

Make the operator take const references instead of pointers. I.e.

bool operator()(const Parola &x, const Parola &y) { 
    return x.repetition > y.repetition; 
}

Answer 5

Generally when-ever you have an object that you want the STL to sort for you, either using the sort method, or putting it in a std::set, you need a operator< method.

Hence it's best to make it a member of the class. The signature of that method should be something like: bool operator<(const Parola& left, const Parola& right)

How you implement it is dependent on your class itself.