Różnice między wybraną wersją a wersją aktualną.
Both sides previous revision Previous revision Next revision | Previous revision Last revision Both sides next revision | ||
opis_kontenera:multimap [2008/11/07 00:39] adrianf0 |
opis_kontenera:multimap [2008/11/15 23:11] 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:multimap3.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.//| | ||
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 57: | Linia 60: | ||
Składnia: | Składnia: | ||
- | <code> | + | <code cpp> |
#include <map> | #include <map> | ||
multimap(); | multimap(); | ||
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 76: | Linia 79: | ||
Szablon multimapy wymaga podania zarówno key_type jak i value_type. Na przykład można zainicjować multimapę z kluczem string i wartościami typu int: | Szablon multimapy wymaga podania zarówno key_type jak i value_type. Na przykład można zainicjować multimapę z kluczem string i wartościami typu int: | ||
- | <code> | + | <code cpp> |
multimap<string,int> m; | multimap<string,int> m; | ||
</code> | </code> | ||
Linia 82: | Linia 85: | ||
Wykorzystując szblon, można również wskazać key_compare oraz allocator: | Wykorzystując szblon, można również wskazać key_compare oraz allocator: | ||
- | <code> | + | <code cpp> |
multimap<string,int,myComp,myAlloc> m; | multimap<string,int,myComp,myAlloc> m; | ||
</code> | </code> | ||
Linia 88: | Linia 91: | ||
Poniższy przykład, wykorzystując multimapy wiąże pracowników z ich numerami ID: | Poniższy przykład, wykorzystując multimapy wiąże pracowników z ich numerami ID: | ||
- | <code> | + | <code cpp> |
multimap<string,int> m; | multimap<string,int> m; | ||
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 109: | Linia 112: | ||
Poniżej znajduje się wydruk zwracany przez powyższy kod. Warto zauważyć, że lista pracowników jest wyświetlona w porządku alfabetycznym. Wynika to z faktu, iż multimapa jest **sorującym** kontenerem asocjacyjnym. | Poniżej znajduje się wydruk zwracany przez powyższy kod. Warto zauważyć, że lista pracowników jest wyświetlona w porządku alfabetycznym. Wynika to z faktu, iż multimapa jest **sorującym** kontenerem asocjacyjnym. | ||
- | <code> | + | <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===== | ||
Składnia: | Składnia: | ||
- | <code> | + | <code cpp> |
#include <map> | #include <map> | ||
multimap operator=(const multimap& c2); | multimap operator=(const multimap& c2); | ||
Linia 141: | Linia 144: | ||
Porównanie pomiędzy multimapami wykonywane jest leksykograficznie. | Porównanie pomiędzy multimapami wykonywane jest leksykograficznie. | ||
+ | |||
=====equal_range===== | =====equal_range===== | ||
Składnia: | Składnia: | ||
- | <code> | + | <code cpp> |
#include <map> | #include <map> | ||
pair<iterator, iterator> equal_range( const key_type& key ); | pair<iterator, iterator> equal_range( const key_type& key ); | ||
Linia 153: | Linia 157: | ||
Poniższy przykład, pokazuje możliwość przypisania z pliku konfiguracyjnego odpowiednich funkcji do klawiszy klawiatury i joysticka z wykorzystaniem multimap, stringów oraz funkcji equal_range(): | Poniższy przykład, pokazuje możliwość przypisania z pliku konfiguracyjnego odpowiednich funkcji do klawiszy klawiatury i joysticka z wykorzystaniem multimap, stringów oraz funkcji equal_range(): | ||
- | <code> | + | <code cpp> |
multimap<string,pair<int,int> > input_config; | multimap<string,pair<int,int> > input_config; | ||
| | ||
Linia 164: | Linia 168: | ||
ii = input_config.equal_range("key"); | ii = input_config.equal_range("key"); | ||
for( i = ii.first; i != ii.second; ++i ) { | for( i = ii.first; i != ii.second; ++i ) { | ||
- | bindkey(i->second.first, i->second.second); //przypisanie funckji klawiszą klawiatury | + | bindkey(i->second.first, i->second.second); //przypisanie funckji klawiszom klawiatury |
} | } | ||
ii = input_config.equal_range("joyb"); | ii = input_config.equal_range("joyb"); | ||
for( i = ii.first; i != ii.second; ++i ) { | for( i = ii.first; i != ii.second; ++i ) { | ||
- | bindjoyb(i->second.first, i->second.second); //przypisanie funkcji klawiszą joysticka | + | bindjoyb(i->second.first, i->second.second); //przypisanie funkcji klawiszom joysticka |
} | } | ||
| | ||
Linia 177: | Linia 181: | ||
Składnia: | Składnia: | ||
- | <code> | + | <code cpp> |
#include <map> | #include <map> | ||
iterator insert( iterator pos, const value_type& val ); | iterator insert( iterator pos, const value_type& val ); | ||
Linia 192: | Linia 196: | ||
Poniżej, przykładowy kod używa funkcji insert() dodając pary <name,ID> do multimapy pracowników: | Poniżej, przykładowy kod używa funkcji insert() dodając pary <name,ID> do multimapy pracowników: | ||
- | <code> | + | <code cpp> |
multimap<string,int> m; | multimap<string,int> m; | ||
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 214: | 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> | ||