Narzędzia użytkownika
opis_kontenera:multimap
Różnice
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:03] 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 | ||
| - | cout << *theIterator; } | ||
| =====equal_range===== | =====equal_range===== | ||
| Linia 215: | 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 233: | 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> | ||
opis_kontenera/multimap.1226016201.txt.gz · ostatnio zmienione: 2008/11/07 01:03 przez adrianf0
Narzędzia strony
Wszystkie treści w tym wiki, którym nie przyporządkowano licencji, podlegają licencji: CC Attribution-Noncommercial-Share Alike 3.0 Unported
