Nastavi v standardno knjižnico predlog C++ (STL)
Nabori so vrsta asociativnega vsebnika, v katerem mora biti vsak element edinstven, ker ga vrednost elementa identificira. Vrednosti so shranjene v določenem razvrščenem vrstnem redu, tj. naraščajoče ali padajoče.
The std::set je del standardne knjižnice predlog C++ (STL) in je definiran znotraj naslovna datoteka.
Sintaksa:
std::set set_name;
Tip podatkov: Set lahko sprejme katero koli vrsto podatkov, odvisno od vrednosti, npr. int, char, float itd.
primer:
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;> }> |
Izhod
F G
Časovna zahtevnost: O(N) // N je velikost nabora.
Pomožni prostor: O(N)
Razlog, da je natisnil samo F in G, je ta, da nabor ne sprejme več istih vrednosti, ampak sprejme le edinstveno vrednost. Lahko uporabimo Multiset če želimo shraniti več enakih vrednosti.
Nastavite razvrščeno v padajočem vrstnem redu
Privzeto je std::set razvrščen v naraščajočem vrstnem redu. Vendar pa imamo možnost spremeniti vrstni red razvrščanja z uporabo naslednje sintakse.
std::set set_name;
primer:
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;> }> |
Izhod
12 10 5 4
Časovna zahtevnost: O(N) // N je velikost nabora.
Pomožni prostor: O(N)
Opomba: Namesto večjega lahko uporabimo kateri koli primerjalnik, da nastavimo razvrščanje po meri.
Lastnosti
- Naročilo za shranjevanje – Set shrani elemente v razvrščeno naročilo.
- Vrednote Značilnosti – Vsi elementi v kompletu imajo edinstvene vrednosti .
- Vrednote Narava – Vrednosti elementa ni mogoče spremeniti, ko je dodan naboru, vendar je mogoče odstraniti in nato dodati spremenjeno vrednost tega elementa. Torej vrednote so nespremenljiv .
- Tehnika iskanja – Kompleti sledijo Binarno iskalno drevo izvajanje.
- Urejanje naročila – Vrednosti v nizu so neindeksirano .
Opomba: Če želite elemente shraniti v nerazvrščenem (naključnem) vrstnem redu, neurejen_nabor() je lahko uporabljen.
Nekatere osnovne funkcije, povezane z naborom
- začeti() – Vrne iterator prvemu elementu v nizu.
- konec () – Vrne iterator teoretičnemu elementu, ki sledi zadnjemu elementu v nizu.
- velikost () – Vrne število elementov v nizu.
- max_size() – Vrne največje število elementov, ki jih lahko vsebuje niz.
- prazno() – Vrne, ali je niz prazen.
Časovne zapletenosti za izvajanje različnih operacij na množicah so:
- Vstavljanje elementov – O(log N)
- Brisanje elementov – 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.begin(), s1.end());> > // 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;> }> |
Izhod
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
Drugačna funkcija nabora v C++ STL
| funkcija | Opis |
|---|---|
| začeti() | Vrne iterator prvemu elementu v nizu. |
| konec () | Vrne iterator teoretičnemu elementu, ki sledi zadnjemu elementu v nizu. |
| rbegin() | Vrne povratni iterator, ki kaže na zadnji element v vsebniku. |
| render() | Vrne povratni iterator, ki kaže na teoretični element tik pred prvim elementom v vsebniku nabora. |
| crbegin() | Vrne stalni iterator, ki kaže na zadnji element v vsebniku. |
| crend() | Vrne stalni iterator, ki kaže na položaj tik pred prvim elementom v vsebniku. |
| cbegin() | Vrne stalni iterator, ki kaže na prvi element v vsebniku. |
| nekaj() | Vrne stalni iterator, ki kaže na položaj za zadnjim elementom v vsebniku. |
| velikost () | Vrne število elementov v nizu. |
| max_size() | Vrne največje število elementov, ki jih lahko vsebuje niz. |
| prazno() | Vrne, ali je niz prazen. |
| vstavi (const g) | V niz doda nov element 'g'. |
| vstavek iteratorja (položaj iteratorja, const g) | Doda nov element 'g' na položaj, na katerega kaže iterator. |
| izbriši (položaj iteratorja) | Odstrani element na položaju, na katerega kaže iterator. |
| izbriši (const g) | Odstrani vrednost 'g' iz niza. |
| počisti() | Odstrani vse elemente iz kompleta. |
| key_comp() / value_comp() | Vrne objekt, ki določa, kako so elementi v nizu urejeni (» <« privzeto). |
| najdi (const g) | Vrne iterator elementu 'g' v nizu, če je najden, drugače vrne iterator na konec. |
| štetje (const g) | Vrne 1 ali 0 glede na to, ali je element 'g' prisoten v nizu ali ne. |
| spodnja_meja (const g) | Vrne iterator prvemu elementu, ki je enakovreden 'g' ali zagotovo ne bo šel pred element 'g' v nizu. |
| zgornja_meja(konst g) | Vrne iterator prvemu elementu, ki bo šel za elementom 'g' v nizu. |
| enako_razpon() | Funkcija vrne iterator parov. (key_comp). Par se nanaša na obseg, ki vključuje vse elemente v vsebniku, ki imajo ključ, enak k. |
| namestiti () | Ta funkcija se uporablja za vstavljanje novega elementa v vsebnik niza, samo če je element, ki ga želite vstaviti, edinstven in še ne obstaja v nizu. |
| emplace_hint() | Vrne iterator, ki kaže na položaj, kjer je opravljeno vstavljanje. Če element, posredovan v parametru, že obstaja, potem vrne iterator, ki kaže na položaj, kjer je obstoječi element. |
| zamenjaj() | Ta funkcija se uporablja za izmenjavo vsebine dveh kompletov, vendar morata biti kompleta iste vrste, čeprav se velikosti lahko razlikujejo. |
| operater= | ‘=’ je operator v C++ STL, ki kopira (ali premakne) niz v drug niz, set::operator= pa je ustrezna operatorska funkcija. |
| get_allocator() | Vrne kopijo predmeta dodeljevalnika, povezanega z nizom. |
Razlika med množico in neurejeno množico
| Set | Neurejen komplet |
|---|---|
| Set shrani elemente v razvrščenem vrstnem redu | Unordered Set hrani elemente v nerazvrščenem vrstnem redu |
| Nastavite samo trgovine/pridobite edinstvene elemente | Unordered Set shrani/pridobi samo edinstvene vrednosti |
| Set za izvedbo uporablja binarna iskalna drevesa | Unordered Set za izvedbo uporablja zgoščene tabele |
| Več kot en element lahko izbrišete tako, da podate začetni in končni iterator | Tisti element, za katerega je podan položaj iteratorja, lahko izbrišemo |
| set Set_Name; | unordered_set UnorderedSet_Name; |
Za več informacij si lahko ogledate članek – Kompleti proti neurejenemu nizu .
