ZESTAW W STANDARDOWEJ BIBLIOTECE SZABLONÓW C++ (STL)

Zbiory to rodzaj kontenera skojarzeniowego, w którym każdy element musi być unikalny, ponieważ identyfikuje go wartość elementu. Wartości są przechowywane w określonej kolejności posortowania, tj. rosnąco lub malejąco.

The standardowe::ustawione klasa jest częścią standardowej biblioteki szablonów C++ (STL) i jest zdefiniowana wewnątrz plik nagłówkowy.

Składnia:

std::set set_name;

Typ danych: Zestaw może przyjmować dowolny typ danych w zależności od wartości, np. int, char, float itp.

Przykład:

set val; // defining an empty set set val = {6, 10, 5, 1}; // defining a set with values

Program:

C++

// C++ Program to Demonstrate> // the basic working of STL> #include> #include> int> main()> {> > std::set <> char> >a;> > a.insert(> 'G'> );> > a.insert(> 'F'> );> > a.insert(> 'G'> );> > for> (> auto> & str : a) {> > std::cout < < str < <> ' '> ;> > }> > std::cout < <>

'
'>

;> > return> 0;> }>

Wyjście

F G

Złożoność czasowa: O(N) // N to rozmiar zbioru.

Przestrzeń pomocnicza: NA)

Powodem, dla którego wydrukowano tylko F i G, jest to, że set nie przyjmuje wielu takich samych wartości, akceptuje jedynie unikalną wartość. Możemy użyć Zestaw wielokrotny jeśli chcemy przechowywać wiele takich samych wartości.

Ustaw posortowane w kolejności malejącej

Domyślnie std::set jest sortowany w kolejności rosnącej. Mamy jednak możliwość zmiany kolejności sortowania za pomocą następującej składni.

std::set  set_name;

Przykład:

C++

// C++ program to demonstrate the creation of descending> // order set container> #include> #include> using> namespace> std;> int> main()> {> > set <> int> , greater <> int> >> s1;> > s1.insert(10);> > s1.insert(5);> > s1.insert(12);> > s1.insert(4);> > for> (> auto> i : s1) {> > cout < < i < <> ' '> ;> > }> > return> 0;> }>

Wyjście

12 10 5 4

Złożoność czasowa: O(N) // N to rozmiar zbioru.

Przestrzeń pomocnicza: NA)

Notatka: Możemy użyć dowolnego komparatora zamiast większego, aby ustawić niestandardowe sortowanie.

Nieruchomości

Zapisywanie zamówienia – Zestaw przechowuje elementy w posortowane zamówienie.
Wartości Charakterystyka – Wszystkie elementy w zestawie posiadają unikalne wartości .
Ceni naturę – Wartość elementu nie może być modyfikowana po dodaniu go do zbioru, aczkolwiek istnieje możliwość usunięcia, a następnie dodania zmodyfikowanej wartości tego elementu. Tym samym wartości Czy niezmienny .
Technika wyszukiwania – Zestawy podążają za Drzewo wyszukiwania binarnego realizacja.
Ustalanie kolejności – Wartości w zestawie to nieindeksowane .

Notatka: Aby przechowywać elementy w kolejności nieposortowanej (losowej), unordered_set() może być użyte.

Niektóre podstawowe funkcje związane z zestawem

zaczynać() – Zwraca iterator do pierwszego elementu w zestawie.
koniec() – Zwraca iterator do elementu teoretycznego, który następuje po ostatnim elemencie w zestawie.
rozmiar() – Zwraca liczbę elementów w zestawie.
największy rozmiar() – Zwraca maksymalną liczbę elementów, jakie może pomieścić zbiór.
pusty() – Zwraca informację, czy zbiór jest pusty.

Złożoność czasowa wykonywania różnych operacji na zbiorach to:

Wstawianie elementów – O(log N)
Usuwanie elementów – O(log N)

CPP

// C++ program to demonstrate various functions of> // STL> #include> #include> #include> using> namespace> std;> int> main()> {> > // empty set container> > set <> int> , greater <> int> >> s1;> > // insert elements in random order> > s1.insert(40);> > s1.insert(30);> > s1.insert(60);> > s1.insert(20);> > s1.insert(50);> > // only one 50 will be added to the set> > s1.insert(50);> > s1.insert(10);> > // printing set s1> > set <> int> , greater <> int> >>::iterator itr;> > cout < <>

'
The set s1 is : 
'>

;> > for> (itr = s1.begin(); itr != s1.end(); itr++) {> > cout < < *itr < <> ' '> ;> > }> > cout < < endl;> > // assigning the elements from s1 to s2> > set <> int> >s2(s1.początek(), s1.koniec());> > // print all elements of the set s2> > cout < <>

'
The set s2 after assign from s1 is : 
'>

;> > for> (itr = s2.begin(); itr != s2.end(); itr++) {> > cout < < *itr < <> ' '> ;> > }> > cout < < endl;> > // remove all elements up to 30 in s2> > cout < <>

'
s2 after removal of elements less than 30 '>

>

':
'>

;> > s2.erase(s2.begin(), s2.find(30));> > for> (itr = s2.begin(); itr != s2.end(); itr++) {> > cout < < *itr < <> ' '> ;> > }> > // remove element with value 50 in s2> > int> num;> > num = s2.erase(50);> > cout < <>

