CODEWITHSUNDEEP
c++sortingsetstd-pair
Rajdeep
Rajdeep

Reputation: 2462

C++ set sorting with pair as key

How will an ordered set container in c++ sort its keys if the key is a pair? (By default without a custom comparator)

Say I have a key of (1,2) and another key of (1,1).

Am I right to say that it will try to sort with respect to the first value in the pair then if they are equal proceed to compare the second pair value ?

So in this scenario (1,1) will be before (1,2).

Upvotes: 1

Views: 1946

Answers (2)

Vlad from Moscow
Vlad from Moscow

Reputation: 310990

The template class std::pair has already the defined operator <. So you can sort containers that contain objects of the type std::pair.

From the C++ Standard (20.3.3 Specialized algorithms)

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

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

Also you can consider two objects as members of an object of the type std::pair using function std::tie.

Here is a demonstrative program

#include <iostream>
#include <utility>
#include <functional>
#include <algorithm>
#include <iterator>

int main() 
{
    std::pair<int, int> a[] = { { 1, 2 }, { 1, 1 } };

    for ( const auto &p : a ) 
    {
        std::cout << "< " << p.first << ", " << p.second << "> ";
    }
    std::cout << std::endl;

    std::sort( std::begin( a ), std::end( a ) );

    for ( const auto &p : a ) 
    {
        std::cout << "< " << p.first << ", " << p.second << "> ";
    }
    std::cout << std::endl;

    std::cout << std::endl;

    struct Pair
    {
        int x;
        int y;
    } b[] = { { 1, 2 }, { 1, 1 } };

    for ( const auto &p : b ) 
    {
        std::cout << "< " << p.x << ", " << p.y << "> ";
    }
    std::cout << std::endl;

    std::sort( std::begin( b ), std::end( b ), 
        []( const Pair &left, const Pair &right)
        {
            return std::tie( left.x, left.y ) < std::tie( right.x, right.y );
        } );

    for ( const auto &p : b ) 
    {
        std::cout << "< " << p.x << ", " << p.y << "> ";
    }
    std::cout << std::endl;

    return 0;
}

Its output is

< 1, 2> < 1, 1> 
< 1, 1> < 1, 2> 

< 1, 2> < 1, 1> 
< 1, 1> < 1, 2>

Upvotes: 4

Ulrich Eckhardt
Ulrich Eckhardt

Reputation: 17415

You can customize the way the keys in set/map (and their multi variants) are sorted using a template parameter. This template parameter is not always given, because it has defaults. It is only required if there is not default sorting order or that order isn't right for the use case. However, this is also what you need to look at: It's the template parameter default and what that default means for pairs which determines how they are sorted.

Long story short, a lexical comparison is used, comparing the first and then the second element. Of course, this again used defaults, because the first half of a pair can be a pair itself etc.

Upvotes: 1

Related Questions