Sort a vector c++

Question

I am trying to sort a 2D vector with the type:

vector<pair<char, double>> output;

I am trying to arrange them from the highest to lowest double value and only displaying the top 5. This is what I am trying to do:

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

But this sort is not working properly for me. What am I doing wrong?

Another possibility...swap the char-double pair with a double-char pair, and then directly sort it..extra +O(N) time which is irrelevant because sorting is O(NlogN) and extra O(N) memory...if you can afford it. — , Nov 28 '17 at 00:36

juanchopanza · Accepted Answer · 2013-10-08T20:03:46.010

3

By default, std::sort will use the less-than comparison operator for the elements of the container, which will perform am lexicographical comparison using the char first and then the double.

You can use your own ordering function/functor that orders based on the pair's double element only:

bool cmp(const std::pair<char, double>& lhs, 
         const std::pair<char, double>& rhs)
{
  return lhs.second > rhs.second;
}

then

std::vector<std::pair<char, double>> output = ....;
sort(output.begin(), output.end(), cmp);

See working demo here.

edited Oct 08 '13 at 20:03

answered Oct 08 '13 at 19:39

juanchopanza

223,364
34
402
480

Error 1 error C3867: 'CaesarCypher::cmp': function call missing argument list; use '&CaesarCypher::cmp' to create a pointer to member – user977154 Oct 08 '13 at 19:45
@user977154 you're doing something wrong! The `cmp` function is a non-member function. – juanchopanza Oct 08 '13 at 19:46
Error 2 error C2780: 'void std::sort(_RanIt,_RanIt)' : expects 2 arguments - 3 provided – user977154 Oct 08 '13 at 19:47
Even after making it a non member function it does not compile – user977154 Oct 08 '13 at 19:49
@user977154 Either you are doing something else wrong, or your std library installation is broken. See [this compiling demo](http://ideone.com/6lTwAR). – juanchopanza Oct 08 '13 at 19:51
Thank you, I will look around for errors in my code. – user977154 Oct 08 '13 at 20:05

David G · Answer 2 · 2013-10-08T19:53:41.797

2

As Violet said, you may want to include your own comparison function:

class compare
{
public:
    bool operator() (std::pair<char, int> const& p1,
                    std::pair<char, int> const& p2) const
    {
        // perform logic here
    }
} Predicate;

std::sort uses operator < to compare the elements, and sorts them accordingly. It has an extra optional parameter for the comparsion functor, which we can include like this:

std::sort(output.begin(), output.end(), Predicate);

Note that this can also be done using a lambda in C++11.

edited Oct 08 '13 at 19:53

answered Oct 08 '13 at 19:41

David G

94,763
41
167
253

I'm not sure, but the comparator has not to be a thing (function, lambda, functor) with signature `bool(const value_type& , const value_type&)`? I think you should write `operator()` instead of `operator<` – Manu343726 Oct 08 '13 at 19:50
@Manu343726 That is exactly what this is. `std::sort` will call `compare::operator <` internally. – David G Oct 08 '13 at 19:52
mmmm no, is not a callable object, you have defined comparison operator only. – Manu343726 Oct 08 '13 at 19:53

score 0 · Answer 3 · edited Oct 16 '13 at 11:20

0

You need to write a comparison operator between the pair<char, double> operands. http://en.cppreference.com/w/cpp/algorithm/sort

edited Oct 16 '13 at 11:20

answered Oct 08 '13 at 19:39

Vadiklk

3,696
5
28
44

score 0 · Answer 4 · answered Oct 08 '13 at 19:43

Is there a reason you're using a vector of pairs? In other words, does the order in which the elements are stored internally really matter to you? If not, you're probably better off using a map<double,char> with a reverse iterator to get the last 5 elements sorted by double value.

Sort a vector c++

4 Answers4