'
s2.erase(50) : '>

;> > cout < < num < <>

' removed
'>

;> > for> (itr = s2.begin(); itr != s2.end(); itr++) {> > cout < < *itr < <> ' '> ;> > }> > cout < < endl;> > // lower bound and upper bound for set s1> > cout < <> 's1.lower_bound(40) : '> > < < *s1.lower_bound(40) < < endl;> > cout < <> 's1.upper_bound(40) : '> > < < *s1.upper_bound(40) < < endl;> > // lower bound and upper bound for set s2> > cout < <> 's2.lower_bound(40) : '> > < < *s2.lower_bound(40) < < endl;> > cout < <> 's2.upper_bound(40) : '> > < < *s2.upper_bound(40) < < endl;> > return> 0;> }>

Wyjście

The set s1 is : 60 50 40 30 20 10 The set s2 after assign from s1 is : 10 20 30 40 50 60 s2 after removal of elements less than 30 : 30 40 50 60 s2.erase(50) : 1 removed 30 40 60 s1.lower_bound(40) : 40 s1.upper_bound(40) : 30 s2.lower_bound(40) : 40 s2.upper_bound(40) : 60

Inna funkcja zestawu w C++ STL

Funkcjonować	Opis
zaczynać()	Zwraca iterator do pierwszego elementu w zestawie.
koniec()	Zwraca iterator do elementu teoretycznego, który następuje po ostatnim elemencie w zestawie.
rzacznij()	Zwraca iterator odwrotny wskazujący na ostatni element w kontenerze.
renderowanie()	Zwraca iterator odwrotny wskazujący element teoretyczny tuż przed pierwszym elementem w ustawionym kontenerze.
crbegin()	Zwraca stały iterator wskazujący na ostatni element w kontenerze.
wiara()	Zwraca stały iterator wskazujący pozycję tuż przed pierwszym elementem w kontenerze.
cbegin()	Zwraca stały iterator wskazujący na pierwszy element w kontenerze.
kilka()	Zwraca stały iterator wskazujący pozycję za ostatnim elementem kontenera.
rozmiar()	Zwraca liczbę elementów w zestawie.
największy rozmiar()	Zwraca maksymalną liczbę elementów, jakie może pomieścić zestaw.
pusty()	Zwraca informację, czy zestaw jest pusty.
wstaw (stała g)	Dodaje nowy element „g” do zestawu.
wstawka iteratora (pozycja iteratora, const g)	Dodaje nowy element „g” w pozycji wskazanej przez iterator.
usuń(pozycja iteratora)	Usuwa element w pozycji wskazanej przez iterator.
usuń (stała g)	Usuwa wartość „g” ze zbioru.
jasne()	Usuwa wszystkie elementy z zestawu.
klucz_komp() / wartość_komp()	Zwraca obiekt określający kolejność elementów w zestawie (domyślnie „ <”).
znajdź(stała g)	Zwraca iterator do elementu „g” w zestawie, jeśli został znaleziony, w przeciwnym razie zwraca iterator na koniec.
liczba (stała g)	Zwraca 1 lub 0 w zależności od tego, czy element „g” występuje w zestawie, czy nie.
dolna granica (stała g)	Zwraca iterator do pierwszego elementu, który jest odpowiednikiem „g” lub na pewno nie przejdzie przed elementem „g” w zestawie.
górna granica (stała g)	Zwraca iterator do pierwszego elementu, który nastąpi po elemencie „g” w zestawie.
równy_zakres()	Funkcja zwraca iterator par. (key_comp). Para odnosi się do zakresu obejmującego wszystkie elementy w kontenerze, których klucz jest odpowiednikiem k.
miejsce()	Funkcja ta służy do wstawienia nowego elementu do kontenera zestawu, tylko jeśli wstawiany element jest unikalny i nie istnieje jeszcze w zbiorze.
miejsce_podpowiedź()	Zwraca iterator wskazujący pozycję, w której wykonano wstawianie. Jeśli element przekazany w parametrze już istnieje, zwraca iterator wskazujący pozycję, w której znajduje się istniejący element.
zamieniać()	Funkcja ta służy do zamiany zawartości dwóch zestawów, przy czym zestawy muszą być tego samego typu, chociaż rozmiary mogą się różnić.
operator=	„=” to operator w języku C++ STL, który kopiuje (lub przenosi) zestaw do innego zestawu, a set::operator= jest odpowiednią funkcją operatora.
get_allocator()	Zwraca kopię obiektu alokatora powiązanego z zestawem.

Różnica między zbiorem a zbiorem nieuporządkowanym

Ustawić	Zestaw nieuporządkowany
Zestaw przechowuje elementy w posortowanej kolejności	Unordered Set przechowuje elementy w nieposortowanej kolejności
Ustawiaj sklepy/kupuj tylko unikalne elementy	Nieuporządkowany Zestaw przechowuje/pozyskuje tylko unikalne wartości
Zestaw wykorzystuje do implementacji drzewa wyszukiwania binarnego	Zestaw nieuporządkowany wykorzystuje do implementacji tablice mieszające
Można usunąć więcej niż jeden element, podając iterator początkowy i końcowy	Możemy wymazać ten element, dla którego podana jest pozycja iteratora
ustaw nazwę_zestawu;	unordered_set UnorderedSet_Name;