CKTIS / C++
std::multiset — un conteneur ordonné avec des doublons
std::multiset, défini dans <set>, stocke les clés dans l’ordre établi par le comparateur et autorise les clés équivalentes. Découvrez comment fonctionnent la recherche et le comptage, et distinguez la suppression d’un élément de celle de tous les éléments équivalents.
Version : C++23; repository compiler flag, production runtime not attested
Syntaxe
#include <set>
std::multiset<Key, Compare, Allocator> values;
// Defaults: Compare = std::less<Key>, Allocator = std::allocator<Key>std::multiset<Key, Compare, Allocator> de <set> est un conteneur associatif ordonné : chaque élément est lui-même une clé. Contrairement à std::set, il autorise plusieurs clés équivalentes. Le std::less<Key> par défaut donne un ordre croissant pour les nombres ; l’itération suit l’ordre du comparateur.
Compare doit définir un ordre strict faible. Les clés a et b sont équivalentes lorsque !comp(a, b) && !comp(b, a), ce qui ne signifie pas nécessairement a == b. Il est impossible de modifier les éléments au moyen d’itérateurs. Pour changer une clé, on peut supprimer l’élément puis en insérer un nouveau. Les itérateurs sont bidirectionnels, et non à accès aléatoire.
Pour N éléments, une insertion ordinaire ainsi que find, lower_bound et upper_bound ont une complexité en O(log N). find renvoie un élément correspondant ou end() ; count compte tous les éléments équivalents et equal_range détermine leur plage [first, last). Le comptage coûte O(log N + K), où K est le nombre de correspondances.
Attention : erase(key) supprime tous les éléments équivalents et renvoie leur nombre. erase(it) ne supprime que l’élément indiqué ; passer end() est invalide. L’insertion n’invalide ni les itérateurs ni les références, tandis que la suppression n’invalide que ceux qui désignent les éléments supprimés.
L’exemple est destiné à être compilé avec -std=c++23 ; son comportement à l’exécution en production n’est pas attesté. La source est un projet de norme en évolution, et non une publication C++23 figée ; cette entrée n’applique pas à C++23 ses déclarations constexpr plus récentes.
Exemples
#include <iostream>
#include <set>
int main() {
std::multiset<int> values{3, 1, 3, 2};
values.insert(3);
std::cout << "count: " << values.count(3) << '\n';
auto it = values.find(3);
if (it != values.end()) {
values.erase(it);
}
std::cout << "after one: " << values.count(3) << '\n';
auto removed = values.erase(3);
std::cout << "removed: " << removed << '\n';
std::cout << "remaining:";
for (int value : values) {
std::cout << ' ' << value;
}
std::cout << '\n';
}
Résultat
count: 3 after one: 2 removed: 2 remaining: 1 2
Le code affiché et le résultat déclaré ont été vérifiés dans un environnement isolé selon la méthode consignée dans la preuve de vérification de cette version exacte.