Kontenery standardowe

Definicja kontenera

Kontener

• w bibliotece standardowej C++ to struktura służąca do przechowywania danych i posiadająca ściśle zdefiniowany interfejs (zgodny z wymogami standardu)
• kontroluje alokację i dealokację obiektów przy pomocy konstruktorów, destruktorów, operacji wstawiania i usuwania elementów

W kontenerach standardowych do C++11 można było przechowywać tylko typy o semantyce wartości. Od C++11 minimalnym wymogiem jest, aby typ był usuwalny (erasable).

Każdy kontener Cont<T> (przechowujący typ T):

• definiuje typy cech

  Typ	Opis
  value_type	Typ T elementu przechowywanego w kontenerze
  reference	T&
  const_reference	const T&
  iterator	Typ iteratora, który wskazuje na elementy typu T
  const_iterator	Typ iteratora gwarantujący stałość wskazywanych elementów
  diference_type	int
  size_type	unsigned int

• posiada metody zwracające iteratory:

  Operacja	Efekt
  begin()	Zwraca iterator wskazujący na pierwszy element kolekcji
  end()	Zwraca iterator wskazujący pozycję następną po ostatnim elementem kolekcji
  cbegin()	Zwraca stały iterator wskazujący na pierwszy element kolekcji
  cend()	Zwraca stały iterator wskazujący pozycję następną po ostatnim elementem kolekcji

• implementuje operacje

  Operacja	Efekt
  Container c	Domyślny konstruktor - tworzy pusty kontener
  Container c(c2)	Konstruktor kopiujący (wszystkie elementy są kopiowane)
  Container c = c2	Konstruktor kopiujący (wszystkie elementy są kopiowane)
  Container c = r-value	Konstruktor przenoszący
  Container c(first, last)	Konstruuje kontener inicjując go kopiami wszystkich elementów z zakresu [first; last)
  Container c = {init_list}	Konstruuje kontener kopiując wszystkie elementy z listy inicjalizującej
  c.~Container()	Destruktor - niszczony jest każdy element kontenera i zwalniana jest pamięć
  c = c2	Kopiujący operator przypisania
  c = r-value	Przenoszący operator przypisania
  c.empty()	Zwraca czy kontener jest pusty
  c.size()	Zwraca ilość elementów przechowywanych w kontenerze
  c1 == c2	Zwraca czy dwa kontenery są sobie równe
  c2 != c2	Zwraca czy dwa kontenery są różne od siebie
  c1.swap(c2)	Wymienia zawartość dwóch kontenerów c1 i c2
  swap(c1, c2)	Wymienia zawartość dwóch kontenerów c1 i c2

Iteracja po kontenerach

Kontenery standardowe są kompatybilne z pętlą range-based-for:

const std::vector<int> vec = { 1, 2, 3, 4, 5 };

for(const auto& item : vec)
{
    std::cout << item << '\n';
}

Powyższa pętla jest rozwijana dla kontenerów standardowych do postaci:

{
    auto&& __range = vec;

    auto __begin = vec.begin();
    auto __end = vec.end();
    for( ; __begin != __end; ++__begin)
    {
        const auto& item = *__begin;
        std::cout << item << '\n';
    }
}

Adaptory kontenerów

szablony klas używające kontenerów do przechowywania elementów i udostępniające ograniczony interfejs. Adaptory kontenerów nie udostępniają iteratorów.

Kontenery sekwencyjne

Kontenery sekwencyjne

elementy są przechowywane w kolejności, w której zostały wstawione.

array<T, size_t>

• tablica o stałym rozmiarze (fixed size array).
• adaptuje dla statycznej tablicy pełny interfejs kontenera wymagany przez standard
• szybki dostęp do dowolnego elementu
• plik nagłówkowy: <array>

vector<T>

• podobny do tablicy
• może się rozrastać w zależności od potrzeb
• szybkie dodawanie i usuwanie możliwe jedynie na końcu pojemnika
• szybki dostęp do dowolnego elementu
• plik nagłówkowy: <vector>

deque<T>

• kolejka o dwóch końcach
• szybkie dodawanie z początku i końca
• szybki dostęp do poszczególnych elementów
• plik nagłówkowy: <deque>

list<T>

• szybkie wstawianie i usuwanie elementów
• brak dostępu do dowolnego elementu na liście
• plik nagłówkowy: <list>

std::array

std::array<T, N> implementuje tablicę o stałym rozmiarze (fixed size array). Spełnia (prawie) wszystkie wymagania dla kontenera przez co jest dużo wygodniejsza w użyciu niż tablica typu C-style.

Plik nagłówkowy <array>

namespace std
{
    template <typename T, size_t Size>
    struct array
    {
        T _Elems[Size];

        using value_type = T;
        using size_type = size_t;
        using difference_type = ptrdiff_t;
        using pointer = T *;
        using const_pointer = const T *;
        using reference = T&;
        using const_reference = const T&;

        using iterator = _Array_iterator<_Ty, _Size>;
        using const_iterator = _Array_const_iterator<_Ty, _Size>;

        using reverse_iterator = _STD reverse_iterator<iterator>;
        using const_reverse_iterator = _STD reverse_iterator<const_iterator>;

        constexpr reference operator[](size_type pos) noexcept
        {
            return _Elems[pos];
        }

        constexpr iterator begin() noexcept
        {   // return iterator for beginning of mutable sequence
            return (iterator(_Elems, 0));
        }


        constexpr iterator end() noexcept
        {   // return iterator for end of mutable sequence
            return (iterator(_Elems, _Size));
        }

        //... rest of implementation
    };
}

Inicjalizacja

Ponieważ std::array jest agregatem, możliwa jest inicjalizacja agregatowa.

Jest też jedynym kontenerem standardowym, którego elementy są inicjalizowane w sposób domyślny (default initialized).

std::array<int, 4> a; // items of a have undefined value

std::array<int, 4> arr1 = { {} }; // { 0, 0, 0, 0 }
std::array<int, 4> arr2 = { { 1, 2 } }; // { 1, 2, 0, 0 }
std::array<int, 4> arr3 = { { 1, 2, 3, 4 } }; // { 1, 2, 3, 4 };
std::array<int, 6> arr4 = { 1, 2, 3, 4, 5, 6 }; // possible warning

Od C++17 można w celu inicjalizacji wykorzystać mechanizm dedukcji parametrów klasy szablonowej:

std::array arr = { 1, 2, 3, 4, 5, 6 }; // std::array<int, 6>

static_assert(arr.size() == 6);
static_assert(is_same_v<decltype(arr)::value_type, int>);

for(const auto& item : arr)
    std::cout << item << ' ';
std::cout << '\n';

Zwracanie tablicy z funkcji

