To jest stara wersja strony!
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 zdefiniowana jest w standardowym nagłówku map oraz w niestandardowym, wstecznie kompatybilnym nagłówku map.h.
Składnik | Opis działania | |
---|---|---|
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ę. | |
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. | |
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. | |
const_iterator upper_bound(const key_type& k) const | Znajduje pierwszy element, którego klucz jest wiekszy niż k. | |
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>("Bob Smith",employeeID++) ); m.insert( pair<string,int>("Bob Thompson",employeeID++) ); m.insert( pair<string,int>("Bob Smithey",employeeID++) ); m.insert( pair<string,int>("Bob Smith",employeeID++) ); cout << "Number of employees named 'Bob Smith': " << m.count("Bob Smith") << endl; cout << "Number of employees named 'Bob Thompson': " << m.count("Bob Thompson") << endl; cout << "Number of employees named 'Bob Smithey': " << m.count("Bob Smithey") << endl; cout << "Employee list: " << endl; for( multimap<string, int>::iterator iter = m.begin(); iter != m.end(); ++iter ) { cout << " Name: " << 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.
Number of employees named 'Bob Smith': 2 Number of employees named 'Bob Thompson': 1 Number of employees named 'Bob Smithey': 1 Employee list: Name: Bob Smith, ID #0 Name: Bob Smith, ID #3 Name: Bob Smithey, ID #2 Name: Bob Thompson, 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> iterator begin(); const_iterator begin() const;
Funkcja begin() zwraca iterator na początek multimapy.
Poniższy kod wykorzystuje multimape do przemieszczania się po liście:
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; }
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>("Bob Smith",employeeID++) ); m.insert( pair<string,int>("Bob Thompson",employeeID++) ); m.insert( pair<string,int>("Bob Smithey",employeeID++) ); m.insert( pair<string,int>("Bob Smith",employeeID++) ); cout << "Number of employees named 'Bob Smith': " << m.count("Bob Smith") << endl; cout << "Number of employees named 'Bob Thompson': " << m.count("Bob Thompson") << endl; cout << "Number of employees named 'Bob Smithey': " << m.count("Bob Smithey") << endl; cout << "Employee list: " << endl; for( multimap<string, int>::iterator iter = m.begin(); iter != m.end(); ++iter ) { cout << " Name: " << iter->first << ", ID #" << iter->second << endl; }
Powyższy kod genereuje następujący wydruk:
Number of employees named 'Bob Smith': 2 Number of employees named 'Bob Thompson': 1 Number of employees named 'Bob Smithey': 1 Employee list: Name: Bob Smith, ID #0 Name: Bob Smith, ID #3 Name: Bob Smithey, ID #2 Name: Bob Thompson, ID #1