c++ vector two sided sorting

Question

I have a vector with pairs of string and integer (count), I sorted everything according to count, but I have to sort also the strings if there are 2 or more repetitions in the list. For example;

3 trial 2 yummy 2 abc

So, there are 2 2's in the list, therefore abc must come before yummy. My code looks like this:

vector<pair<string, int> > values(hash_table.begin(), hash_table.end());

sort(values.begin(), values.end(), sort_reverse);


bool sort_reverse(const pair<string, int> &a, const pair<string, int> &b) {
  return a.second > b.second;
}

Answer 1

You can invert the sorting of any range by using a greater-than comparison instead of the default less-than:

std::sort(values.begin(), values.end(), std::greater<std::pair<string, int>>());

Alternatively, you can reverse the order of iteration:

std::sort(values.rbegin(), values.rend());

Edit If you want to change the comparison criteria to compare lexicographically by the pair's second first and it's first next, you can provide your own comparison function. It must still satisfy strict weak ordering as in the examples above. Lexicographical comparisons are trivial to implement with std::tie:

#include <tuple>

template<typename T1, typename T2>
struct pair_backwards_greater
{
  bool operator()(const std::pair<T1, T2>& lhs, const std::pair<T1, T2>& rhs) const
  {
    return std::tie(lhs.second, lhs.first) > std::tie(rhs.second, rhs.first);
  }
};

then

std::sort(values.begin(), values.end(), pair_backwards_greater<string, int>());

You also have the option of using a simple lambda expression instead of writing the functor by hand:

  std::sort(values.begin(), values.end(),
            [](const std::pair<std::string, int> &lhs, const std::pair<std::string, int> &rhs) 
            {
              return std::tie(lhs.second, lhs.first) > std::tie(rhs.second, rhs.first); 
            }  
           );

std::tie requires C++11 library support, but there are C++03 alternative implementations in boost::tie and std::tr1::tie. Lambda expressions require C++11 language support.

Answer 2

To sort on both fields in one hit:

bool sort_pair(const std::pair<std::string, int> &a, const std::pair<std::string, int> &b) 
{
    return (a.second > b.second) ||  
        ( 
            (a.second == b.second)  &&
            (a.first > b.first)
    );
}

void sortVector(std::vector<std::pair<std::string, int> >& values)
{
    std::sort(values.begin(), values.end(), sort_pair);
}

See also existing entry

Answer 3

you have to take the values itself into account.

bool sort_reverse(const pair<string, int> &a, const pair<string, int> &b) {
    return (a.second > b.second) || ((a.second == b.second) && (a.first > b.first));
}

Answer 4

I would like to propose an alternative, which is slightly different, and introduces the benefits of stable_sort.

typedef std::pair<int, std::string> CNP;

bool byName(CNP const& left, CNP const& right) { return left.second < right.second; }
bool byCount(CNP const& left, CNP const& right) { return left.first < right.first; }

std::sort(values.begin(), values.end(), byName);

std::stable_sort(values.begin(), values.end(), byCount);

This works because in case of equivalent elements (elements that compare equal) stable_sort preserve their relative order (which sort may, but does not guarantee).

Thus, imagining that you have [ (3, "apple"), (2, "zorro"), (2, "banana") ]:

• sort by name yields: [ (3, "apple"), (2, "banana"), (2, "zorro") ]
• stable sort by count: [ (2, "banana"), (2, "zorro"), (3, "apple") ]

It is of course more efficient to use a single sort with a more complicated predicate if you have no need for the intermediate step; however if you receive a list already sorted by name, then just applying the stable_sort by count might be faster.

Finally, a simple trick to check whether a list is sorted accorded to a criterion (or not):

template <typename C, typename P>
bool is_sorted(C const& list, P comp) {
    typedef typename C::const_reference CR;

    auto const reversed = [](CR left, CR right) { return comp(right, left);  };

    return std::adjacent_find(list.begin(), list.end(), reversed) == list.end();
}

Note: C++11 has a is_sorted method, though expressed in terms of iterators and not container of course.