How to Sort a List of Pairs in C++? - Coding

In C++, the pair container allows the users to store two different types of objects as a single unit. We can store the pairs in a list if we want to store multiple pairs in a single place. Lists are sequence containers that allow non-contiguous memory allocation. In this article, we will learn how to sort a list of pairs in different orders in our C++ program.

For Example,

Input:
list<pair<int,int>> l ={{200,2},{300,3},{100,1}}
Output: 
list<pair<int,int>> l ={{100,1},{200,2},{300,3}}

Sort List of Pairs in C++

We can use the std::list::sort() function to sort the list but for a list of pairs, we will have to provide a custom comparator function (can be a lambda expression) to compare the elements of each pair with others.

Note: We cannot use the global std::sort() function for lists as they require random access iterators while we can only have sequential access iterator for list containers.

C++ Program to Sort List of Pairs in Ascending Order

C++

// C++ program to illustrate how to sort the list of pairs 
// in c++ using list::sort and lambda expression 
#include <bits/stdc++.h> 
using namespace std; 
  
// driver code 
int main() 
{ 
    // creating a list of pairs 
    list<pair<int, int> > li = { 
        { 300, 1 }, { 200, 2 }, { 100, 3 }, { 400, 4 } 
    }; 
  
    cout << "List Initially " << endl; 
    for (auto i : li) { 
        cout << "( " << i.first << ", " << i.second << " )"
             << endl; 
    } 
  
    /// sorting by providing the custom comparator in the 
    /// form of lamda expression 
    li.sort([](const auto& a, const auto& b) { 
        return a.first 
               < b.first; // use > for descending order 
    }); 
  
    // Print the sorted list of pairs 
    cout << endl << "List After Sorting: " << endl; 
    for (auto i : li) { 
        cout << "( " << i.first << ", " << i.second << " )"
             << endl; 
    } 
  
    return 0; 
}

Output

List Initially 
( 300, 1 )
( 200, 2 )
( 100, 3 )
( 400, 4 )

List After Sorting: 
( 100, 3 )
( 200, 2 )
( 300, 1 )
( 400, 4 )

In the above program, we have sorted the list according to the value of the first element of the pair. We can also sort the list based on the value of the second element.

Time Complexity: O(N logN), where N is the size of the List.
Auxiliary Space: O(1), since no extra space is used to sort the elements.

C++ Program to Sort the List of Pairs According to the Second Element

C++

// C++ program to illustrate how to sort the list of pairs 
// based on the value of the second element of the pair 
#include <bits/stdc++.h> 
using namespace std; 
  
int main() 
{ 
    // creating list of pairs 
    list<pair<int, int> > li = { 
        { 300, 3 }, { 200, 2 }, { 100, 1 }, { 400, 4 } 
    }; 
  
    cout << "List Initially " << endl; 
    for (auto i : li) { 
        cout << "( " << i.first << ", " << i.second << " )"
             << endl; 
    } 
  
    // Sorting the list  based on the secondelement of each 
    // pair 
    li.sort([](auto& a, auto& b) { 
        return a.second > b.second; 
    }); 
  
    // Print the sorted list of pairs 
    cout << endl << "List After Sorting: " << endl; 
    for (auto i : li) { 
        cout << "( " << i.first << ", " << i.second << " )"
             << endl; 
    } 
  
    return 0; 
}

Output

List Initially 
( 300, 3 )
( 200, 2 )
( 100, 1 )
( 400, 4 )

List After Sorting: 
( 400, 4 )
( 300, 3 )
( 200, 2 )
( 100, 1 )

The above program sorts the list based on the value of the second element of the pair. It also sorts the list in the descending order. We can actually sort the list in any order we want by providing a comparator function of our choice.

Time Complexity: O(N logN), where N is the size of the List.
Auxiliary Space: O(1), since no extra space is used to sort the elements.

Reffered: https://www.geeksforgeeks.org

C++

Related
How to Convert Map to a Vector of Pairs in C++?
Command Line Arguments in C++
When Do We Pass Arguments by Reference or Pointer in C++?
void Pointer in C++
NULL Pointer in C++

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	12