Jedną z zalet tablic std::array jest to, że można je zwracać z funkcji:

auto cross_product(const std::array<int, 3>& a, const std::array<int, 3>& b) -> std::array<int, 3>
{
    return {{
        a[1] * b[2] - a[2] * b[1],
        a[2] * b[0] - a[0] * b[2],
        a[0] * b[1] - a[1] * b[0],
    }};
}

Interoperacyjność z tablicami C

Metoda data() zwraca wskaźnik do typu danych przechowywanych w tablicy. Umożliwia to współpracę z kodem używającym klasycznych tablic C.

namespace LegacyCode
{
    void use_tab(int* tab, size_t size)
    {
        cout << "using tab: ";
        for (int* it = tab; it != tab + size; ++it)
            cout << *it << " ";
        cout << '\n';
    }
}

std::array arr1 = { 1, 2, 3, 4, 5 };
LegacyCode::use_tab(arr.data(), arr.size());

Można wykorzystać std::array<char> jako bufor dla C-string’ów:

std::array<char,255> cstr;           // create static array of 41 chars

strcpy(cstr.data(),"hello, world"); // copy a C-string into the array
printf("%s\n", cstr.data());        // print contents of the array as C-string

Zamiana danych - swap

Metoda swap() umożliwia wymianę danych w tablicach tego samego typu. Złożoność tej operacji jest liniowa.

std::array<int, 4> arr1 = { { 1, 2, -1, 4} };
std::array<int, 4> arr2 = { {} };

utils::print(arr1, "arr1: ");
utils::print(arr2, "arr2: ");

arr1.swap(arr2);

cout << "\nAfter swap:\n";
utils::print(arr1, "arr1: ");
utils::print(arr2, "arr2: ");

arr1: [ 1 2 -1 4 ]
arr2: [ 0 0 0 0 ]
Swap:
arr1: [ 0 0 0 0 ]
arr2: [ 1 2 -1 4 ]

Interfejs krotki

Dla typu std::array zaimplementowany jest interfejs krotki (tuple interface). W rezultacie można traktować obiekty tablic jako homogeniczne krotki.

using ArrayAsTuple = std::array<int, 4>;

ArrayAsTuple t = { { 1, 2, 3, 4 } };
static_assert(std::tuple_size<ArrayAsTuple>::value == 4);
static_assert(std::is_same_v<std::tuple_element<1, ArrayAsTuple>::type, int>);
assert(std::get<1>(t) == 2);

Structured bindings (C++17)

Od C++17 std::array może być dekomponowane do zmiennych za pomocą mechanizmu structured bindings:

array coord = { { 1, 2, 3 } };

auto [x, y, z] = coord;

assert(x == 1);
assert(y == 2);
assert(z == 3);

std::vector

• Plik nagłówkowy <vector>
• Rozmiar może być ustalany w czasie wykonania programu
• Elementy przechowywane są w sposób ciągły w pamięci
• Może się rozrastać w zależności od potrzeb
• Szybkie dodawanie i usuwanie jedynie na końcu (stała zamortyzowana złożoność czasowa)
• Liniowa złożoność operacji wstawiania i usuwania elementów z dowolnego innego miejsca
• Bardzo szybki dostęp do n-tego elementu zapisanego w wektorze - implementuje iterator o dostępie swobodnym

std::vector - szablon

Szablon

namespace std
{
    template <
        class T,
        class Allocator = std::allocator<T>
    > class vector
    {
        //...
    };
}

std::vector - konstruktory

Konstruktory - std::vector

vector::vector()

Tworzy pusty wektor

vector::vector(const vector &vec)

Tworzy wektor i kopiuje do niego wszystkie elementy z kontenera vec

vector::vector(vector &&vec)

Tworzy wektor i przenosi do niego wszystkie elementy z kontenera vec

vector::vector(sizeType n, const valueType &x)

Tworzy kontener posiadający n kopii elementu x

vector::vector(InIter first, Inlter last)

Tworzy kontener z elementami skopiowanymi z zakresu [first,last) określonego przez iteratory wejściowe first i last

std::vector<int> vec_int;
std::vector<std::string> vec_str(10, "item"s);
std::vector<double> vec_dbl = { 3.14, 1.15, 7.66, 6.65 };

std::vector<int> vec_int_backup(vec_int);
std::vector<std::string> vec_str_backup(vec_str.begin(), vec_str.end());

Ostrzeżenie

Należy uważać na wywołania konstruktorów za pomocą nawiasów klamrowych.

vector<int> vec1(4, 1); // vec1 contains { 1, 1, 1, 1 }
vector<int> vec2{4, 1}; // vec2 contains { 4, 1 }

Inicjalizacja w C++17

Od C++17 można inicjalizować wektor w prostszy sposób wykorzystując mechanizm dedukcji typów dla argumentów klas szablonowych:

std::vector vec = { 1, 2, 3, 4 };

std::array arr = { 1, 2, 3, 4, 5 };

std::vector backup(begin(arr), end(arr)); // deduction of T from pair of iterators

std::vector - metody dostępu

Metody dostępowe wektora:

reference vector::front()

zwraca pierwszy element wektora

reference vector::back()

zwraca ostatni element wektora

reference vector::operator[](sizeType n)

zwraca element o indeksie n

reference vector::at(sizeType n)

zwraca element o indeksie n - rzuca wyjątki std::out_of_range gdy n>=size()

Rozmiar, pojemność, maksymalny rozmiar

sizeType vector::size() const

zwraca liczbę elementów znajdujących się w kontenerze

sizeType vector::capacity() const

zwraca maksymalną liczbę elementów, które można zapisać w kontenerze bez zmiany jego rozmiaru

sizeType vector::max_size() const

zwraca maksymalną liczbę elementów, które można zapisać w kontenerze

bool vector::empty() const

jeżeli kontener jest pusty zwraca true

Przykład

std::vector<int> vec_int(3, 0);
vec_int[0] = 1;
vec_int.at(1) = 2;
vec_int[2] = 3;

std::cout << vec_int.front() << '\n';

try
{
    vec_int.at(300) = 2;
}
catch (const std::out_of_range& e)
{
    std::cerr << "out_of_range: " << e.what() << std::endl;
}

std::vector - iteratory

Metody zwracające iteratory

const_iterator vector::begin() const

iterator vector::begin()

const_iterator vector::cbegin() const

zwraca iterator wskazujący na pierwszy element

iterator vector::end()

const_iterator vector::end() const

const_iterator vector::cend() const

zwraca iterator wskazujący na pozycję znajdującą się z ostatnim elementem zapisanym w kontenerze

reverse_iterator vector::rbegin()

const_reverse_iterator vector::rbegin() const

const_reverse_iterator vector::crbegin() const

