Trier un vecteur de paires en C++

1. Utilisez l’algorithme std::sort pour trier le vecteur de paires par les valeurs du premier élément en C++
2. Utilisez l’algorithme std::sort avec l’expression lambda pour trier le vecteur de paires par valeurs de deuxième élément en C++
3. Utilisez l’algorithme std::sort avec une fonction personnalisée pour trier le vecteur de paires en C++

Cet article explique comment trier un vecteur de paires en C++.

Utilisez l’algorithme std::sort pour trier le vecteur de paires par les valeurs du premier élément en C++

Les paires sont fournies en tant que classe distincte dans la bibliothèque de modèles standard C++. Il implémente un type pour stocker deux objets hétérogènes en une seule unité. L’algorithme std::pair est essentiellement une structure de données de type tuple avec seulement deux éléments.

Un objet paire est déclaré avec deux paramètres de modèle qui spécifient le type de chaque élément. Nous pouvons déclarer un vecteur d’objets pair en plaçant la déclaration de paire en tant que paramètre de modèle vectoriel. Un vecteur de paires peut être initialisé avec une liste d’initialisation en passant chaque paire avec des accolades distinctes, comme illustré dans l’extrait de code suivant.

Nous pouvons trier le vecteur de paires en utilisant l’algorithme de tri générique fourni par STL. La fonction std::sort prend deux itérateurs de la plage à trier, et elle réarrange les éléments par défaut dans un ordre non décroissant. Dans le cas des paires, le vecteur est trié par le premier élément de chaque paire.

#include <iostream>
#include <vector>

using std::cin;
using std::cout;
using std::endl;
using std::pair;
using std::string;
using std::vector;

template <typename T>
void printVector(vector<T> &vec) {
  for (const auto &item : vec) {
    cout << "{" << item.first << "," << item.second << "}"
         << "; ";
  }
  cout << endl;
}

int main() {
  vector<pair<int, string>> vec1 = {
      {12, "eleven"}, {32, "thirty-two"}, {6, "six"}, {43, "forty-three"}};

  cout << "vec1: ";
  printVector(vec1);

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

  cout << "vec1: ";
  printVector(vec1);

  return EXIT_SUCCESS;
}

Production:

vec1 : {12, eleven};
{32, thirty - two};
{6, six};
{43, forty - three};
vec1 : {6, six};
{12, eleven};
{32, thirty - two};
{43, forty - three};

Utilisez l’algorithme std::sort avec l’expression lambda pour trier le vecteur de paires par valeurs de deuxième élément en C++

Alternativement, nous pouvons trier le vecteur de paires donné par les valeurs du deuxième élément si nous passons un objet de fonction de comparaison facultatif à l’algorithme std::sort. Dans ce cas, nous utilisons une expression lambda pour former un objet fonction et le transmettons comme troisième argument de l’appel de fonction sort. Notez qu’il s’agit essentiellement de la méthode pour définir toute routine de comparaison personnalisée pour les éléments de la paire.

#include <iostream>
#include <vector>

using std::cin;
using std::cout;
using std::endl;
using std::pair;
using std::string;
using std::vector;

template <typename T>
void printVector(vector<T> &vec) {
  for (const auto &item : vec) {
    cout << "{" << item.first << "," << item.second << "}"
         << "; ";
  }
  cout << endl;
}

int main() {
  vector<pair<int, string>> vec1 = {
      {12, "eleven"}, {32, "thirty-two"}, {6, "six"}, {43, "forty-three"}};

  cout << "vec1: ";
  printVector(vec1);

  std::sort(vec1.begin(), vec1.end(),
            [](const auto &x, const auto &y) { return x.second < y.second; });

  cout << "vec1: ";
  printVector(vec1);
  cout << endl;

  return EXIT_SUCCESS;
}

Production:

vec1 : {12, eleven};
{32, thirty - two};
{6, six};
{43, forty - three};
vec1 : {12, eleven};
{43, forty - three};
{6, six};
{32, thirty - two};

Utilisez l’algorithme std::sort avec une fonction personnalisée pour trier le vecteur de paires en C++

Une autre méthode pour passer une fonction de comparaison à l’algorithme std::sort consiste à définir une fonction distincte sous la forme de bool cmp(const Type1 &a, const Type2 &b). Généralement, std::sort a une complexité de temps d’exécution O(nlogn).

L’exemple suivant définit une fonction sortPairs qui compare les premiers éléments de chaque paire. Cependant, vous pouvez définir une fonction de comparaison plus complexe pour les paires qui stockent des objets de classe personnalisés ou lorsque plusieurs membres de données doivent être évalués.

#include <iostream>
#include <vector>

using std::cin;
using std::cout;
using std::endl;
using std::pair;
using std::string;
using std::vector;

template <typename T>
void printVector(vector<T> &vec) {
  for (const auto &item : vec) {
    cout << "{" << item.first << "," << item.second << "}"
         << "; ";
  }
  cout << endl;
}

bool sortPairs(const pair<int, string> &x, const pair<int, string> &y) {
  return x.first > y.first;
}

int main() {
  vector<pair<int, string>> vec1 = {
      {12, "eleven"}, {32, "thirty-two"}, {6, "six"}, {43, "forty-three"}};

  cout << "vec1: ";
  printVector(vec1);

  std::sort(vec1.begin(), vec1.end(), sortPairs);

  cout << "vec1: ";
  printVector(vec1);
  cout << endl;

  return EXIT_SUCCESS;
}

Production:

vec1 : {12, eleven};
{32, thirty - two};
{6, six};
{43, forty - three};
vec1 : {43, forty - three};
{32, thirty - two};
{12, eleven};
{6, six};