Is Std::Pair<Int, Std::String> Ordering Well-Defined

Is std::pair int, std::string ordering well-defined?

std::pair uses lexicographic comparison: It will compare based on the first element. If the values of the first elements are equal, it will then compare based on the second element.

The definition in the C++03 standard (section 20.2.2) is:

template <class T1, class T2>
bool operator<(const pair<T1, T2>& x, const pair<T1, T2>& y);

Returns: x.first < y.first || (!(y.first < x.first) && x.second < y.second).

Comparison function for sorting std::set std::pair int,std::pair int,int

Your comparison function is a good start. What is missing is "tie resolution". You need to specify what happens when l.second.second == r.second.second, and also what happens when l.second.first == r.second.first:

bool operator()(const myPair& l, const myPair& r)const{
    return (l.second.second < r.second.second) ||
           ((l.second.second == r.second.second) && (l.second.first < r.second.first)) ||
           ((l.second.second == r.second.second) && (l.second.first == r.second.first) && (l.first < r.first)).
}

• The first condition comes from your implementation.
• The second condition tells what to do when the first-priority items are equal to each other
• The third condition tells what to do when both the first-priority and the second-priority items are equal to each other.

In order to use this function for ordering your set, you need to pass it as the second template parameter to std::set. Here is a Q&A explaining how to do it.

What is wrong with my comparison function?

You haven't explained how you want to sort your triples, so all I can say is that your expectations are wrong.

Your comparison function considers your last three elements to be equal.

A triple (x0,x1,x2) is considered less than another triple (y0,y1,y2) if x0 < y0 and x1 < y1. For example, when comparing (6,4,7) and (6,5,4), neither triple is considered less than the other because the first number in each triple is the same (6 < 6 is false). Similarly, (5,4,6) is considered equal to (6,4,7) because neither is less than the other (4 < 4 is false).

The only thing you might reasonably expect is that (5,4,6) < (6,5,4), but your comparison function also says both of those are equal to (6,4,7). In other words, the function claims there are values a, b, c where a = b and b = c but a < c. This makes no sense, so your comparison function is broken.

If all you want is a lexicographical ordering, you don't need to do anything special:

std::sort(vec.begin(), vec.end());

std::pair sorts by its first component first; if those are equal, it compares the second components. That seems to be exactly the behavior you expect.

sorting a key-value pair according to values as well as keys

There is a similar question on HackerEarth This is how I solved it:

#include <algorithm>
#include <iostream> 
#include <vector>

int main() {
    std::vector<std::pair<std::string, long>> hotels;
    long n = 0;
    std::cin >> n;
    while (n--) {
        std::pair<std::string, long> hotel;
        std::cin >> hotel.first >> hotel.second;
        hotels.push_back(hotel);
    }
    std::sort(hotels.begin(), hotels.end(), [](std::pair<std::string, long> lhotel, std::pair<std::string, long> rhotel)->bool {
        if (lhotel.second > rhotel.second)
            return true;
        else if ((lhotel.second == rhotel.second) && (lhotel.first < rhotel.first))
            return true;
        return false;
    });
    std::cout << hotels.front().first;
    return 0;
}

In your solution, just use vector instead of set and all will be fine :)

Just for future references, if you want to deviate from the standard implementation of
any STL container in c++, always go for vectors instead. Never fails ;)

how to use std::pair as the key std::map

Yes, it is allowed.

std::pair already has an operator< which compares the two values in order, so you may not need to do anything special for a comparator at all.

std::pair with a comparable and a non-comparable object needs to be sorted

Your wrapper class should be similar to:

template <typename T>
struct Wrapper{
    Wrapper(const T & pair): pair_mem(pair) {}
    bool operator <(const Wrapper& rhs) const {
        return pair_mem.first < rhs.pair_mem.first;
    }
    T pair_mem;
};

Demo

But using custom comparer seems better (less intrusive).

std::sort(x.begin(), x.end(),
          [](const auto& lhs, const auto& rhs) {
              return lhs.first < rhs.first;
          });

---

Related Topics