zwraca wsteczny iterator wskazujący na ostatni element kontenera

reverse_iterator vector::rend()

const_reverse_iterator vector::rend() const

const_reverse_iterator vector::crend() const

zwraca wsteczny iterator wskazujący na pozycję poprzedzającą pierwszy element wektora

Przykład

#include <vector>
using namespace std;
...
vector<int> vec_int(10);

for (auto cit = vec_int.cbegin(); cit != vec_int.cend(); ++cit)
    cout << *cit << endl;

int count = 0;
for (auto it = vec_int.begin(); it != vec_int.end(); ++it)
    *it = ++count;

std::vector - wstawianie elementów

Do wektora można wstawiać elementy za pomocą następujących metod:

void vector::push_back(const T &elem)

wstawia na koniec wektora kopię wartości elementu elem.

void vector::push_back(T &&elem)

wstawia na koniec wektora przenosząc wartość elementu elem.

iterator vector::insert(iterator pos, const T &elem)

wartość elementu elem zostaje wstawiona do wektora przed pozycją wskazywaną przez pos

iterator vector::insert(iterator pos, T &&elem)

wartość elementu elem zostaje przeniesiona do wektora przed pozycją wskazywaną przez pos

iterator vector::insert(iterator pos, InputIt first, InputIt last)

wstawia do kontenera elementy z zakresu [first; last) przed pozycją pos

iterator vector::insert(iterator, initializer_list<T> il)

wstawia elementy z listy inicjalizacyjnej przed pozycją pos

std::vector<int> v;

v.push_back(1);
v.push_back(2);
v.insert(v.begin(), 0)
v.insert(v.end(), {3, 4, 5});

// v -> 0, 1, 2, 3, 4, 5

Operacje emplace

Od wersji C++11 istnieją nowe metody:

reference vector::emplace_back(Args&&... args)

wstawia na koniec obiekt skonstruowany „w miejscu” (in-place). Konstruktor elementu jest wywoływany z użyciem argumentów args.

iterator vector::emplace(const_iterator pos, Args&&... args)

wstawia przed pozycją pos obiekt skonstruowany „w miejscu” (in-place). Konstruktor elementu jest wywoływany z użyciem argumentów args.

using namespace std;

struct Person
{
    string name;
    string surname;

    bool operator==(const Person& p) const
    {
        return std::tie(name, surname) == std::tie(p.name, p.surname);
    }
};

int main()
{
    std::vector<Person> staff;
    auto& person = staff.emplace_back("Jan", "Nowak");

    assert(person == staff.front());
}

std::vector - usuwanie elementów

Operacje erase() umożliwiają usuwanie elementów z wektora:

iterator vector::erase(iterator pos)

usuwa element wskazywany przez pos.

Iterator pos musi być prawidłowy i dereferencjowalny -> iterator zwracany przez end() nie może być w tym przypadku użyty

iterator vector::erase(iterator first, iterator last)

usuwa elementy w zakresie wskazywanym przez [first, last)

W obu przypadkach zwracany jest iterator wskazujący na następną pozycję po ostatnim usuniętym elemencie.

std::vector<int> vec = { 1, 2, 3, 4, 5, 6, 7, 8 };

vec.erase(begin(vec) + 2, begin(vec) + 5);

// in vec after erase { 1, 2, 6, 7, 8 }

std::vector - ważność iteratorów

Wstawienie lub usunięcie elementów powoduje unieważnienie referencji, wskaźników oraz iteratorów odnoszących się do elementów następnych.

Jeśli wstawienie powoduje realokację unieważniane są wszystkie referencje, wskaźniki oraz iteratory odnoszące się do elementów kontenera.

Przykład nieprawidłowego kodu:

std::vector vec = { 1, 4, 5, 4, 2, 3, 4, 1 };

auto end = vec.end();
for (auto it = vec.begin(); it != end; ++it)
{
    if (*it == 4)
        v.erase(it); // WRONG!

}

Użycie funkcji reserve() jeśli spowoduje realokację także unieważnia wszystkie referencje, wskaźniki oraz iteratory odnoszące się do elementów kontenera

std::vector<string> words = { "hello", "stl", "!" };

std::string* ps = &words[0];

std::string& rs = words.back();

auto it = words.begin();
++it;

words.reserve(255); // reallocation

std::cout << *ps << " " << rs << " " << *it << '\n'; // undefined behavior

Efektywne stosowanie wektorów

Kontener typu std::vector to ciągły bufor pamięci (tablica) o rozmiarze odpowiednim do przechowywania n obiektów typu T.

Klasa std::vector posiada mechanizmy automatycznego zarządzania pamięcią bufora

• metody służące do wstawiania oraz usuwania elementów
• metody udostępniające zestaw metadanych o stanie kontenera
  • size()
  • capacity()
  • max_size()

Obiekt klasy vector potrafi automatycznie powiększać swoją pojemność. Algorytm rozrostu rozmiaru bufora jest zależny od implementacji. Zwykle bufor o n elementach jest zastępowany buforem o rozmiarze 2n

Procedura rozciągania bufora kontenera przedstawia się następująco:

1. Przydział pamięci dla nowego bufora
2. Skopiowanie (lub przeniesienie) elementów z starego do nowego bufora
3. Zwolnienie dotychczasowego bufora

Rezerwacja pamięci dla bufora danych

Realokacja bufora w wektorze jest operacją czasochłonną. Należy się przed tym chronić rezerwując z góry bufor odpowiednio duży do planowanego rozmiaru kontenera.

std::vector<std::string> vec; // empty vec (size & capacity == 0)
vec.reserve(100);

for(int i = 0; i < 100; ++i)
    vec.push_back(std::to_string(i)); // efficient push_backs

Efektywne usuwanie elementów

Usunięcie elementu ze środka kontenera ma złożoność liniową.

vector<int> vec = { 1, 2, 3, 4, 6, 7, 8, 9, 10 };

vec.erase(begin(vec) + 2);

Jeśli nie zależy nam na zachowaniu porządku elementów w wektorze możemy zastosować wydajniejszy idiom:

template<typename T>
void efficient_erase(std::vector<T>& vec, std::vector<T>::iterator pos)
{
    std::swap(*pos, vec.back());
    vec.pop_back();
}

efficient_erase(vec, begin(vec) + 2);

Przechowywanie wskaźników w wektorze

W kontenerach standardowych mogą być przechowywane smart-pointer’y.

class Gadget { /*...*/ };

vector<unique_ptr<Gadget>> gadgets;

auto g = make_unique<Gadget>(6, "mp3 player");

gadgets.push_back(make_unique<Gadget>(1, "ipad")); // C++14
gadgets.push_back(move(g));
gadgets.emplace_back(make_unique<Gadget>(4, "smartphone"));

