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.
Przykładowy program wykorzystujący multimape.
Multimapa zdefiniowana jest w standardowym nagłówku map oraz w niestandardowym, wstecznie kompatybilnym nagłówku map.h.
Składnik | Opis | |
---|---|---|
key_type | Typ klucza multimapy, Key. | |
data_type | Typ obiektów powiązanych z kluczem. | |
value_type | Typ obiektu, pair<const key_type, data_type>, magazynowanego w multimapie. | |
key_compare | Obiekt funkcyjny, który porównuje dwa klucze w celu ustalenia porządku. | |
value_compare | Obiekt funkcyjny, który porównuje obikety obiekty powiązane z kluczami w celu ustalenia porządku. | |
pointer | Wskaźnik na T. | |
reference | Referencja do T. | |
const_reference | Stała referencja do T. | |
size_type | Integralny typ bez znaku. | |
difference_type | Integralny typ ze znakiem. | |
iterator | Iterator używany do iteracji poprzez multimapę. | |
const_iterator | Stały iterator używany do iteracji 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ę. | |
Nazwa metody | Opis działania | |
Konstruktory i destruktor | Domyślne metody do alokowania, kopiowania i dealocowania multimap. Złożoność czasowa: liniowa. | |
Operatory | Operacje przypisują i porównują multimap. Złożoność czasowa: liniowa. | |
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. | |
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. | |
reverse_iterator rbegin() | Zwraca reverse_iterator wskazujący na początek wstecznej multimapy.Złożoność czasowa: stała. | |
reverse_iterator rend() | Zwraca reverse_iterator wskazujący na koniec wstecznej multimapy.Złożoność czasowa: stała. | |
const_reverse_iterator rbegin() const | Zwraca const_reverse_iterator wskazujący na początek wstecznej multimapy.Złożoność czasowa: stała. | |
const_reverse_iterator rend() const | Zwraca const_reverse_iterator wskazujący na koniec wstecznej multimapy.Złożoność czasowa: stałą. | |
size_type size() const | Zwraca rozmiar multimapy. | |
size_type max_size() const | Zwraca najwiekszy możliwy rozmiar multimapy. | |
bool empty() const | Zwraca true jeśli rozmiar multimapy wynosi 0. | |
key_compare key_comp() const | Zwraca key_compare obiekt używany przez multimapę.Złożoność czasowa: stała. | |
value_compare value_comp() const | Zwraca value_compare obiekt używany przez mapę.Złożoność czasowa: stała. | |
void swap(multimap&) | Zamienia zawartość dwóch multimap.Złożoność czasowa: stała. | |
iterator insert(const value_type& x) | Wstawia x w multimapę. | |
iterator insert(iterator pos,const value_type& x) | Wstawia x w multimapę, używając pos jako wskazówki gdzie ma być wstawione. | |
void insert( input_iterator start, input_iterator end ) | Wstawia zakres w multimape. | |
void erase(iterator pos) | Usuwa element wskazywany przez pos. | |
size_type erase(const key_type& k) | Usuwa element, którego kluczem jest k. | |
void erase(iterator first, iterator last) | Usuwa wszystkie elementy z zakresu. | |
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. | |
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. | |
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. | |
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.Złożoność czasowa: logarytmiczna. | |
pair<iterator, iterator> equal_range(const key_type& k) | Znajduje zakres zawierający wszystkie elementy o kluczu k. | |
pair<const_iterator, const_iterator> equal_range(const key_type& k) const | Znajduje zakres zawierający wszystkie elementy o kluczu k. |
Składnia:
#include <map> multimap(); multimap( const multimap& c ); multimap( iterator begin, iterator end, const key_compare& cmp = Compare(), const allocator& alloc = Allocator() ); ~multimap();
Multimapy posiadaja kilka konstruktorów:
Domyślny destruktor jest wywoływany w celu zniszczenia objektu multimapy.
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:
multimap<string,int> m;
Wykorzystując szblon, można również wskazać key_compare oraz allocator:
multimap<string,int,myComp,myAlloc> m;
Poniższy przykład, wykorzystując multimapy wiąże pracowników z ich numerami ID:
multimap<string,int> m; int employeeID = 0; m.insert( pair<string,int>("Kowalski",employeeID++) ); m.insert( pair<string,int>("Nowak",employeeID++) ); m.insert( pair<string,int>("Matuszak",employeeID++) ); m.insert( pair<string,int>("Kowalski",employeeID++) ); cout << "Liczba pracownikow o nazwisku 'Kowalski': " << m.count("Kowalski") << endl; cout << "Liczba pracownikow o nazwisku 'Nowak': " << m.count("Nowak") << endl; cout << "Liczba pracownikow o nazwisku 'Matuszak': " << m.count("Matuszak") << endl; cout << "Lista pracownikow: " << endl; for( multimap<string, int>::iterator iter = m.begin(); iter != m.end(); ++iter ) { cout << " Nazwisko: " << iter->first << ", ID #" << iter->second << endl; }
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.
Liczba pracownikow o nazwisku 'Kowalski': 2 Liczba pracownikow o nazwisku 'Nowak': 1 Liczba pracownikow o nazwisku 'Matuszak': 1 Lista pracownikow: Nazwisko: Kowalski, ID #0 Nazwisko: Kowalski, ID #3 Nazwisko: Matuszak, ID #2 Nazwisko: Nowak, ID #1
Składnia:
#include <map> multimap operator=(const multimap& c2); bool operator==(const multimap& c1, const multimap& c2); bool operator!=(const multimap& c1, const multimap& c2); bool operator<(const multimap& c1, const multimap& c2); bool operator>(const multimap& c1, const multimap& c2); bool operator<=(const multimap& c1, const multimap& c2); bool operator>=(const multimap& c1, const multimap& c2);
Wszystkie kontenery w języku C++ mogą być porównywane i przypisywane z wykorzystaniem standardowych operatorów porównania: ==, !=, ⇐, >=, <, > oraz =. Złożoność czasowa operacji porównania i przypisania jest liniowa.
Dwie multimapy są równe jeśli:
Porównanie pomiędzy multimapami wykonywane jest leksykograficznie.
Składnia:
#include <map> pair<iterator, iterator> equal_range( const key_type& key );
Funkcja equal_range() zwraca dwa iteratory - jeden wskazuje na pierwszy element o kluczu key, zaś drugi na element za ostatnim elementem o kluczu key.
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():
multimap<string,pair<int,int> > input_config; // czyta konfiguracje z pliku "input.conf" do input_config readConfigFile( input_config, "input.conf" ); pair<multimap<string,pair<int,int> >::iterator,multimap<string,pair<int,int> >::iterator> ii; multimap<string,pair<int,int> >::iterator i; ii = input_config.equal_range("key"); for( i = ii.first; i != ii.second; ++i ) { bindkey(i->second.first, i->second.second); //przypisanie funckji klawiszom klawiatury } ii = input_config.equal_range("joyb"); for( i = ii.first; i != ii.second; ++i ) { bindjoyb(i->second.first, i->second.second); //przypisanie funkcji klawiszom joysticka }
Składnia:
#include <map> iterator insert( iterator pos, const value_type& val ); iterator insert( const value_type& val ); void insert( input_iterator start, input_iterator end );
Rodzaje funkcji insert():
Poniżej, przykładowy kod używa funkcji insert() dodając pary <name,ID> do multimapy pracowników:
multimap<string,int> m; int employeeID = 0; m.insert( pair<string,int>("Kowalski",employeeID++) ); m.insert( pair<string,int>("Nowak",employeeID++) ); m.insert( pair<string,int>("Matuszak",employeeID++) ); m.insert( pair<string,int>("Kowalski",employeeID++) ); cout << "Liczba pracownikow o nazwisku 'Kowalski': " << m.count("Kowalski") << endl; cout << "Liczba pracownikow o nazwisku 'Nowak': " << m.count("Nowak") << endl; cout << "Liczba pracownikow o nazwisku 'Matuszak': " << m.count("Matuszak") << endl; cout << "Lista pracownikow: " << endl; for( multimap<string, int>::iterator iter = m.begin(); iter != m.end(); ++iter ) { cout << " Nazwisko: " << iter->first << ", ID #" << iter->second << endl; }
Powyższy kod genereuje następujący wydruk:
Liczba pracownikow o nazwisku 'Kowalski': 2 Liczba pracownikow o nazwisku 'Nowak': 1 Liczba pracownikow o nazwisku 'Matuszak': 1 Lista pracownikow: Nazwisko: Kowalski, ID #0 Nazwisko: Kowalski, ID #3 Nazwisko: Matuszak, ID #2 Nazwisko: Nowak, ID #1