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:

Jako parametr wzorca

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

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

Jako parametr wzorca

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

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

Użycie składowej value_type

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

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

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:

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
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"