// caution!!!
gadgets.emplace_back(new Gadget{4, "smartphone"}); // may leak in C++11

gadgets.clear(); // deleting all gadgets stored in the vector

Kopiowanie wektora

Kopiowanie wektorów można wykonać na dwa sposoby:

1. konstruując obiekt kontenera vector jako kopię innego kontenera tego typu - konstruktor kopiujący
2. wywołując na rzecz istniejącego kontenera metodę assign()

string words[] = { "Szkolenie", "ze", "Standard",  "Template", "Library" };

vector<string> vec1(words, words + 5);
vector<string> vec2(vec1);
vector vec3(vec1); // since C++17


vec1.assign(vec3.rbegin(), vec3.rend());

Zamiana danych w wektorach

Efektywna zamiana danych między dwoma wektorami tego samego typu jest możliwa dzięki operacji swap()

std::vector<int> vec1 = { 1, 2, 3, 4, 5, 6, 7, 8 };
std::vector<int> vec2 = { 9, 10 };

vec1.swap(vec2); // zamiana danych w wektorach

Idiom zmniejszania bufora danych w wektorze wymaga użycia metody swap()

std::vector<int> vec(1000);
vec.erase(begin(vec) + 50, end(vec));

std::vector<int> temp(vec);
temp.swap(vec);

// krócej z wykorzystaniem obiektu tymczasowego
std::vector<int>(vec).swap(vec);

W C++11 możliwa jest zmiana wielkości zarezerwowanej przez wektor pamięci przy pomocy funkcji shrink_to_fit().

vec.shrink_to_fit(); // reallocation if necessary

Obsługa wyjątków

Jedyną funkcją, od której standard wymaga zgłaszania wyjątków, jest metoda at()

Jeśli funkcja wywołana przez wektor zgłasza wyjątki gwarantowane jest:

• Jeśli za pomocą push_back() wstawiany jest element i wystąpi wyjątek, funkcja ta nie spowoduje żadnego skutku
• Jeśli operacje kopiowania elementów nie zgłaszają wyjątków, funkcja insert() albo kończy się powodzeniem, albo nie powoduje żadnego skutku
• Funkcja pop_back() nie zgłasza żadnych wyjątków
• Funkcja swap() nie zgłasza żadnych wyjątków*
• Jeśli używane są typy POD, każda operacja kończy się powodzeniem, albo nie powoduje żadnego skutku
• Funkcje erase() oraz clear() nie zgłaszają wyjątków, jeśli operacje kopiowania nie zgłaszają wyjątków.

std::vector<bool>

Specjalizowana klasa przechowująca w wektorze wartości logiczne w postaci bitowej.

Posiada rozszerzony interfejs - operację flip()

std::vector<bool> vec_bool(7);
vec_bool[1] = true;
vec_bool[4] = true;

vec_bool.push_back(true);

std::copy(vec_bool.begin(), vec_bool.end(), std::ostream_iterator<int>(std::cout, " ") );
std::cout << '\n';

vec_bool[0].flip();
vec_bool.flip();

Problemy z typem vector<bool>

1. nie jest poprawnym kontenerem STL - nie spełnia wymagań zdefiniowanych przez standard

   std::vector<int> vec = { 1, 2, 3 };
   int* p = &c[0];
   
   vector<bool> v(8);
   bool* pb = &v[0]; // compilation error
   

2. operator indeksowania nie zwraca typu referencyjnego (bool&) - zwraca tymczasowe obiekty proxy

   template <typename Allocator>
   class std::vector<bool, Allocator>
   {
   public:
       class reference { /*....*/ };
       reference operator[](size_type n);
   };
   

   W rezultacie aby iterować pętlą range-based-for po kontenerze z zamiarem zmiany elementów, należy użyć deklaracji auto&&:

   std::vector<bool> bits = { 0, 1, 1, 1, 0, 0, 0, 1 };
   
   for(auto&& bit : bits)
   {
       bit.flip();
       cout << bit;
   }
   cout << '\n';
   

std::deque

deque [„deck”] = double-ended queue - kolejka dwukierunkowa

namespace std
{
    template<
        class T,
        class Allocator = std::allocator<T>
    > class deque
    {
        //...
    };
}

• Plik nagłówkowy: <deque>
• Wstawianie elementów jest efektywne zarówno na początku jak i na końcu kontenera
• Posiada operator []
• Struktura wewnętrzna wprowadza dodatkowy etap pośredni w dostępie do elementów - operacje dostępu do elementów i ruchu iteratora są zwykle wolniejsze
• Iteratory są inteligentnymi wskaźnikami nawigującymi po segmentach pamięci
• Kontener deque nie oferuje możliwości sterowania pojemnością ani momentem realokacji
• Bloki pamięci mogą zostać automatycznie zwolnione, gdy nie są już wykorzystywane

std::deque - operacje na końcach kolejki

Operacje wstawiania i usuwania na końcach kolejki

void deque::push_front(const valueType &x)

wstawianie na początek

void deque::pop_front()

usunięcie z początku

void deque::push_back(const valueType &x)

wstawianie na koniec

void deque::pop_back()

usunięcie ostatniego elementu

Podobnie jak wektor, od wersji C++11 mamy nowe metody wykorzystujące tworzenie obiektów „w miejscu”:

reference deque::emplace_back(Args &&args)

reference deque::emplace_front(Args &&args)

iterator deque::emplace(const_iterator pos, Args &&args)

wstawiają elementy przekazując do konstruktora typu argumenty args

std::deque<std::string> coll = { "middle" };

coll.push_back("last");
coll.emplace_back('!', 3);

coll.push_front("first");
coll.emplace_front('>', 3);

coll.emplace(coll.begin() + 2, '-', 3);

// coll { ">>>", "first", "---", "last", "!!!" }

coll.pop_back();
coll.pop_front();

// coll { "first", "---", "last" }

std::deque - ważność iteratorów

• Operacje wstawiania na końcach kolejki - push_front(), push_back(), emplace_back(), emplace_front()
  • wszystkie związane z nią iteratory tracą ważność, natomiast wszystkie wskaźniki i referencje na elementy kolejki nie tracą ważności
• Operacje wstawiania w środku - insert(), emplace()
  • unieważniają wszystkie iteratory i referencje (wskaźniki) do elementów kontenera
• Operacje usuwania ostatniego elementu - pop_back()
  • tracą ważność iterator past-the-end oraz iterator i referencje do usuwanego elementu
• Operacja usuwania pierwszego (ale nie ostatniego) elementu - pop_front()
  • unieważnia iteratory i referencje do usuwanego elementu
• Operacja usuwania ze środka deque’a - erase()
  • unieważnia wszystkie iteratory i referencje (wskaźniki) do elementów kontenera

std::list

• Jest kontenerem zoptymalizowanym do wstawiania lub usuwania elementów (stały czas)
• Posiada liniową złożoność obliczeniową znalezienia n-tego elementów
• Lista zapewnia iteratory dwukierunkowe.
• Plik nagłówkowy: <list>
  • brak iteratorów o dostępie swobodnym.
• Zaimplementowana została w postaci podwójnie łączonej listy (dwukierunkowej)

Definicja:

namespace std
{
    template <
        typename T,
        typename Allocator = std::allocator<T>
    > class list
    {
        //...
    };
}

std::list - wstawianie i usuwanie elementów

Elementy można dodawać następującymi metodami:

void list::push_back(const valueType &x)

wstawia x jako ostatni element w kontenerze

void list::push_front(const valueType &x)

wstawia x jako pierwszy element w kontenerze

iterator list::insert(iterator pos, const valueType &x)

wstawia x przed element p i zwraca iterator wskazujący na x

iterator list::erase(iterator p)

usuwa element wskazywany przez pos i zwraca iterator do elementu następnego (po usuniętym)

Podobnie jak wektor, od wersji C++11 mamy nowe metody wykorzystujące tworzenie obiektów „w miejscu”:

reference list::emplace_back(Args &&args)

reference list::emplace_front(Args &&args)

iterator list::emplace(const_iterator pos, Args &&args)

wstawiają elementy przekazując do konstruktora typu argumenty args

std::list<std::string> lst = { "..." };
lst.push_back("C++");
lst.push_front("Szkolenie");

auto pos = find(lst.begin(). lst.end(), "C++");
pos = lst.erase(pos);
lst.insert(pos, { "z", "programowania", "w" });

std::list - ważność iteratorów

Operacje wstawiania i usuwania elementów nie powodują unieważnienia wskaźników, referencji ani iteratorów do innych elementów. Unieważniane są iteratory, referencje i wskaźniki do usuwanych elementów.

std::list - odporność na wyjątki

Lista realizuje obsługę wyjątków w taki sposób, że niemal każda operacja kończy się powodzeniem, albo nie powoduje zmiany stanu kontenera. Nie jest zatem możliwe wystąpienie stanu pośredniego, w którym zakończona zostałaby tylko połowa operacji.

Lista oferuje najlepsze gwarancje bezpieczeństwa w przypadku zgłaszania sytuacji wyjątkowych.

std::list - metody specjalne

Zawiera metody zoptymalizowane pod kątem operacji na liście dwukierunkowej

void list::sort()

Sortuje elementy przechowywane na liście

void list::merge(list<T> &lst)

Łączy aktualną posortowaną listę z inną, również posortowaną listą. Elementy z listy x są usuwane (po wyjściu z funkcji lista lst jest pusta)

void list::reverse()

Odwraca kolejność elementów na liście

void list::unique()

Usuwa z listy sąsiadujące ze sobą duplikaty elementów

void list::remove(const T &value)

Usuwa z listy wszystkie wystąpienia podanej wartości

void list::remove_if(Predicate pred)

Usuwa wszystkie elementy, dla których wywołanie pred(item) zwraca true

void list::splice(Iterator where, list &lst)

Przenosi wszystkie elementy kontenera lst do kontenera *this na rzecz którego została wywołana metoda i umieszcza je przed pozycją iteratora where. Żaden z elementów nie jest kopiowany lub przenoszony (przepinane są węzły).

void list::splice(Iterator where, list &lst, const_iterator it)

Przenosi węzeł wskazywany iteratorem it do listy *this. Węzeł jest wpinany przed elementem wskazywanym iteratorem it

void list::splice(Iterator where, list &lst, const_iterator first, const_iterator last)

Przenosi węzły z zakresu [first, last) listy ``lst do listy *this. Węzły są wpinane przed elementem wskazywanym iteratorem it

Przykład

list<string> lst_1 = { 5, 2, 5, 1, 7 };
list<string> lst_2 = {3, 5, 8, 2, 23, 5 };

// sorting
lst_1.sort();
lst_2.sort();

// merging sorted lists
lst_1.merge(lst_2); // lst_1 = { 1, 2, 2, 3, 5, 5, 5, 5, 7, 8, 23 }
assert(lst_2.size() == 0);

// removing elements
lst_1.remove(5); // lst_1 = { 1, 2, 2, 3, 7, 8, 23 }

// moving nodes between lists
list<int> lst_3 = { 101, 202 };
lst_3.splice(lst_3.begin(), lst_1); // lst3 = { 1, 2, 2, 3, 7, 8, 23, 101, 202 }
assert(lst_1.size() == 0);

Kontenery asocjacyjne

Kontenery asocjacyjne

• zbiory - set<T>, multiset<T>
  • zbiory przechowujące klucze w kolejności określonej poprzez funktor porównujący (domyślnie less<T>)
  • set<T> przechowuje unikalne klucze
  • plik nagłówkowy: <set>
• mapy - map<K, T>, multimap<K, T>
  • słowniki - przechowują pary: klucz i mapowany na klucz obiekt
  • pary są przechowywane w kolejności określonej przez funktor porównujący wartości kluczy (domyślnie less<K>)
  • kontener std::map nie zezwala na przechowywanie duplikatów kluczy
  • plik nagłówkowy: <map>
• Operacje wstawiania, wyszukiwania i usuwania w kontenerach set i map mają złożoność logarytmiczną
• Kontenery asocjacyjne wykonują automatyczne sortowanie swoich elementów zgodnie z określonym kryterium porównywania kluczy

Strict weak ordering

Kryterium sortowania musi definiować tzw. „ścisłe uporządkowanie słabe” (strict weak ordering):

• Musi być antysymetryczne

  • Dla operatora < oznacza to: jeśli x < y jest prawdziwe, to y < x jest fałszywe

  -Dla predykatu op(): jeśli op(x, y) jest prawdziwe, to op(y, x) jest fałszywe

• Musi być przechodnie

  • Dla operatora < oznacza to: jeśli x < y jest prawdziwe oraz y < z jest prawdziwe, to x < z jest prawdziwe
  • Dla predykatu op(): jeśli op(x,  y) jest prawdziwe oraz op(y, z) jest prawdziwe, to op(x, z) jest prawdziwe

• Musi być niezwrotne

  • Dla operatora < oznacza to: x < x jest zawsze fałszywe
  • Dla predykatu op(): op(x, x) jest zawsze fałszywe

Równość a równoważność

Elementy e1 i e2 są równe, jeśli:

e1 == e2

Elementy e1 i e2 są równoważne, jeśli:

!(e1 < e2) && !(e2 < e1)

Równoważność można zinterpretować następująco:

