Tot timpul zilei!
Deci, să începem. După cum mulți știu, "setul" este tradus din limba engleză ca "set". De aici putem face o concluzie logică că setul este un fel de structură de date care implementează setul ca obiect matematic. În C ++ 11, există două implementări diferite ale setului. Primul a venit la noi de la C ++ 98. Acesta este un set normal și se bazează pe realizarea unui copac roșu-negru. A doua implementare este setată neordonată. care a fost "legalizată" odată cu introducerea standardului C ++ 11. Se bazează pe tabelele hash.
Următoarele operații utile sunt definite pentru setul:
În ceea ce privește multe alte containere stl, pentru a declara un set, este necesar să se înregistreze
De asemenea, puteți utiliza constructorul pentru a inițializa imediat containerul. Puteți inițializa cu un alt container sau o pereche de iteratori [primul. ultima).
Acesta este executat prin inserarea funcției supraîncărcate. Sintaxa apelului său:
Iată opțiunile sale principale:
Este nevoie de o valoare, o valoare care să fie introdusă în set și returnează o pereche de iteratori care indică elementul inserat și o variabilă bool indicând "succesul" inserției. Ie 1 - introducerea a avut loc, 0 - nr. Această funcție este realizată ca un logaritm din mărimea containerului, adică O (logn).
Este nevoie de valoarea valorii și iteratorul de indiciu și încearcă să introducă elementul cât mai aproape posibil de iteratorul de indiciu. Dacă inserarea se face imediat după sau înainte de iteratorul hintului. atunci funcția funcționează pentru O (1). în caz contrar, O (logn).
Adaugă adaugă pentru a seta toate elementele care se află în intervalul [primul; ultimul] după O ((ultima - prima) logare). InputIt trebuie să îndeplinească cerințele InputIterator. și anume sprijiniți următoarele operațiuni:
În acest caz, toate indicatorii și iteratorii de pe elementele setului rămân în stare de funcționare. De asemenea, este de remarcat faptul că setul suportă doar o apariție a unui element cu aceeași valoare, dar dacă setul are deja un element cu o astfel de valoare, acesta nu va fi adăugat. Cu toate acestea, există o structură multiset. care suportă mai multe apariții ale aceluiași element. Cu toate acestea, operațiunile pe aceasta, cu excepția nuanțelor mici, sunt identice cu operațiile pe set și, prin urmare, nu vor fi luate în considerare aici.
Există mai multe funcții diferite pentru a găsi elemente în set. Aici sunt:
Numără numărul de apariții ale cheii cu cheia din recipient. Evident, din cauza proprietăților containerului, această funcție returnează 0 sau 1. Funcționează pentru O (logn).
Găsește elementul cheie. Dacă se găsește un element, returnează un iterator pe acesta, altfel la capătul () al containerului. Funcționează pentru O (logn).
Returnează iteratorul la primul element din set care este mai mare sau egal cu cel dorit. O (logn).
Returnează iteratorul la primul element din set, care este strict mai mare decât cel pe care îl căutați. O (logn).
Fiți atenți! Pentru a utiliza în mod corespunzător aceste funcții, trebuie să le numiți ca funcții membre ale containerului.
Există, de asemenea, o funcție de ștergere supraîncărcată (). care vă permite să ștergeți articole. Iată opțiunile sale principale:
Înlăturarea elementului în poziția specificată de iterator. Complexitatea amortizată este O (1).
Elimină toate elementele cu ajutorul tastei cheie valoare. Este clar că dacă e doar un set. dar nu multiset. numărul de astfel de elemente nu depășește 1. Funcționează pentru O (logn + count (key)).
Elimină toate elementele din intervalul [prima; ultima]. Funcționează pentru O (logn + distanța (primul).
Acum să vorbim despre hartă. Numele provine de la matricea asociativă de cartografiere. Operațiile pe acesta sunt aproape identice stabilite. dar elementele de container este o singură valoare este stocată, iar perechea cheie-valoare. Sortarea, în acest caz, va avea loc în același mod ca și în perechile de sortare convenționale - prima prioritate merge comparația dintre primele elemente în pereche, și apoi, în caz de egalitate, a doua elemente sunt comparate. De remarcat este și implementarea foarte convenabilă a tratamentului indicatorilor. De exemplu, aici este codul:
Mai întâi, creați o pereche ("zece", 10) în harta test_un container, apoi schimbați al doilea element în acesta la 8.
neordonate _ set și neordonată _ harta suportă majoritatea operațiunilor susținute de set și harta. dar, în medie, le îndeplinesc pentru O (1). Cu toate acestea, ele nu sunt întotdeauna benefice pentru utilizare, deoarece mijloace neordonate neordonate, adică elementele din ele nu sunt acceptate în ordine sortată. Prin urmare, nu putem folosi aceste containere, de exemplu, sortarea piramidală, și nu putem în O (1) accesul la cea mai mare și cel mai mic element din set și harta. Și, ca urmare a unor tulburări, nu putem folosi aceste containere de operare mai mici _ legat și superioară _ legat.
În cele din urmă, pot sugera mai multe sarcini care pot fi rezolvate destul de ușor (în comparație cu soluția fără STL) utilizând aceste structuri de date:
P.S. Înțeleg că articolul nu este dezvăluit pe deplin în articol, deși am încercat să o fac. Dacă aveți întrebări sau comentarii după citire, le puteți spune.
STL. set. hartă
Trimiteți-le prietenilor: