====== SET ======
===== Opis =====
Set - zbiór.
Set jest kontenerem asocjacyjnym w którym elementy są kluczami. Wartości elementów są unikalne - w zbiorze nie mogą znajdować się dwa elementy których .
Zbiór jest skonstruowany tak aby wyszukiwanie elementów według klucza było szybkie, natomiast wyszukiwanie po pozycji nie jest priorytetem.
Elementy w zbiorze są uporządkowane od najmniejszego do największego.
Podsumowując:
* Unikalne elementy
* Wartość elementu jest kluczem
* Elementy są uporządkowane
===== Wykorzystanie =====
==== Użycie szablonu ====
template < class Key, class Compare = less,
class Allocator = allocator > class set;
Szablon set przyjmuje 3 parametry:
- **Key** - klasa reprezentująca elementy
- **Compare** - klasa służąca do porównania dwóch elementów - wyrażenie **comp(a,b)** gdzie **//a,b//** to elementy, a **//comp//** to obiekt klasy **Compare** powinno zwrócić wartość true jeśli **//a//** ma być umieszczony przed **//b//**. Domyślnie wykorzystywany jest **//operator /**.
- **Allocator** - typ alokatora używany przy tworzeniu elementów. Domyślnie użyta jest klasa **allocator**
==== Metody ====
=== Konstruktory i destruktory ===
== Konstruktor domyślny ==
explicit set ( const Compare& comp = Compare(), Allocator& = Allocator() );
Tworzy pusty zbiór, o zerowym rozmiarze, bez żadnych elementów.\\
Złożoność obliczeniowa - stała.
== Konstruktor iterujący ==
template set ( InputIterator first, InputIterator last,
const Compare& comp= Compare(), const Allocator& = Allocator() );
Tworzy nowy zbiór który zawiera kopię elementów z podanego zakresu - pomiędzy **first**, a **last**. **//first//** wchodzi w zakres, **//last//** nie.\\
Złożoność obliczeniowa - liniowa jeśli elementy są posortowane według **comp**, dla nie posortowanych logarytmiczna.
== Konstruktor kopiujący ==
set ( const set& x );
Tworzy kopię zbioru, zawierającą kopie wszystkich elementów.\\
Złożoność obliczeniowa - liniowa.
== Destruktor domyślny ==
~set ( );
Niszczy obiekt wywołując destruktory dla wszystkich elementów które zawiera, i zwalnia całą przydzieloną pamięć.\\
Złożoność obliczeniowa - liniowa.
=== Iteratory ===
== begin ==
iterator begin ();
const_iterator begin () const;
Zwraca iterator wskazujący na pierwszy element w zbiorze.\\
Złożoność obliczeniowa - stała.
== end ==
iterator end ();
const_iterator end () const;
Zwraca iterator wskazujący na element za ostatnim elementem w zbiorze.\\
Złożoność obliczeniowa - stała.
== rbegin ==
reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
Zwraca odwrotny iterator wskazujący na ostatni element w zbiorze. Pozwala przejść po elementach w odwrotnej kolejności.\\
Złożoność obliczeniowa - stała.
== rend ==
reverse_iterator rend();
const_reverse_iterator rend() const;
Zwraca odwrotny iterator wskazujący na element przed pierwszym elementem.\\
Złożoność obliczeniowa - stała.
=== Pojemność ===
== empty ==
bool empty ( ) const;
Zwraca true jeśli zbiór jest pusty.\\
Złożoność obliczeniowa - stała.
== size ==
size_type size() const;
Zwraca ilość elementów w zbiorze.\\
Złożoność obliczeniowa - stała.
== max_size ==
size_type max_size () const;
Zwraca maksymalną liczbę elementów jakie może zawierać zbiór, ze względu na ograniczenia systemu, oraz biblioteki.\\
Złożoność obliczeniowa - stała.
=== Modyfkiacja zawartości ===
== insert ==
pair insert ( const value_type& x );
Dodawanie elementów do zbioru. **//x//** jest elementem który dodajemy.\\
Zwracana wartość to para zawierająca iterator na wstawiony element oraz zmienna bool która mówi o tym czy wstawienie się powiodło(mógł już istnieć element o tej samej wartości). Jeśli wstawienie nie powiodło się iterator wskazuje na element o wartości elementu wstawianego który już był w zbiorze.\\
Złożoność obliczeniowa - logarytmiczna.
iterator insert ( iterator position, const value_type& x );
Dodawanie elementów do zboiru z zaznaczeniem pozycji od której zacząć poszukiwanie miejsca na wstawienie elementu.
Może być w niektórych przypadkach szybsze niż zwykły insert.\\
Zwracana wartość to iterator na wstawiony, bądź już istniejący element.\\
Złożoność obliczeniowa - logarytmiczna.
template
void insert ( InputIterator first, InputIterator last );
Wstawia elementy z zakresu iteratorów **//first//** i **//last//**. **//first//** wchodzi w zakres, **//last//** nie.\\
Złożoność obliczeniowa - logarytmiczna.
== erase ==
void erase ( iterator position );
Usunięcie elementu wskazywanego przez iterator.\\
Złożoność obliczeniowa - stała.
size_type erase ( const key_type& x );
Usunięcie elementu o podanej wartości.\\
Zwraca 1 jeśli usunięto, 0 jeśli nie było elementu o podanej wartości.\\
Złożoność obliczeniowa - logarytmiczna.
void erase ( iterator first, iterator last );
Usuwa elementy z zakresu iteratorów **//first//** i **//last//**. **//first//** wchodzi w zakres, **//last//** nie.\\
Złożoność obliczeniowa - logarytmiczna.
== swap ==
void swap ( set& st );
Zamienia elementy z elementami w drugim zbiorze. Elementy z pierwszego zbioru znajdują się w drugim, a elementy z drugiego w pierwszym. Iteratory, referencje i wskaźniki pozostają aktualne po zamianie.\\
Złożoność obliczeniowa - stała.
== clear ==
void clear ( );
Usuwa wszystkie elementy ze zbioru.
Złożoność obliczeniowa - liniowa.
=== Porównywanie ===
== key_comp, value_comp ==
key_compare key_comp ( ) const;
value_compare value_comp ( ) const;
Zwraca obiekt przyjmujący 2 parametry umożliwiający porównanie 2 elementów
**comp(a,b)** gdzie **//a,b//** to elementy, a **//comp//** to obiekt zwrócony przez **//key_vomp//**, lub **//value_comp//** , zwraca wartość true jeśli **//a//** jest mniejszy niż **//b//**.\\
W przypadku zbioru **//key_comp//** i **//value_comp//** zwracają to samo gdyż elementy są kluczami.\\
Złożoność obliczeniowa - stała.
=== Operacje ===
== find ==
iterator find ( const key_type& x ) const;
Zwraca iterator wskazujący na element o podanej wartości. Jeśli element nie zostanie znaleziony to zwracany jest iterator end.\\
Złożoność obliczeniowa - logarytmiczna.
== count ==
size_type count ( cont key_type& x ) const;
Zwraca ilość elementów o podanej wartości. Dla zbioru zwraca 1, lub 0 w zależności czy element został znaleziony.\\
Złożoność obliczeniowa - logarytmiczna.
== lower_bound ==
iterator lower_bound ( const key_type& x ) const;
Zwraca iterator wskazujący na najmniejszy element który jest większy bądź równy podanemu.\\
Złożoność obliczeniowa - logarytmiczna.
== upper_bound ==
iterator upper_bound ( const key_type& x ) const;
Zwraca iterator wskazujący na najmniejszy element który jest większy od podanego.\\
Złożoność obliczeniowa - logarytmiczna.
== equal_range ==
pair equal_range ( const key_type& x ) const;
Zwraca zakres elementów o podanej wartości. W przypadku zbioru zwraca zakres o długości 1, lub 0.
Jeśli element o podanej wartości zostanie znaleziony zostaje on zwrócony jako pierwszy iterator, drugi iterator wskazuje na element za nim. Jesli element nie zostanie znaleziony pierwszy i drugi iterator wskazują na najmniejszy element większy od podanego.\\
Złożoność obliczeniowa - logarytmiczna.