C++
std :: set et std :: multiset

Introduction

Remarques

Insérer des valeurs dans un ensemble

Trois méthodes d’insertion différentes peuvent être utilisées avec les ensembles.

• Tout d'abord, une simple insertion de la valeur. Cette méthode renvoie une paire permettant à l'appelant de vérifier si l'insertion s'est réellement produite.
• Deuxièmement, un insert en donnant une indication de l'endroit où la valeur sera insérée. L'objectif est d'optimiser le temps d'insertion dans un tel cas, mais il n'est pas courant de savoir où une valeur doit être insérée. Soyez prudent dans ce cas; la manière de donner un indice diffère avec les versions du compilateur .
• Enfin, vous pouvez insérer une plage de valeurs en donnant un pointeur de début et de fin. Le premier sera inclus dans l'insertion, le dernier est exclu.

#include <iostream>
#include <set>

int main ()
{
  std::set<int> sut;
  std::set<int>::iterator it;
  std::pair<std::set<int>::iterator,bool> ret;

  // Basic insert
  sut.insert(7);
  sut.insert(5);
  sut.insert(12);
  
  ret = sut.insert(23);
  if (ret.second==true)
    std::cout << "# 23 has been inserted!" << std::endl;
    
  ret = sut.insert(23); // since it's a set and 23 is already present in it, this insert should fail
  if (ret.second==false)
    std::cout << "# 23 already present in set!" << std::endl;
 
  // Insert with hint for optimization
  it = sut.end();
  // This case is optimized for C++11 and above
  // For earlier version, point to the element preceding your insertion
  sut.insert(it, 30); 

  // inserting a range of values
  std::set<int> sut2;
  sut2.insert(20);
  sut2.insert(30);
  sut2.insert(45);
  std::set<int>::iterator itStart = sut2.begin();
  std::set<int>::iterator itEnd = sut2.end();
  
  sut.insert (itStart, itEnd); // second iterator is excluded from insertion

  std::cout << std::endl << "Set under test contains:" << std::endl;
  for (it = sut.begin(); it != sut.end(); ++it)
  {
    std::cout << *it << std::endl;
  }

  return 0;
}

La sortie sera:

# 23 has been inserted!                                                                                                                                                                                                                                                                                                   
# 23 already present in set!                                                                                                                                                                                                                                                                                              
                                                                                                                                                                                                                                                                                                                          
Set under test contains:                                                                                                                                                                                                                                                                                                  
5                                                                                                                                                                                                                                                                                                                         
7                                                                                                                                                                                                                                                                                                                         
12                                                                                                                                                                                                                                                                                                                        
20                                                                                                                                                                                                                                                                                                                        
23                                                                                                                                                                                                                                                                                                                        
30                                                                                                                                                                                                                                                                                                                        
45   

Insertion de valeurs dans un multiset

Toutes les méthodes d'insertion des ensembles s'appliquent également aux multisets. Néanmoins, il existe une autre possibilité, qui fournit une initializer_list:

auto il = { 7, 5, 12 };
std::multiset<int> msut;
msut.insert(il);

Changer le type de jeu par défaut

set et multiset ont des méthodes de comparaison par défaut, mais dans certains cas, vous devrez peut-être les surcharger.

Imaginons que nous stockions des valeurs de chaîne dans un ensemble, mais nous savons que ces chaînes ne contiennent que des valeurs numériques. Par défaut, le tri sera une comparaison de chaîne lexicographique, donc l'ordre ne correspondra pas au tri numérique. Si vous voulez appliquer une sorte équivalente à ce que vous auriez avec les valeurs int , vous avez besoin d'un foncteur pour surcharger la méthode de comparaison:

#include <iostream>
#include <set>
#include <stdlib.h> 

struct custom_compare final
{
    bool operator() (const std::string& left, const std::string& right) const
    {
        int nLeft = atoi(left.c_str());
        int nRight = atoi(right.c_str());
        return nLeft < nRight;
    }
};

int main ()
{
    std::set<std::string> sut({"1", "2", "5", "23", "6", "290"});
  
    std::cout << "### Default sort on std::set<std::string> :" << std::endl;
    for (auto &&data: sut)
        std::cout << data << std::endl;
  
    std::set<std::string, custom_compare> sut_custom({"1", "2", "5", "23", "6", "290"},
                                                     custom_compare{}); //< Compare object optional as its default constructible.
  
    std::cout << std::endl << "### Custom sort on set :" << std::endl;
    for (auto &&data : sut_custom)
        std::cout << data << std::endl;
  
    auto compare_via_lambda = [](auto &&lhs, auto &&rhs){ return lhs > rhs; };
    using set_via_lambda = std::set<std::string, decltype(compare_via_lambda)>;
    set_via_lambda sut_reverse_via_lambda({"1", "2", "5", "23", "6", "290"},
                                          compare_via_lambda);
  
    std::cout << std::endl << "### Lambda sort on set :" << std::endl;
    for (auto &&data : sut_reverse_via_lambda)
        std::cout << data << std::endl;

    return 0;
}

La sortie sera:

### Default sort on std::set<std::string> :
1
2
23
290
5
6
### Custom sort on set :
1
2
5
6
23
290  

### Lambda sort on set :
6
5
290
23
2
1

Dans l'exemple ci-dessus, on peut trouver 3 manières différentes d'ajouter des opérations de comparaison à std::set , chacune étant utile dans son propre contexte.

Tri par défaut

Cela utilisera l'opérateur compare de la clé (premier argument du modèle). Souvent, la clé fournira déjà une bonne valeur par défaut pour la fonction std::less<T> . A moins que cette fonction soit spécialisée, elle utilise l' operator< de l'objet. Ceci est particulièrement utile lorsque d'autres codes essaient également d'utiliser un certain ordre, car cela permet une cohérence sur toute la base de code.

En écrivant le code de cette façon, vous réduirez les efforts de mise à jour de votre code lorsque les modifications clés sont des API, comme par exemple: une classe contenant 2 membres qui devient une classe contenant 3 membres. En mettant à jour l' operator< dans la classe, toutes les occurrences seront mises à jour.

Comme vous vous en doutez, utiliser le tri par défaut est une valeur par défaut raisonnable.

Tri personnalisé

L'ajout d'un tri personnalisé via un objet avec un opérateur de comparaison est souvent utilisé lorsque la comparaison par défaut n'est pas conforme. Dans l'exemple ci-dessus, c'est parce que les chaînes font référence à des entiers. Dans d'autres cas, il est souvent utilisé lorsque vous souhaitez comparer des pointeurs (intelligents) basés sur l'objet auquel ils se réfèrent ou parce que vous avez besoin de contraintes différentes pour comparer (exemple: comparer std::pair à la valeur du first ).

Lors de la création d'un opérateur de comparaison, cela devrait être un tri stable. Si le résultat de l'opérateur de comparaison change après l'insertion, vous aurez un comportement indéfini. Comme bonne pratique, votre opérateur de comparaison ne doit utiliser que les données constantes (membres const, fonctions const ...).

Comme dans l'exemple ci-dessus, vous rencontrerez souvent des classes sans membres en tant qu'opérateurs de comparaison. Cela se traduit par des constructeurs par défaut et des constructeurs de copie. Le constructeur par défaut vous permet d'omettre l'instance au moment de la construction et le constructeur de la copie est requis car l'ensemble prend une copie de l'opérateur de comparaison.

Type Lambda

Les Lambdas sont un moyen plus court d'écrire des objets de fonction. Cela permet d'écrire l'opérateur de comparaison sur moins de lignes, ce qui rend le code global plus lisible.

L'inconvénient de l'utilisation de lambdas est que chaque lambda obtient un type spécifique au moment de la compilation, de sorte que decltype(lambda) sera différent pour chaque compilation de la même unité de compilation (fichier cpp) que sur plusieurs unités de compilation ). Pour cette raison, il est recommandé d'utiliser des objets de fonction comme opérateur de comparaison lorsqu'ils sont utilisés dans des fichiers d'en-tête.

