==========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ć. 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.


|^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|
|[[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.//|
|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.//|
|[[multimap#insert|iterator insert(const value_type& x)]] | Wstawia x w multimapę.|
|[[multimap#insert|iterator insert(iterator pos,const value_type& x)]] | Wstawia x w multimapę, używając pos jako wskazówki gdzie ma być wstawione.|
|[[multimap#insert|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.//|
|[[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.|

=====Konstruktory=====
Składnia:

<code cpp>
    #include <map>
    multimap();
    multimap( const multimap& c );
    multimap( iterator begin, iterator end,
              const key_compare& cmp = Compare(), const allocator& alloc = Allocator() );
    ~multimap();
</code>

Multimapy posiadaja kilka konstruktorów:

  * Domyślny konstruktow jest bezparametrowy i tworzy nową instancję multimapy. Jego złożoność czasowa jest stała.
  * 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 allocator wykorzystywany do zarządzania pamięcią wewnętrzną.

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:

<code cpp>
    multimap<string,int> m;
</code>

Wykorzystując szblon, można również wskazać key_compare oraz allocator:

<code cpp>
    multimap<string,int,myComp,myAlloc> m;
</code>

Poniższy przykład, wykorzystując multimapy wiąże pracowników z ich numerami ID:

<code cpp>
    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;
    }
</code>

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 terminal>
    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
</code>
=====Operatory=====
Składnia:

<code cpp>
    #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);
</code>

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:

  - Ich rozmiar jest jednakowy, oraz
  - Każdy element na danej pozycji w pierwszej multimapie jest równy elementówi na tej samej pozycji w drugiej multimapie.

Porównanie pomiędzy multimapami wykonywane jest leksykograficznie.

=====equal_range=====
Składnia:

<code cpp>
    #include <map>
    pair<iterator, iterator> equal_range( const key_type& key );
</code>

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():

<code cpp>
  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
  }
  
</code>

=====insert=====
Składnia:

<code cpp>
    #include <map>
    iterator insert( iterator pos, const value_type& val );
    iterator insert( const value_type& val );
    void insert( input_iterator start, input_iterator end );
</code>

Rodzaje funkcji insert():

  * wstawiająca val za elementem wskazywanym przez pos (gdzie jest to jedynie sugestia miejsca umieszczenia val, ponieważ multimapa jest posortowana) i zwraca iterator wskazujący na ten element.
  * wstawiająca val do multimapy, zwracając iterator na wstawiony element.
  * wstawiająca zakres elementów od start do end.

Poniżej, przykładowy kod używa funkcji insert() dodając pary <name,ID> do multimapy pracowników:

<code cpp>
    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;
    }
</code>

Powyższy kod genereuje następujący wydruk:

<code terminal>
  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
</code>