C++
std :: set i std :: multiset
Szukaj…
Wprowadzenie
set jest rodzajem kontenera, którego elementy są posortowane i unikalne. multiset jest podobny, ale w przypadku multiset wiele elementów może mieć tę samą wartość.
Uwagi
W tych przykładach zastosowano różne style C ++. Uważaj, jeśli używasz kompilatora C ++ 98; część tego kodu może nie być użyteczna.
Wstawianie wartości do zestawu
Trzy różne metody wstawiania mogą być używane z zestawami.
- Najpierw prosta wstawka wartości. Ta metoda zwraca parę, dzięki czemu dzwoniący może sprawdzić, czy wstawienie rzeczywiście wystąpiło.
- Po drugie, wstawka podając wskazówkę, gdzie wartość zostanie wstawiona. Celem jest optymalizacja czasu wstawiania w takim przypadku, ale wiedza, gdzie należy wstawić wartość, nie jest częstym przypadkiem. Bądź ostrożny w takim przypadku; sposób podania podpowiedzi różni się w zależności od wersji kompilatora .
- Na koniec możesz wstawić zakres wartości, podając wskaźnik początkowy i końcowy. Początkowy zostanie uwzględniony podczas wstawiania, a końcowy zostanie wykluczony.
#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;
}
Dane wyjściowe będą:
# 23 has been inserted!
# 23 already present in set!
Set under test contains:
5
7
12
20
23
30
45
Wstawianie wartości w wielu odcinkach
Wszystkie metody wstawiania z zestawów dotyczą także multisets. Niemniej jednak istnieje inna możliwość, która zapewnia listę inicjalizującą:
auto il = { 7, 5, 12 };
std::multiset<int> msut;
msut.insert(il);
Zmiana domyślnego rodzaju zestawu
set i multiset mają domyślne metody porównywania, ale w niektórych przypadkach może być konieczne ich przeciążenie.
Wyobraźmy sobie, że przechowujemy wartości ciągów w zestawie, ale wiemy, że te ciągi zawierają tylko wartości liczbowe. Domyślnie sortowanie będzie porównaniem ciągów leksykograficznych, więc kolejność nie będzie pasować do sortowania numerycznego. Jeśli chcesz zastosować sortowanie równoważne z tym, co byś miał z wartościami int , potrzebujesz funktora do przeciążenia metody porównania:
#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;
}
Dane wyjściowe będą:
### 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
W powyższym przykładzie można znaleźć 3 różne sposoby dodawania operacji porównania do std::set , każda z nich jest przydatna w swoim własnym kontekście.
Domyślne sortowanie
Spowoduje to użycie operatora porównania klucza (pierwszy argument szablonu). Często klucz już zapewnia dobre ustawienie domyślne dla funkcji std::less<T> . O ile ta funkcja nie jest wyspecjalizowana, używa operator< obiektu. Jest to szczególnie przydatne, gdy inny kod również próbuje użyć jakiegoś uporządkowania, ponieważ pozwala to zachować spójność całej bazy kodu.
Pisanie kodu w ten sposób zmniejszy wysiłek związany z aktualizacją kodu, gdy kluczowymi zmianami jest API, na przykład: klasa zawierająca 2 elementy, która zmienia się w klasę zawierającą 3 elementy. Po zaktualizowaniu operator< w klasie wszystkie wystąpienia zostaną zaktualizowane.
Jak można się spodziewać, użycie domyślnego sortowania jest rozsądnym ustawieniem domyślnym.
Sortowanie niestandardowe
Dodanie sortowania niestandardowego za pomocą obiektu za pomocą operatora porównania jest często stosowane, gdy domyślne porównanie nie jest zgodne. W powyższym przykładzie dzieje się tak, ponieważ ciągi odnoszą się do liczb całkowitych. W innych przypadkach jest często używany, gdy chcesz porównać (inteligentne) wskaźniki na podstawie obiektu, do którego się odnoszą lub ponieważ potrzebujesz różnych ograniczeń do porównywania (na przykład: porównywanie std::pair przez wartość first ).
Podczas tworzenia operatora porównania powinno to być stabilne sortowanie. Jeśli wynik operacji porównania zmieni się po wstawieniu, zachowanie będzie niezdefiniowane. Jako dobrą praktykę, operator porównania powinien używać tylko stałych danych (stałych członków, stałych funkcji ...).
Jak w powyższym przykładzie, często napotykasz klasy bez członków jako operatory porównania. Powoduje to utworzenie domyślnych konstruktorów i konstruktorów kopiowania. Domyślny konstruktor pozwala pominąć instancję w czasie budowy, a konstruktor kopiowania jest wymagany, ponieważ zestaw pobiera kopię operatora porównania.
Sortuj Lambda
Lambda to krótszy sposób pisania obiektów funkcyjnych. Pozwala to na zapisanie operatora porównania w mniejszej liczbie wierszy, dzięki czemu cały kod jest bardziej czytelny.
Wadą użycia lambdas jest to, że każda lambda dostaje określony typ w czasie kompilacji, więc decltype(lambda) będzie inny dla każdej kompilacji tej samej jednostki kompilacji (plik cpp) jak w przypadku wielu jednostek kompilacji (jeśli są zawarte w pliku nagłówkowym ). Z tego powodu zaleca się stosowanie obiektów funkcji jako operatora porównania, gdy są one używane w plikach nagłówków.
Taka konstrukcja często występuje, gdy zamiast tego używany jest std::set w lokalnym zasięgu funkcji, podczas gdy obiekt funkcji jest preferowany, gdy jest używany jako argument funkcji lub element klasy.
Inne opcje sortowania
Ponieważ operator porównania std::set jest argumentem szablonowym, wszystkie wywoływalne obiekty mogą być używane jako operator porównania, a powyższe przykłady są tylko szczególnymi przypadkami. Jedyne ograniczenia, jakie mają te obiekty na żądanie:
- Muszą być możliwe do skopiowania
- Muszą być wywoływalne z 2 argumentami typu klucza. (niejawne konwersje są dozwolone, ale nie zalecane, ponieważ mogą negatywnie wpłynąć na wydajność)
Wyszukiwanie wartości w zestawie i multisecie
Istnieje kilka sposobów wyszukiwania danej wartości w std::set lub w std::multiset :
Aby uzyskać iterator pierwszego wystąpienia klucza, można użyć funkcji find() . Zwraca end() jeśli klucz nie istnieje.
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);
Innym sposobem jest użycie funkcji count() , która zlicza, ile odpowiednich wartości znaleziono w set / multiset (w przypadku set , zwracana wartość może wynosić tylko 0 lub 1). Stosując te same wartości, co powyżej, będziemy mieć:
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
W przypadku std::multiset może istnieć kilka elementów o tej samej wartości. Aby uzyskać ten zakres, można użyć funkcji equal_range() . Zwraca std::pair posiadające odpowiednio iterator dolną granicę (włącznie) i górną granicę (wyłącznie). Jeśli klucz nie istnieje, oba iteratory wskazywałyby na najbliższą nadrzędną wartość (na podstawie metody porównania zastosowanej do posortowania danego 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'
Usuwanie wartości z zestawu
Najbardziej oczywistą metodą, jeśli chcesz po prostu zresetować set / multiset do pustej, jest użycie clear :
std::set<int> sut;
sut.insert(10);
sut.insert(15);
sut.insert(22);
sut.insert(3);
sut.clear(); //size of sut is 0
Następnie można zastosować metodę erase . Oferuje pewne możliwości, które wyglądają mniej więcej tak, jak wstawienie:
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;
}
Dane wyjściowe będą:
Set under test contains:
10
15
30
Wszystkie te metody dotyczą również multiset . Należy pamiętać, że jeśli poprosisz o usunięcie elementu z multiset i jest on obecny wiele razy, wszystkie równoważne wartości zostaną usunięte .