Różnice między wybraną wersją a wersją aktualną.
Both sides previous revision Previous revision Next revision | Previous revision | ||
opis_kontenera:multimap [2008/11/07 01:05] adrianf0 |
opis_kontenera:multimap [2008/11/15 23:19] (aktualna) adrianf0 |
||
---|---|---|---|
Linia 1: | Linia 1: | ||
==========Multimap========== | ==========Multimap========== | ||
- | Multimapa (podobnie jak mapa) to posortowany kontener asocjacyjny, czyli zbiornik o zmiennej długości gromadzący dane, które można dodawać i usuwać. Nie można jednak dodawać danych na konkretną pozycje, ponieważ kolejność ustalana jest wg danej klucz. Multimapa jest również parowym zbiornikiem asocjacyjnym, czyli jej elementami są pary wartości klucz i dana. Pierwszej wartości key_type, czyli klucza multimapy, nie można zmieniać, natomiast druga wartość danej jest przypisywalna (np.(*i).second=2). Multimapa **nie jest unikalnym kontenerem asocjacyjnym**, a więc dwa elementy mogą posiadać ten sam klucz. | + | Multimapa (podobnie jak mapa) to posortowany kontener asocjacyjny, czyli zbiornik o zmiennej długości gromadzący dane, które można dodawać i usuwać. Jest ona zbiornikiem parowym, a więc jej elementami są pary wartości: klucz i dana. Pierwszej wartości typu key_type, będącej kluczem multimapy, nie można zmieniać, natomiast druga wartość danej jest przypisywalna (np.(*i).second=2). Elementów multimapy nie można dodawać na konkretną pozycje, ponieważ ich kolejność ustalana jest wg danej klucz. Multimapa **nie jest unikalnym kontenerem asocjacyjnym**, a więc dwa elementy mogą posiadać ten sam klucz. |
+ | |||
+ | {{:multimap:multimap4.cpp|Przykładowy program wykorzystujący multimape.}} | ||
Multimapa zdefiniowana jest w standardowym nagłówku map oraz w niestandardowym, wstecznie kompatybilnym nagłówku map.h. | Multimapa zdefiniowana jest w standardowym nagłówku map oraz w niestandardowym, wstecznie kompatybilnym nagłówku map.h. | ||
- | |^Składnik ^Opis działania| | + | |^Składnik ^Opis| |
|key_type | Typ klucza multimapy, Key.| | |key_type | Typ klucza multimapy, Key.| | ||
|data_type | Typ obiektów powiązanych z kluczem.| | |data_type | Typ obiektów powiązanych z kluczem.| | ||
Linia 21: | Linia 23: | ||
|reverse_iterator | Iterator używany do iteracji wstecznej poprzez multimapę.| | |reverse_iterator | Iterator używany do iteracji wstecznej poprzez multimapę.| | ||
|const_reverse_iterator | Stały iterator używany do iteracji wstecznej poprzez multimapę.| | |const_reverse_iterator | Stały iterator używany do iteracji wstecznej poprzez multimapę.| | ||
+ | |^Nazwa metody ^Opis działania| | ||
|[[multimap#Konstruktory| Konstruktory i destruktor]]|Domyślne metody do alokowania, kopiowania i dealocowania multimap. //Złożoność czasowa: liniowa.//| | |[[multimap#Konstruktory| Konstruktory i destruktor]]|Domyślne metody do alokowania, kopiowania i dealocowania multimap. //Złożoność czasowa: liniowa.//| | ||
|[[multimap#Operatory | Operatory]]|Operacje przypisują i porównują multimap. //Złożoność czasowa: liniowa.//| | |[[multimap#Operatory | Operatory]]|Operacje przypisują i porównują multimap. //Złożoność czasowa: liniowa.//| | ||
- | |[[multimap#begin|iterator begin()]] | Zwraca iterator wskazujący na początek multimapy. //Złożoność czasowa: stała.//| | + | |iterator begin() | Zwraca iterator wskazujący na początek multimapy. //Złożoność czasowa: stała.//| |
|iterator end{} | Zwraca iterator wskazujący na koniec multimapy.//Złożoność czasowa: stała.//| | |iterator end{} | Zwraca iterator wskazujący na koniec multimapy.//Złożoność czasowa: stała.//| | ||
- | |[[multimap#begin|const_iterator begin() const ]]| Zwraca const_iterator wskazujący na początek multimapy.//Złożoność czasowa: stała.//| | + | |const_iterator begin() const | Zwraca const_iterator wskazujący na początek multimapy.//Złożoność czasowa: stała.//| |
|const_iterator end() const | Zwraca const_iterator wskazujący na koniec multimapy.//Złożoność czasowa: stała.//| | |const_iterator end() const | Zwraca const_iterator wskazujący na koniec multimapy.//Złożoność czasowa: stała.//| | ||
|reverse_iterator rbegin() | Zwraca reverse_iterator wskazujący na początek wstecznej multimapy.//Złożoność czasowa: stała.//| | |reverse_iterator rbegin() | Zwraca reverse_iterator wskazujący na początek wstecznej multimapy.//Złożoność czasowa: stała.//| | ||
Linia 45: | Linia 48: | ||
|void clear() | Usuwa wszystkie elementy. //Złożoność czasowa: liniowa.//| | |void clear() | Usuwa wszystkie elementy. //Złożoność czasowa: liniowa.//| | ||
|iterator find(const key_type& k) | Znajduje element, którego kluczem jest k.//Złożoność czasowa: logarytmiczna.//| | |iterator find(const key_type& k) | Znajduje element, którego kluczem jest k.//Złożoność czasowa: logarytmiczna.//| | ||
- | |const_iterator find(const key_type& k) const | Znajduje element, którego kluczem jest k.| | + | |const_iterator find(const key_type& k) const | Znajduje element, którego kluczem jest k.//Złożoność czasowa: logarytmiczna.//| |
|size_type count(const key_type& k) | Zlicza elementy, których kluczem jest k.//Złożoność czasowa: logarytmiczna.//| | |size_type count(const key_type& k) | Zlicza elementy, których kluczem jest k.//Złożoność czasowa: logarytmiczna.//| | ||
|iterator lower_bound(const key_type& k) | Znajduje pierwszy element, którego klucz jest nie mniejszy niż k.//Złożoność czasowa: logarytmiczna.//| | |iterator lower_bound(const key_type& k) | Znajduje pierwszy element, którego klucz jest nie mniejszy niż k.//Złożoność czasowa: logarytmiczna.//| | ||
|const_iterator lower_bound(const key_type& k) const | Znajduje pierwszy element, którego klucz jest nie mniejszy niż k.//Złożoność czasowa: logarytmiczna.//| | |const_iterator lower_bound(const key_type& k) const | Znajduje pierwszy element, którego klucz jest nie mniejszy niż k.//Złożoność czasowa: logarytmiczna.//| | ||
- | |iterator upper_bound(const key_type& k) | Znajduje pierwszy element, którego klucz jest wiekszy niż k.| | + | |iterator upper_bound(const key_type& k) | Znajduje pierwszy element, którego klucz jest wiekszy niż k.//Złożoność czasowa: logarytmiczna.//| |
- | |const_iterator upper_bound(const key_type& k) const | Znajduje pierwszy element, którego klucz jest wiekszy niż k.| | + | |const_iterator upper_bound(const key_type& k) const | Znajduje pierwszy element, którego klucz jest wiekszy niż k.//Złożoność czasowa: logarytmiczna.//| |
|[[multimap#equal_range | pair<iterator, iterator> equal_range(const key_type& k) ]]| Znajduje zakres zawierający wszystkie elementy o kluczu k.| | |[[multimap#equal_range | pair<iterator, iterator> equal_range(const key_type& k) ]]| Znajduje zakres zawierający wszystkie elementy o kluczu k.| | ||
|[[multimap#equal_range | pair<const_iterator, const_iterator> equal_range(const key_type& k) const]] | Znajduje zakres zawierający wszystkie elementy o kluczu k.| | |[[multimap#equal_range | pair<const_iterator, const_iterator> equal_range(const key_type& k) const]] | Znajduje zakres zawierający wszystkie elementy o kluczu k.| | ||
Linia 68: | Linia 71: | ||
Multimapy posiadaja kilka konstruktorów: | Multimapy posiadaja kilka konstruktorów: | ||
- | * Domyślny konstruktow jest bezparametrowy i tworzy nową instancję multimapynts, złożoność: stała. | + | * Domyślny konstruktow jest bezparametrowy i tworzy nową instancję multimapy. Jego złożoność czasowa jest stała. |
- | * Domyślny konstruktor koopiujący (złożoność: stała) może być użyty to tworzenia nowej multimapy będącej kopią danej multimapy c. | + | * Domyślny konstruktor kopiujący (stała złożoność czasowa) może być użyty to tworzenia nowej multimapy będącej kopią danej multimapy c. |
- | * Multimapy mogą być również utworzone z zakresu zdefiniowego przez begin oraz end. Używając konstruktora, opcjonalnie można dostarczyć key_compare& oraz allocato wykorzystywany do zarządzania pamięcią wewnętrzną. | + | * Multimapy mogą być również utworzone z zakresu zdefiniowego przez begin oraz end. Używając konstruktora, opcjonalnie można dostarczyć key_compare& oraz allocator wykorzystywany do zarządzania pamięcią wewnętrzną. |
Domyślny destruktor jest wywoływany w celu zniszczenia objektu multimapy. | Domyślny destruktor jest wywoływany w celu zniszczenia objektu multimapy. | ||
Linia 92: | Linia 95: | ||
int employeeID = 0; | int employeeID = 0; | ||
- | m.insert( pair<string,int>("Bob Smith",employeeID++) ); | + | m.insert( pair<string,int>("Kowalski",employeeID++) ); |
- | m.insert( pair<string,int>("Bob Thompson",employeeID++) ); | + | m.insert( pair<string,int>("Nowak",employeeID++) ); |
- | m.insert( pair<string,int>("Bob Smithey",employeeID++) ); | + | m.insert( pair<string,int>("Matuszak",employeeID++) ); |
- | m.insert( pair<string,int>("Bob Smith",employeeID++) ); | + | m.insert( pair<string,int>("Kowalski",employeeID++) ); |
- | cout << "Number of employees named 'Bob Smith': " << m.count("Bob Smith") << endl; | + | cout << "Liczba pracownikow o nazwisku 'Kowalski': " << m.count("Kowalski") << endl; |
- | cout << "Number of employees named 'Bob Thompson': " << m.count("Bob Thompson") << endl; | + | cout << "Liczba pracownikow o nazwisku 'Nowak': " << m.count("Nowak") << endl; |
- | cout << "Number of employees named 'Bob Smithey': " << m.count("Bob Smithey") << endl; | + | cout << "Liczba pracownikow o nazwisku 'Matuszak': " << m.count("Matuszak") << endl; |
- | cout << "Employee list: " << endl; | + | cout << "Lista pracownikow: " << endl; |
for( multimap<string, int>::iterator iter = m.begin(); iter != m.end(); ++iter ) { | for( multimap<string, int>::iterator iter = m.begin(); iter != m.end(); ++iter ) { | ||
- | cout << " Name: " << iter->first << ", ID #" << iter->second << endl; | + | cout << " Nazwisko: " << iter->first << ", ID #" << iter->second << endl; |
} | } | ||
</code> | </code> | ||
Linia 110: | Linia 113: | ||
<code terminal> | <code terminal> | ||
- | Number of employees named 'Bob Smith': 2 | + | Liczba pracownikow o nazwisku 'Kowalski': 2 |
- | Number of employees named 'Bob Thompson': 1 | + | Liczba pracownikow o nazwisku 'Nowak': 1 |
- | Number of employees named 'Bob Smithey': 1 | + | Liczba pracownikow o nazwisku 'Matuszak': 1 |
- | Employee list: | + | Lista pracownikow: |
- | Name: Bob Smith, ID #0 | + | Nazwisko: Kowalski, ID #0 |
- | Name: Bob Smith, ID #3 | + | Nazwisko: Kowalski, ID #3 |
- | Name: Bob Smithey, ID #2 | + | Nazwisko: Matuszak, ID #2 |
- | Name: Bob Thompson, ID #1 | + | Nazwisko: Nowak, ID #1 |
</code> | </code> | ||
=====Operatory===== | =====Operatory===== | ||
Linia 141: | Linia 144: | ||
Porównanie pomiędzy multimapami wykonywane jest leksykograficznie. | Porównanie pomiędzy multimapami wykonywane jest leksykograficznie. | ||
- | =====begin===== | ||
- | Składnia: | ||
- | <code cpp> | ||
- | #include <map> | ||
- | iterator begin(); | ||
- | const_iterator begin() const; | ||
- | </code> | ||
- | |||
- | Funkcja begin() zwraca iterator na pierwszy element multimapy. | ||
- | |||
- | Poniższy kod wykorzystuje multimape do przemieszczania się po liście: | ||
- | <code cpp> | ||
- | list<char> charList; // Tworzenie listy | ||
- | for( int i=0; i < 10; i++ ) { | ||
- | charList.push_front( i + 65 ); } | ||
- | list<char>::iterator theIterator; | ||
- | for( theIterator = charList.begin(); theIterator != charList.end(); theIterator++ ){ //inicjowanie iteratora i wykorzystanie go do poruszania się po liscie | ||
- | cout << *theIterator; } | ||
- | <//code> | ||
=====equal_range===== | =====equal_range===== | ||
Linia 216: | Linia 200: | ||
int employeeID = 0; | int employeeID = 0; | ||
- | m.insert( pair<string,int>("Bob Smith",employeeID++) ); | + | m.insert( pair<string,int>("Kowalski",employeeID++) ); |
- | m.insert( pair<string,int>("Bob Thompson",employeeID++) ); | + | m.insert( pair<string,int>("Nowak",employeeID++) ); |
- | m.insert( pair<string,int>("Bob Smithey",employeeID++) ); | + | m.insert( pair<string,int>("Matuszak",employeeID++) ); |
- | m.insert( pair<string,int>("Bob Smith",employeeID++) ); | + | m.insert( pair<string,int>("Kowalski",employeeID++) ); |
- | cout << "Number of employees named 'Bob Smith': " << m.count("Bob Smith") << endl; | + | cout << "Liczba pracownikow o nazwisku 'Kowalski': " << m.count("Kowalski") << endl; |
- | cout << "Number of employees named 'Bob Thompson': " << m.count("Bob Thompson") << endl; | + | cout << "Liczba pracownikow o nazwisku 'Nowak': " << m.count("Nowak") << endl; |
- | cout << "Number of employees named 'Bob Smithey': " << m.count("Bob Smithey") << endl; | + | cout << "Liczba pracownikow o nazwisku 'Matuszak': " << m.count("Matuszak") << endl; |
- | cout << "Employee list: " << endl; | + | cout << "Lista pracownikow: " << endl; |
for( multimap<string, int>::iterator iter = m.begin(); iter != m.end(); ++iter ) { | for( multimap<string, int>::iterator iter = m.begin(); iter != m.end(); ++iter ) { | ||
- | cout << " Name: " << iter->first << ", ID #" << iter->second << endl; | + | cout << " Nazwisko: " << iter->first << ", ID #" << iter->second << endl; |
} | } | ||
</code> | </code> | ||
Linia 234: | Linia 218: | ||
<code terminal> | <code terminal> | ||
- | Number of employees named 'Bob Smith': 2 | + | Liczba pracownikow o nazwisku 'Kowalski': 2 |
- | Number of employees named 'Bob Thompson': 1 | + | Liczba pracownikow o nazwisku 'Nowak': 1 |
- | Number of employees named 'Bob Smithey': 1 | + | Liczba pracownikow o nazwisku 'Matuszak': 1 |
- | Employee list: | + | Lista pracownikow: |
- | Name: Bob Smith, ID #0 | + | Nazwisko: Kowalski, ID #0 |
- | Name: Bob Smith, ID #3 | + | Nazwisko: Kowalski, ID #3 |
- | Name: Bob Smithey, ID #2 | + | Nazwisko: Matuszak, ID #2 |
- | Name: Bob Thompson, ID #1 | + | Nazwisko: Nowak, ID #1 |
</code> | </code> | ||