• Jeśli e1 nie poprzedza w sekwencji e2 i jednocześnie e2 nie poprzedza e1.
• Ich relatywna pozycja w posortowanym ciągu jest taka sama (dwa obiekty trafią w to samo miejsce do posortowanej kolekcji).

Metody kontenerów asocjacyjnych

size_type count(const key_type &k)

Zwraca liczbę elementów o wartości k

size_type erase(const key_type &k)

Usuwa wszystkie elementy o kluczu równoważnym z k. Złożoność funkcji: log(N) + count

iterator erase(iterator pos)

iterator erase(iterator first, iterator last)

Usuwa element wskazywany przez iterator lub zakres elementów [first, last). Zwracany jest iterator do następnego elementu po usuniętym.

iterator find(const key_type &k)

Znajduje element równoważny z k i zwraca wskazujący na niego iterator. Złożoność: log(N)

pair<iterator, bool> insert(const value_type &x)

Wstawia element x. Jeżeli kontener pozwala na istnienie duplikatów kluczy, to funkcja zwraca iterator wskazujący na wstawiony element Jeżeli kontener wymaga unikalnych kluczy, to funkcja zwraca wartość pair<iterator, bool>, w której pierwszy element to iterator na wartość równoważną z x, a drugi to wartość logiczna określająca, czy element x został wstawiony, czy też istniał wcześniej w kontenerze

pair<iterator, bool> emplace(Args&&... args)

Wstawia element w miejscu, utworzony przy pomocy parametrów konstruktora args. Pozwala to omijać kopiowanie lub przenoszenie elementu do kontenera.

iterator emplace_hint(const_iterator hint, Args&&... args)

Wstawia element w miejscu, utworzony przy pomocy parametrów konstruktora args, w miejscu możliwie najbliższym pozycji hint.

iterator lower_bound(const Key &k)

zwraca iterator wskazujący na pierwszy element nie mniejszy niż klucz k

iterator upper_bound(const Key &k)

zwraca iterator wskazujący na pierwszy element, który jest większy od podanego klucza k

std::pair<iterator, iterator> equal_range(const Key &k)

zwraca zakres elementów równoważnych podanemu kluczowi - odpowiednik pair(lower_bound(k), upper_bound(k))

std::set

std::set - kontener asocjacyjny przechowujący klucze w porządku zgodnym z podanym kryterium porównywania

namespace std
{
    template <
        typename T,
        typename Compare = std::less<T>,
        typename Allocator = std::allocator<T>
    > class set { /*...*/ };
}

• Plik nagłówkowy: <set>
• Kontener zoptymalizowany dla operacji wstawiania, usuwania elementów oraz testowania, czy dany element jest przechowywany w kontenerze
• Implementacja - zrównoważone drzewo binarne bez duplikatów
• Zbiory implementują iteratory dwukierunkowe
• Jeśli nie zostanie podane żadne specjalne kryterium sortowania, użyty zostanie funktor less<T>, który wykorzystuje operator <

std::set - kryteria sortowania

Kryterium sortowania może zostać zdefiniowane na dwa sposoby:

1. Jako parametr wzorca

std::set<int, std::greater<int> > coll;

2. Jako parametr konstruktora

   • funkcja

     bool ptr_compare(int* x, int* y)
     {
         return *x > *y;
     }
     
     set<int*, bool (*)(int*, int*)> set_int( &ptr_compare );
     

   • std::function

     set<Gadget, std::function<bool(const Gadget&, const Gadget&)>>
         gadgets([](const Gadget& g1, const Gadget& g2) { return g1.id() < g2.id(); });
     
     gadgets.emplace(4, "AD1234");
     gadgets.insert(Gadget(1, "AB2323"));
     gadgets.emplace(7, "AA4235");
     
     for (const auto& g : gadgets)
         cout << g.id() << endl;
     

   • typ domknięcia

     auto comp = [](const unique_ptr<int>&a , const unique_ptr<int>& b) { return *a < *b; };
     
     set<unique_ptr<int>, decltype(comp)> numbers(comp);
     

std::set - wstawianie elementów

pair<iterator, bool> set::insert(const value_type &x)

wstawia element x do kontenera, jeśli kontener nie zawiera już klucza x. Zwraca obiekt pair<iterator, bool>, w którym składowa first zawiera iterator wskazujący na wartość równoważną x, a druga składowa second zawiera wartość bool, czy dany element został wstawiony, czy też nie.

std::set<int> set_one = { 6, 7, 8, 4 };

set_one.insert(18);
pair<set<int>::iterator, bool> result = set_one.insert(18);

if (result.second)
    std::cout << "element został wstawiony" << '\n'
else
    std::cout << "element nie został wstawiony" << '\n';

Od C++17 powyższy kod może zostać uproszczony z wykorzystaniem structured-bindings i formą instrukcji if z sekcją inicjalizacji:

std::set<int> set_one = { 6, 7, 8, 4 };

if (auto [pos, action_performed] = set_one.insert(18); action_performed)
    std::cout << "element został wstawiony" << '\n'
else
    std::cout << "element nie został wstawiony" << '\n';

for (const auto& key : set_one)
    std::cout << key << '\n';

pair<iterator, bool> set::emplace(Args&&... args)

wstawia nowy element do kontenera, konstruując go in-place*`` za pomocą przekazanych argumentów, jeśli nie istnieje już element równoważny

struct Person
{
    int id;
    std::string name;

    bool operator<(const Person& other) const
    {
        return std::tie(id, name) < std::tie(other.id, other.name);
    }
};

set<Person> people = { {5, "Adamski"}, {3, "Nowakowski"} };
people.emplace(4, "Nowak");

iterator set::emplace_hint(const_iterator hint, Args&&... args)

wstawia nowy element, konstruując go in-place jak najbliżej miejsca przed podpowiedzią hint. Jeśli wskazówka jest prawidłowa umożliwia osiągnięcie stałego, zamortyzowanego czasu wstawienia elementu

auto hint = people.end();
people.emplace_hint(hint, 9, "Anonim");

std::set - operacje wyszukiwania

Zbiory są zoptymalizowane pod kątem szybkiego wyszukiwania elementów, więc udostępniają one specjalne funkcje wyszukiwania.

std::multiset<int> data = {1, 2, 4, 4, 4, 5, 6 };

auto lb = data.lower_bound(3);
assert(*lb == 4);

auto ub = data.upper_bound(4);
assert(*ub == 5);

assert(distance(lb, ub) == 3);

auto [first, last] = data.equal_range(4);

assert(first == lb);
assert(last == ub);

Gdy w zbiorze nie ma określonego klucza metody lower_bound() i upper_bound() zwracają iterator wskazujący na pozycję umożliwiającą efektywne wstawienie elementu.

std::set<int> data = { 1, 2, 4, 5 };