Cette construction est souvent rencontrée lorsqu'un objet std::set est utilisé dans la portée locale d'une fonction, tandis que l'objet fonction est préféré lorsqu'il est utilisé comme argument de fonction ou membre de classe.

Autres options de tri

Comme l'opérateur de comparaison de std::set est un argument de modèle, tous les objets appelables peuvent être utilisés en tant qu'opérateur de comparaison et les exemples ci-dessus ne sont que des cas spécifiques. Les seules restrictions de ces objets appelables sont les suivantes:

• Ils doivent être constructibles
• Ils doivent pouvoir être appelés avec 2 arguments du type de la clé. (les conversions implicites sont autorisées, mais pas recommandées car elles peuvent nuire aux performances)

Recherche de valeurs dans set et multiset

Il existe plusieurs manières de rechercher une valeur donnée dans std::set ou dans std::multiset :

Pour obtenir l'itérateur de la première occurrence d'une clé, la fonction find() peut être utilisée. Il retourne end() si la clé n'existe pas.

  std::set<int> sut;
  sut.insert(10);
  sut.insert(15);
  sut.insert(22);
  sut.insert(3); // contains 3, 10, 15, 22    

  auto itS = sut.find(10); // the value is found, so *itS == 10
  itS = sut.find(555); // the value is not found, so itS == sut.end()   

  std::multiset<int> msut;
  sut.insert(10);
  sut.insert(15);
  sut.insert(22);
  sut.insert(15);
  sut.insert(3); // contains 3, 10, 15, 15, 22  

  auto itMS = msut.find(10);

Une autre méthode consiste à utiliser la fonction count() , qui compte combien de valeurs correspondantes ont été trouvées dans set / multiset (dans le cas d'un set , la valeur de retour peut être seulement 0 ou 1). En utilisant les mêmes valeurs que ci-dessus, nous aurons:

int result = sut.count(10); // result == 1
result = sut.count(555); // result == 0

result = msut.count(10); // result == 1
result = msut.count(15); // result == 2

Dans le cas de std::multiset , il pourrait y avoir plusieurs éléments ayant la même valeur. Pour obtenir cette plage, la fonction equal_range() peut être utilisée. Il renvoie std::pair ayant la borne inférieure de l'itérateur (inclus) et la limite supérieure (exclusive) respectivement. Si la clé n'existe pas, les deux itérateurs indiqueraient la valeur supérieure la plus proche (selon la méthode de comparaison utilisée pour trier le multiset donné).

auto eqr = msut.equal_range(15);
auto st = eqr.first; // point to first element '15'
auto en = eqr.second; // point to element '22'

eqr = msut.equal_range(9); // both eqr.first and eqr.second point to element '10'

Suppression de valeurs d'un ensemble

La méthode la plus évidente, si vous voulez simplement réinitialiser votre set / multiset à un ensemble vide, consiste à utiliser clear :

  std::set<int> sut;
  sut.insert(10);
  sut.insert(15);
  sut.insert(22);
  sut.insert(3); 
  sut.clear(); //size of sut is 0

Ensuite, la méthode d' erase peut être utilisée. Il offre des possibilités qui ressemblent quelque peu à l’insertion:

std::set<int> sut;
std::set<int>::iterator it;
          
sut.insert(10);
sut.insert(15);
sut.insert(22);
sut.insert(3); 
sut.insert(30);
sut.insert(33);
sut.insert(45);
    
// Basic deletion
sut.erase(3);
    
// Using iterator
it = sut.find(22);
sut.erase(it);
          
// Deleting a range of values
it = sut.find(33);
sut.erase(it, sut.end());
    
std::cout << std::endl << "Set under test contains:" << std::endl;
for (it = sut.begin(); it != sut.end(); ++it)
{
  std::cout << *it << std::endl;
}

La sortie sera:

Set under test contains:                                                                                                                                                                                                                                                                                                  
10                                                                                                                                                                                                                                                                                                                        
15                                                                                                                                                                                                                                                                                                                        
30 

Toutes ces méthodes s'appliquent également au multiset . Veuillez noter que si vous demandez de supprimer un élément d'un multiset , et qu'il est présent plusieurs fois, toutes les valeurs équivalentes seront supprimées .