MULTISET

Multiset - multizbior.

Multiset jest kontenerem asocjacyjnym, w którym przechowywane są elementy typu Key. Multiset jest również kontenerem, w którym możne występować dwa lub więcej elementów o takim samym kluczu.

Multiset jest zdefiniowany w standardowym nagłówku set oraz w niestandardowym kompatybilnym wstecz nagłówku multiset.h

std::multiset<Key,Compare,Alloc>

Jest typem jaki jest przechowywany w multizbiorze. Jest również zdefiniowana jako multiset::key_type oraz multiset::value_type.

Key musi spełniać następujące wymagania:

• posiadać konstruktor kopiujący
• posiadać operator przypisania
• udostępniać funkcje void swap(Key,Key) która zamienia miejscami elementu podane jako argumenty

Jest typem za pomocą którego określa się kolejność przechowywanych elementów. Jest również zdefiniowana jako multiset::key_compare oraz multiset::value_compare. Domyślna wartość to: less<T> .

Compare musi spełniać następujące wymagania:

• posiadać operator wywolania funkcyjnego bool operator()(Key,Key) który zwraca true, gdy pierwszy argument jest mniejszy od drugiego, a w przeciwnym przypadku zwraca false

Jest to alokator używany do zarządzania pamięcią. Domyślna wartość to alloc .

Zdefiniowane są następujące typy iteratorów:

• multiset::iterator - pozwala na sekwencyjny dostęp do elementów multizbioru
• multiset::const_iterator - pozwala na sekwencyjny dostęp do elementów multizbioru (bez możliwości zmiany ich)
• multiset::reverse_iterotor - pozwala na sekwencyjny dostęp do elementów multizbioru (od końca do początku)
• multiset::const_reverse_iterator - pozwala na sekwencyjny dostęp do elementów multizbioru (od końca do początku, bez możliwości zmiany ich)

Zdefiniowane są następujące typy referencji:

• multiset::reference - typ będący referencją do elementów multizbioru
• multiset::const_reference - typ będący stała referencją do elementów multizbioru

Inne zdefiniowane typy to:

• multiset::key_compare , multiset::value_compare - typ określający sposób porównywania elementów
• multiset::key_type ,multiset::value_type - typ przechowywanych elementów
• multiset::size_type - typ określający odległość pomiędzy elementami (nieujemna)
• multiset::difference_type - typ określający odległość pomiędzy elementami (może być ze znakiem)

Konstruktor domyślny, tworzący pusty multizbiór.

Tworzy pusty multizbiór, używający podanego obiektu do porównywania elementów.

Tworzy multizbiór, posiadający elementy z zadanego zakresu.

Tworzy multizbiór, posiadający elementy z zadanego zakresu i używający podanego obiektu do porównywania elementów.

Konstruktor kopiujący.

• iterator begin ();
• const_iterator begin () const;

Zwraca iterator wskazujący na pierwszy element.

• iterator end ();
• const_iterator end () const;

Zwraca iterator wskazujący na element za ostatnim.

• reverse_iterator rbegin();
• const_reverse_iterator rbegin() const;

Zwraca odwrotny iterator wskazujący na ostatni element.

• reverse_iterator rend();
• const_reverse_iterator rend() const;

Zwraca odwrotny iterator wskazujący na element przed pierwszym elementem.

• bool empty() const - zwraca true, gdy multizbiór jest pusty, w przeciwnym przypadku false
• size_type count(const key_type& k) const - zwraca liczbę wystąpień elementów o zadanym kluczu
• size_type size() const - podaje liczbę elementów w multizbiorze

• iterator find(const key_type& k) const - Zwraca pierwszy element o zadanym kluczu.
• iterator lower_bound(const key_type& k) const - Zwraca pierwszy element którego klucz nie jest mniejszy od zadanego klucza.
• iterator upper_bound(const key_type& k) const - Zwraca pierwszy element, którego klucz jest większy od zadanego.

Jeśli nie istnieje taki element to funkcje te zwracają end()

• pair<iterator, iterator> equal_range(const key_type& k) const - Zwraca zakres elementów o zadanym kluczu.

Zakres elementów można też uzyskać za pomocą: pair<iterator, iterator>( multiset::lower_bound(key), multiset::upper_bound(key))

• iterator insert(const value_type& x) - dodaje x do multizbioru.
• iterator insert(iterator pos, const value_type& x) - dodaje x do multizbioru, używając pos jako wskazanie gdzie dany element ma zostać wstawiony
• template <class InputIterator>

void insert(InputIterator, InputIterator) - dodaje elementy z zadanego zakresu

• iterator erase(iterator pos) - usuwa element wskazywany przez iterator (zwraca iterator na element za osuniętym)
• size_type erase(const key_type& k) - usuwa wszystkie elementy o podanym kluczu
• iterator erase(iterator first, iterator last) - usuwa elementy podanego zakresu <first,last) (zwraca iterator na element za ostatnim usunietym)
• void clear() - usuwa wszystkie elementy

Aby usunąć jeden element o zadanym kluczu należy użyć następującej konstrukcji: erase( find(k) )

Przykładowy program pokazujący działanie multiset.