auto lb = data.lower_bound(3);
auto ub = data.upper_bound(3);

assert(lb == ub);

data.insert(lb, 3); // constant amortized time of insertion

std::map

• Kontener (mapa) zarządza parami złożonymi z klucza i odpowiadającej mu wartości.
• Przechowuje elementy typu std::pair<const Key, T>

namespace std
{
    template<
        typename Key, typename T,
        typename Compare = std::less<Key>,
        typename Allocator = std::allocator<std::pair<const Key, T>>
    > class map
    {
        //...
    };
}

• Plik nagłówkowy: <map>
• Elementy są identyfikowane i wstawiane (porządkowane) za pomocą klucza
• Każdy klucz może wystąpić w kontenerze tylko raz - po wstawieniu nie można zmienić jego wartości
• Mapy implementują iteratory dwukierunkowe
• multimap<K, T> - odmiana mapy, w której dozwolone są duplikaty kluczy

std::map - kryterium porządkowania elementów

Tworzenie mapy z domyślnym kryterium sortowania: less<>

std::map<int, std::string> day_of_week;

Kryterium sortowania inne niż domyślne może zostać przekazane

1. Jako parametr wzorca

std::map<int, std::string, std::greater<int> > day_of_week_desc;

2. Jako parametr konstruktora (podobnie jak w std::set)

std::map - konstruktory

// (1) default constructor
map<string, int> map1;

// (2) constructor using pair of iterators
map<string, int> iter(map1.find("anything"), map1.end());

// (3) copy constructor
map<string, int> copied(map1);

// (4) move constructor //C++11
map<string, int> moved(move(map1));

// (5) initializer list //C++11
const map<string, int> dict = {
  {"one", 1},
  {"two", 2},
  {"three", 3}
};

std::map - wstawianie elementów

Wstawianie par klucz-wartość do mapy

1. Użycie składowej value_type

map<string, float> coll;
...
coll.insert(map<string, float>::value_type("sty", 32.33));

2. Użycie struktury pair<K, T>

coll.insert(pair<string, float>("jan", 32.33));
coll.insert(pair<const string, float>("jan", 32.33));
coll.insert(pair("feb"s, 33.22)); // since C++17

3. Użycie funkcji make_pair()

coll.insert(make_pair("sty", 32.33));

Przykład:

std::map<string, string> days_of_week = { {"Saturday", "Sobota" } };

days_of_week.insert(make_pair("Monday", "Poniedziałek"));
days_of_week.insert(pair<string, string>("Tuesday", "Wtorek"));
days_of_week.insert(pair("Friday"s, "Piątek"s));
days_of_week["Wednesday"] = "Środa";

if (auto[where, was_inserted] = days_of_week.insert(pair("Thursday"s, "Czwartek"s)); was_inserted)
{
    const auto& [key, value] = *where;
    std::cout << "New entry was inserted: " << key << " - " << value << '\n';
}
else
{
    std::cout << "Entry already exists in a dictionary...\n";
}

std::map - interfejs tablicy asocjacyjnej

Mapa umożliwia bezpośredni dostęp do elementów przy pomocy operatora []

T &operator[](const Key &key)

zwraca referencję do wartości elementu o kluczu równoważnym key wykonując wstawienie domyślnej wartości elementu jeśli podanego klucza nie ma w mapie

Instrukcja

std::map<std::string, float> constants;
constants["pi"] = 3.14;

jest przetwarzana następująco:

1. Przetwarzaj wyrażenie constants["pi"]:
   • jeśli element o kluczu równoważnym pi istnieje, wyrażenie zwraca referencję do tego elementu
   • jeśli nie istnieje klucz równoważny pi, wyrażenie automatycznie wstawia nowy element z łańcuchem pi jako klucz o wartości domyślnej i zwraca referencję do wstawionego elementu
2. Przypisz wartość 3.14

Od C++17 efektywniejszego wstawienia lub uaktualnienia elementu można użyć funkcji:

template<class M>
pair<iterator, bool> map::insert_or_assign(const key_type &k, M &&obj)

auto [pos, was_inserted] = constants.insert_or_assign("pi", 3.1415);
assert(was_inserted == false);

std::map - iteracja po elementach

Mapa map<Key, T> przechowuje obiekty w parach klucz-wartość, tworzonych za pomocą klasy pair<const Key, T>

Oba elementy pary pair są dostępne za pomocą składowych

• first - pierwszy element
• second - drugi element

Iteracja po mapie to iteracja po parach pair<Key, T> za pomocą iteratora:

template <typename Key, typename T>
void print_map(const map<Key, T>& m)
{
    typename map<Key, T>::const_iterator cit;
    cout << "[ ";
    for (cit = m.begin(); cit != m.end(); ++cit)
        cout << "(" << cit->first << " - " << cit->second << ") ";
    cout << "]" << endl;
}

Iteracja po mapie w C++11:

template <typename Key, typename T>
void print_map(const map<Key, T>& m)
{
    cout << "[ ";
    for (const auto& kv : m)
        cout << "(" << kv.first << " - " << kv.second << ") ";
    cout << "]" << endl;
}

Jeszcze prościej można iterować po elementach mapy w C++17 wykorzystując structured bindings:

template <typename Key, typename T>
void print_map(const map<Key, T>& m)
{
    cout << "[ ";
    for (const auto& [key, value] : m)
        cout << "(" << key << " - " << value << ") ";
    cout << "]" << endl;
}

Transfer węzłów (C++17)

C++17 rozszerza API zbiorów i map (z haszowaniem) o możliwość przepinania węzłów pomiędzy kontenerami.

• lepsza wydajność niż erase() i insert()

• aby przepiąć węzeł tylko typy klucza/wartości (oraz alokatora) muszą być zgodne ze sobą

  • kryteria porównań kluczy, funkcje haszujące mogą być różne
  • dozwolone jest przepinanie z kontenera nie zezwalającego na duplikaty do kontenera z duplikatami kluczy: np. set <-> multiset

• zdefiniowany jest typ węzła container::node_type

  • szczegółowa implementacja nie jest specyfikowana
  • składowa value() zwraca wartość dla zbiorów
  • składowe key() oraz mapped() są dostępne dla map
  • wspierana jest semantyka przenoszenia (np. typy move-only)

• nowe operacje w interfejsie kontenerów:

  • node_type extract(const_iterator pos);

    node_type extract(const key_type& key);
  • merge(std::set& source);

    merge(std::multiset& source);
  • insert_return_type insert(node_type&& nh);

    iterator insert(const_iterator hint, node_type&& nh);

Przykład przepięcia węzłów między kontenerami asocjacyjnymi:

std::map<int, std::string> src{{1, "one"}, {2, "two"}, {3, "three"}};
std::map<int, std::string> dst{{3, "THREE"}};

