Różnice

Różnice między wybraną wersją a wersją aktualną.

--- opis_kontenera_set [2008/12/12 16:04]
maciekc
+++ opis_kontenera_set [2008/12/12 17:51] (aktualna)
maciekc
@@ Linia 1: / Linia 1: @@
 ====== SET ======
+===== Opis =====
 Set - zbiór.
@@ Linia 6: / Linia 8: @@
 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**. **//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 ==
+<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.
+== erase ==
+<code c++>
+void erase ( iterator position );
+</code>
+Usunięcie elementu wskazywanego przez iterator.\\
+Złożoność obliczeniowa - stała.
+<code c++>
+size_type erase ( const key_type& x );
+</code>
+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.
+<code c++>
+void erase ( iterator first, iterator last );
+</code>
+Usuwa elementy z zakresu iteratorów **//first//** i **//last//**. **//first//** wchodzi w zakres, **//last//** nie.\\
+Złożoność obliczeniowa - logarytmiczna.
+== swap ==
+<code c++>
+void swap ( set<Key,Compare,Allocator>& st );
+</code>
+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 ==
+<code c++>
+void clear ( );
+</code>
+Usuwa wszystkie elementy ze zbioru.
+Złożoność obliczeniowa - liniowa.
+=== Porównywanie ===
+== key_comp, value_comp ==
+<code c++>
+key_compare key_comp ( ) const;
+value_compare value_comp ( ) const;
+</code>
+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 ==
+<code c++>
+iterator find ( const key_type& x ) const;
+</code>
+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 ==
+<code c++>
+size_type count ( cont key_type& x ) const;
+</code>
+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 ==
+<code c++>
+iterator lower_bound ( const key_type& x ) const;
+</code>
+Zwraca iterator wskazujący na najmniejszy element który jest większy bądź równy podanemu.\\
+Złożoność obliczeniowa - logarytmiczna.
+== upper_bound ==
+<code c++>
+iterator upper_bound ( const key_type& x ) const;
+</code>
+Zwraca iterator wskazujący na najmniejszy element który jest większy od podanego.\\
+Złożoność obliczeniowa - logarytmiczna.
+== equal_range ==
+<code c++>
+pair<iterator,iterator> equal_range ( const key_type& x ) const;
+</code>
+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.

zpr c++ quick reference

Narzędzia użytkownika

Narzędzia witryny

Różnice

Narzędzia strony