C++
std :: set e std :: multiset
Ricerca…
introduzione
set è un tipo di contenitore i cui elementi sono ordinati e unici. multiset è simile, ma, nel caso del multiset , più elementi possono avere lo stesso valore.
Osservazioni
In questi esempi sono stati usati diversi stili di C ++. Fai attenzione se stai usando un compilatore C ++ 98; parte di questo codice potrebbe non essere utilizzabile.
Inserimento di valori in un set
Tre diversi metodi di inserimento possono essere usati con i set.
- Innanzitutto, un semplice inserimento del valore. Questo metodo restituisce una coppia che consente al chiamante di verificare se l'inserimento è realmente avvenuto.
- Secondo, un inserto dando un suggerimento su dove verrà inserito il valore. L'obiettivo è ottimizzare il tempo di inserimento in questo caso, ma sapere dove un valore deve essere inserito non è il caso comune. Stai attento in quel caso; il modo di dare un suggerimento è diverso con le versioni del compilatore .
- Infine puoi inserire un intervallo di valori dando un puntatore iniziale e finale. L'iniziale sarà incluso nell'inserimento, quello finale è escluso.
#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;
}
L'output sarà:
# 23 has been inserted!
# 23 already present in set!
Set under test contains:
5
7
12
20
23
30
45
Inserimento di valori in un multiset
Tutti i metodi di inserimento dei set si applicano anche ai multiset. Tuttavia, esiste un'altra possibilità che fornisce una lista_inizializzazione:
auto il = { 7, 5, 12 };
std::multiset<int> msut;
msut.insert(il);
Modifica l'ordinamento predefinito di un set
set e multiset hanno metodi di confronto predefiniti, ma in alcuni casi potrebbe essere necessario sovraccaricarli.
Immaginiamo di memorizzare i valori stringa in un set, ma sappiamo che queste string contengono solo valori numerici. Di default l'ordinamento sarà un confronto di stringhe lessicografiche, quindi l'ordine non corrisponderà all'ordinamento numerico. Se vuoi applicare un ordinamento equivalente a quello che avresti con i valori int , hai bisogno di un functor per sovraccaricare il metodo di confronto:
#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;
}
L'output sarà:
### 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
Nell'esempio sopra, si possono trovare 3 diversi modi di aggiungere operazioni di confronto a std::set , ognuno di essi è utile nel proprio contesto.
Ordinamento predefinito
Questo utilizzerà l'operatore di confronto della chiave (primo argomento del modello). Spesso, la chiave fornirà già un buon valore predefinito per la funzione std::less<T> . A meno che questa funzione non sia specializzata, utilizza l' operator< dell'oggetto. Ciò è particolarmente utile quando un altro codice tenta anche di utilizzare alcuni ordini, poiché ciò consente la coerenza su tutto il codice base.
Scrivere il codice in questo modo ridurrà lo sforzo di aggiornare il codice quando la chiave cambia API, come: una classe contenente 2 membri che cambia in una classe contenente 3 membri. Aggiornando l' operator< nella classe, tutte le occorrenze verranno aggiornate.
Come ci si potrebbe aspettare, l'uso dell'ordinamento predefinito è un valore predefinito ragionevole.
Ordinamento personalizzato
L'aggiunta di un ordinamento personalizzato tramite un oggetto con un operatore di confronto viene spesso utilizzata quando il confronto predefinito non è conforme. Nell'esempio sopra questo è perché le stringhe si riferiscono a numeri interi. In altri casi, viene spesso utilizzato quando si desidera confrontare i puntatori (intelligenti) in base all'oggetto cui si riferiscono o perché sono necessari diversi vincoli per il confronto (esempio: confronto di std::pair con il valore di first ).
Quando si crea un operatore di confronto, questo dovrebbe essere un ordinamento stabile. Se il risultato dell'operatore di confronto cambia dopo l'inserimento, si avrà un comportamento indefinito. Come buona pratica, l'operatore di confronto dovrebbe utilizzare solo i dati costanti (membri const, funzioni const ...).
Come nell'esempio sopra, spesso incontrerai le classi senza membri come operatori di confronto. Ciò si traduce in costruttori e costruttori di copia predefiniti. Il costruttore predefinito consente di omettere l'istanza in fase di costruzione e il costruttore della copia è richiesto poiché il set accetta una copia dell'operatore di confronto.
Lambda sort
Lambdas è un modo più breve per scrivere oggetti funzione. Ciò consente di scrivere l'operatore di confronto su meno righe, rendendo più leggibile il codice generale.
Lo svantaggio dell'uso di lambda è che ogni lambda ottiene un tipo specifico in fase di compilazione, quindi decltype(lambda) sarà diverso per ogni compilazione della stessa unità di compilazione (file cpp) come su più unità di compilazione (se inclusa tramite file di intestazione ). Per questo motivo, è consigliabile utilizzare gli oggetti funzione come operatore di confronto se utilizzato all'interno dei file di intestazione.
Questa costruzione si incontra spesso quando un oggetto std::set viene usato all'interno dell'ambito locale di una funzione, mentre l'oggetto funzione è preferito quando viene usato come argomenti di funzione o membri di classe.
Altre opzioni di ordinamento
Poiché l'operatore di confronto di std::set è un argomento modello, tutti gli oggetti chiamabili possono essere utilizzati come operatori di confronto e gli esempi sopra riportati sono solo casi specifici. Le uniche restrizioni che hanno questi oggetti callable sono:
- Devono essere copiabili costruibili
- Devono essere chiamabili con 2 argomenti del tipo di chiave. (le conversioni implicite sono consentite, sebbene non raccomandate in quanto possono danneggiare le prestazioni)
Ricerca di valori in set e multiset
Esistono diversi modi per cercare un determinato valore in std::set o in std::multiset :
Per ottenere l'iteratore della prima occorrenza di una chiave, è possibile utilizzare la funzione find() . Restituisce end() se la chiave non esiste.
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);
Un altro modo è usare la funzione count() , che conta quanti valori corrispondenti sono stati trovati nel set / multiset (nel caso di un set , il valore di ritorno può essere solo 0 o 1). Usando gli stessi valori di cui sopra, avremo:
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
Nel caso di std::multiset , potrebbero esserci più elementi con lo stesso valore. Per ottenere questo intervallo, è possibile utilizzare la funzione equal_range() . Restituisce std::pair con limite inferiore iteratore (incluso) e limite superiore (esclusivo) rispettivamente. Se la chiave non esiste, entrambi gli iteratori puntano al valore superiore più vicino (basato sul metodo di confronto utilizzato per ordinare il multiset ).
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'
Eliminazione di valori da un set
Il metodo più ovvio, se vuoi semplicemente resettare il tuo set / multiset su uno vuoto, è usare clear :
std::set<int> sut;
sut.insert(10);
sut.insert(15);
sut.insert(22);
sut.insert(3);
sut.clear(); //size of sut is 0
Quindi è possibile utilizzare il metodo di erase . Offre alcune possibilità che sembrano in qualche modo equivalenti all'inserimento:
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;
}
L'output sarà:
Set under test contains:
10
15
30
Tutti questi metodi si applicano anche al multiset . Si noti che se si chiede di eliminare un elemento da un multiset ed è presente più volte, tutti i valori equivalenti verranno eliminati .