auto pos_src = src.find(1);
dst.insert(src.extract(pos_src)); // splice using iterator

dst.insert(src.extract(2)); // splice using key value

auto result = dst.insert(src.extract(3));

// result.position == next(next(dst.begin()))
// result.inserted == false
// result.node.key() == 3
// result.node.mapped() == "three"

// instead the last statement
auto [pos, success, node] = dst.insert(src.extract(2)); // splice using key value

// pos == next(next(dst.begin()))
// success == false
// node.key() == 3
// node.mapped() == "three"

Kontenery haszujące

Kontenery haszujące gwarantują średnio stałą złożoność czasową operacji wyszukiwania, wstawiania oraz usuwania. Elementy w kontenerze haszującym nie są posortowane, ale są przechowywane w tzw. kubełkach (buckets). Element trafia do określonego kubełka na podstawie wartości skrótu (hash value) obliczanej dla elementu.

C++11 wprowadza następujące kontenery haszujące

• zbiory: unordered_set i unordered_multiset
• mapy: unordered_map i unordered_multimap

std::unordered_set

• Plik nagłówkowy <unordered_set>

namespace std
{
    template<
        typename Key,
        typename Hash = std::hash<Key>,
        typename Pred = std::equal_to<Key>,
        typename Alloc = std::allocator<Key>
    > class unordered_set
    {
        //...
     };
}

• Zbiór haszujący akceptujący duplikaty kluczy: unordered_multiset
• Kontener unordered_set wymaga podania jako parametrów szablonu:
  • Funktora lub funkcji haszującej klucze - domyślnie std::hash<T>
  • Predykatu równości elementów - domyślnie std::equal_to<T>

Ważne

Dla kluczy typu Key, które są sobie równe k1 == k2, musi być spełniona równość std::hash<Key>(k1) == std::hash<Key>(k2).

Metody dostępowe dla kubełków

Kontenery z haszowaniem dostarczają zbiór metod, które umożliwiają zarządzanie strukturą kubełków w kontenerze.

size_type bucket_count() const

Ilość kubełków

size_type max_bucket_count() const

Górna granica ilości kubełków

size_type bucket_size(size_type n)

Rozmiar kubełka numer n

size_type bucket(const key_type &k)

Indeks kubełka zawierającego klucz k

float load_factor() const

Średnia ilość elementów w kubełku

float max_load_factor() const

Bieżąca maksymalna ilość elementów w kubełku

float max_load_factor(float ml)

Zmiana poziomu zapełnienia kubełków (ml jest traktowane jako podpowiedź)

void rehash(size_type n)

Zmienia ilość kubełków na co najmniej n

Przykład

#include <random>
#include <unordered_set>

std::random_device rd;
std::default_random_engine rnd_engine{rd};
std::uniform_int_distribution<> rnd_distr{rnd_engine};

std::unordered_set<int> uset1;

for(size_t i = 0; i < 1000; ++i)
    uset1.insert(rnd_distr());

cout << "\nIlosc wystapien elementu o wartosci 50: "
     << uset1.count(50) << endl;

std::unordered_set<int>::iterator where = uset1.find(50);
if (where != uset1.end())
    cout << "Znaleziony element: " << *where << endl;

std::unordered_map

• Plik nagłówkowy: <unordered_map>

namespace std
{
    template
    <
        typename Key, class T,
        typename Hash = std::hash<Key>,
        typename Pred = std::equal_to<Key>,
        typename Alloc = std::allocator<std::pair<const Key, T> >
    > class unordered_map
    {
        //...
    };
}

• Jako parametry szablonu klasy przekazywane są typy:
  • Key - klucz
  • T - mapowany typ
  • Hash - funktor wyliczający skrót dla klucza
  • Pred - predykat porównujący klucze
• Mapa haszująca dopuszczająca duplikaty kluczy: unordered_multimap

Przykład:

std::unordered_map<int, string> umap1 = { { 7, "nd"}, {6, "sob"} };

umap1.insert(pair<int, string>(1, "pon"));
umap1.insert(make_pair(2, "wt"));
umap1.insert(std::unordered_map<int, string>::value_type(3, "sr"));
umap1[5] = "pt";

auto where = umap1.find(3);
if (where != umap1.end())
    std::cout << "Znaleziono wpis: " << where->first << " - "
         << where->second << std::endl;

std::cout << "6: " << umap1[6] << std::endl;

std::hash

Struktura szablonowa std::hash definiuje obiekt funkcyjny, który umożliwia wyliczenie wartości skrótu.

Operator wywołania funkcji spełnia poniższe wymagania:

• Akceptuje argument typu Key
• Zwraca wartość typu size_t
• Nie rzuca wyjątków
• Dla dwóch wartości k1 i k2, które są sobie równe std::hash<Key>()(k1) == std::hash<Key>()(k2)
• Dla dwóch wartości, które nie są sobie równe, prawdopodobieństwo, że wyliczona dla nich zostanie taka sama wartość skrótu powinna być bardzo mała.

Standard specjalizuje szablon std::hash dla:

• wszystkich typów liczbowych
• typów wskaźnikowych: T*, std::unique_ptr oraz std::shared_ptr
• typów łańcuchowych
• std::bitset
• std::vector<bool>
• std::thread::id
• std::type_index

Tworzenie funkcji haszujących

Jeżeli typem klucza kontenera z haszowaniem jest typ tworzony przez użytkownika, to należy dostarczyć jako parametr typu kontenera specjalizowaną funkcję haszującą. Może ty zostać zrealizowane na dwa sposoby:

1. Klasa funktora.

   struct Person
   {
       std::string first_name;
       std::string last_name;
   
       bool operator==(const Person& other) const
       {
           return std::tie(first_name, last_name) == std::tie(other.first_name, other.last_name);
       }
   };
   
   template <typename T>
   struct HashPerson
   {
       size_t operator()(const Person& p) const
       {
   
           std::size_t h1 = std::hash<std::string>()(p.first_name);
           std::size_t h2 = std::hash<std::string>()(p.last_name);
           return h1 ^ (h2 << 1); // or use boost::hash_combine
       }
   };
   
   std::unordered_set<Person, HashPerson> people;
   

2. Specjalizacja klasy std::hash.

   namespace std
   {
       template<> struct hash<Person>
       {
           typedef Person argument_type;
           typedef std::size_t result_type;
   
           result_type operator()(argument_type const& p) const
           {
               result_type const h1 ( std::hash<std::string>()(p.first_name) );
               result_type const h2 ( std::hash<std::string>()(p.last_name) );
               return h1 ^ (h2 << 1); // or use boost::hash_combine
           }
       };
   }
   
   std::unordered_set<Person> people;