Różnice między wybraną wersją a wersją aktualną.
Next revision | Previous revision Next revision Both sides next revision | ||
opis_kontenera_set [2008/12/09 13:33] maciekc utworzono |
opis_kontenera_set [2008/12/12 16:57] maciekc |
||
---|---|---|---|
Linia 1: | Linia 1: | ||
- | test | + | ====== 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 ==== | ||
+ | |||
+ | <code c++> | ||
+ | template < class Key, class Compare = less<Key>, | ||
+ | class Allocator = allocator<Key> > class set; | ||
+ | </code> | ||
+ | |||
+ | 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 == | ||
+ | <code c++> | ||
+ | explicit set ( const Compare& comp = Compare(), Allocator& = Allocator() ); | ||
+ | </code> | ||
+ | Tworzy pusty zbiór, o zerowym rozmiarze, bez żadnych elementów. | ||
+ | Złożoność obliczeniowa - stała. | ||
+ | |||
+ | == Konstruktor iterujący == | ||
+ | <code c++> | ||
+ | template <class InputIterator> set ( InputIterator first, InputIterator last, | ||
+ | const Compare& comp= Compare(), const Allocator& = Allocator() ); | ||
+ | </code> | ||
+ | Tworzy nowy zbiór który zawiera kopię elementów z podanego zakresu - pomiędzy **first**, a **last**. | ||
+ | Złożoność obliczeniowa - liniowa jeśli elementy są posortowane według **comp**, dla nie posortowanych logarytmiczna. | ||
+ | |||
+ | == Konstruktor kopiujący == | ||
+ | <code c++> | ||
+ | set ( const set<Key,Compare,Allocator>& x ); | ||
+ | </code> | ||
+ | Tworzy kopię zbioru, zawierającą kopie wszystkich elementów. | ||
+ | Złożoność obliczeniowa - liniowa. | ||
+ | |||
+ | == Destruktor domyślny == | ||
+ | <code c++> | ||
+ | ~set ( ); | ||
+ | </code> | ||
+ | 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 == | ||
+ | <code c++> | ||
+ | iterator begin (); | ||
+ | const_iterator begin () const; | ||
+ | </code> | ||
+ | Zwraca iterator wskazujący na pierwszy element w zbiorze. | ||
+ | Złożoność obliczeniowa - stała. | ||
+ | |||
+ | == end == | ||
+ | <code c++> | ||
+ | iterator end (); | ||
+ | const_iterator end () const; | ||
+ | </code> | ||
+ | Zwraca iterator wskazujący na element za ostatnim elementem w zbiorze. | ||
+ | Złożoność obliczeniowa - stała. | ||
+ | |||
+ | == rbegin == | ||
+ | <code c++> | ||
+ | reverse_iterator rbegin(); | ||
+ | const_reverse_iterator rbegin() const; | ||
+ | </code> | ||
+ | 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 == | ||
+ | <code c++> | ||
+ | reverse_iterator rend(); | ||
+ | const_reverse_iterator rend() const; | ||
+ | </code> | ||
+ | Zwraca odwrotny iterator wskazujący na element przed pierwszym elementem. | ||
+ | Złożoność obliczeniowa - stała. | ||
+ | |||
+ | === Pojemność === | ||
+ | |||
+ | == empty == | ||
+ | <code c++> | ||
+ | bool empty ( ) const; | ||
+ | </code> | ||
+ | Zwraca true jeśli zbiór jest pusty. | ||
+ | Złożoność obliczeniowa - stała. | ||
+ | |||
+ | == size == | ||
+ | <code c++> | ||
+ | size_type size() const; | ||
+ | </code> | ||
+ | Zwraca ilość elementów w zbiorze. | ||
+ | Złożoność obliczeniowa - stała. | ||
+ | |||
+ | == max_size == | ||
+ | <code c++> | ||
+ | size_type max_size () const; | ||
+ | </code> | ||
+ | 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 == | ||
+ | <code c++> | ||
+ | pair<iterator,bool> insert ( const value_type& x ); | ||
+ | </code> | ||
+ | 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. | ||
+ | |||
+ | <code c++> | ||
+ | iterator insert ( iterator position, const value_type& x ); | ||
+ | </code> | ||
+ | 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. | ||
+ | |||
+ | <code c++> | ||
+ | template <class InputIterator> | ||
+ | void insert ( InputIterator first, InputIterator last ); | ||
+ | </code> | ||
+ | Wstawia elementy z zakresu iteratorów **//first//** i **//last//**. **//first//** wchodzi w zakres, **//last//** nie. | ||
+ | Złożoność obliczeniowa - logarytmiczna. |