Adaptory kontenerów

std::stack, std::queue i std::priority_queue to adaptory kontenerów. Standard używa słowa "adaptor", nie "adapter", ale chodzi o ten sam pomysł. Każdy z nich bierze istniejący kontener sekwencyjny i wystawia węższy interfejs z innym kontraktem.

Kształt

Adaptor kontenera posiada kontener bazowy i przekazuje niewielki zestaw operacji. Nie dziedziczy po kontenerze i nie wystawia jego iteratorów ani reszty interfejsu.

#include <deque>
#include <stack>
#include <vector>

std::stack<int> stack;                  // domyślnie std::deque<int>
std::stack<int, std::vector<int>> fast; // std::vector<int>

Domyślnym kontenerem jest std::deque<T>. Możesz podać inny jako drugi argument szablonu, jeśli spełnia wymagania adaptora.

Stos zbudowany ręcznie

Standardowy std::stack jest dobrym modelem dla własnych adapterów. Opakowuje kontener, wystawia tylko operacje sensowne dla stosu i pozwala wybrać sposób przechowywania.

#include <cstddef>
#include <deque>
#include <utility>

template<typename T, typename Container = std::deque<T>>
class Stack {
public:
    void push(const T& value) {
        data_.push_back(value);
    }

    void push(T&& value) {
        data_.push_back(std::move(value));
    }

    void pop() {
        data_.pop_back();
    }

    T& top() {
        return data_.back();
    }

    const T& top() const {
        return data_.back();
    }

    bool empty() const {
        return data_.empty();
    }

    std::size_t size() const {
        return data_.size();
    }

private:
    Container data_;
};

Użycie wygląda tak samo jak ze standardowym typem:

Stack<int> values;
values.push(1);
values.push(2);
values.push(3);

while (!values.empty()) {
    std::cout << values.top() << ' ';
    values.pop();
}

Wynik:

3 2 1

Dlaczego nie dziedziczyć z kontenera

Dziedziczenie po std::vector wygląda na krótsze, ale wystawia cały interfejs wektora:

class BadStack : public std::vector<int> {
public:
    void push(int value) { push_back(value); }
    int pop() { int value = back(); pop_back(); return value; }
};

Klient może teraz wywołać insert, erase, operator[] albo pobrać iteratory i złamać niezmiennik stosu. Adapter przestał cokolwiek adaptować. To zwykły wektor z dwiema dodatkowymi metodami. Składanie pozwala ten niezmiennik egzekwować.

Trzy standardowe adaptory

std::stack daje dostęp typu last in, first out. Potrzebuje back, push_back i pop_back. Domyślny jest std::deque, bo rośnie na obu końcach i rzadziej unieważnia referencje niż wektor.

std::queue daje dostęp typu first in, first out. Potrzebuje front, back, push_back i pop_front. Znowu domyślny jest std::deque. std::list też się nadaje.

std::priority_queue domyślnie trzyma największy element na górze. Potrzebuje dostępu swobodnego, front, push_back, pop_back i operacji kopca. Domyślny jest std::vector, a własny komparator zmienia kolejność:

#include <functional>
#include <queue>
#include <vector>

std::priority_queue<int> max_heap;
std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;

Własny adaptor kontenera

Trzymaj opakowanie cienkie, a kontrakt jawny:

• przechowuj kontener przez wartość, chyba że masz powód, żeby go pożyczać,
• przyjmuj kontener jako parametr szablonu z sensowną wartością domyślną,
• wystawiaj tylko operacje, które zachowują niezmiennik adaptora,
• nie rozdawaj iteratorów, chyba że adaptowany interfejs naprawdę ich potrzebuje,
• opisz, co się dzieje, gdy kontener rzuci wyjątek, zwłaszcza jeśli adaptor trzyma blokadę.

Ostatni punkt ma znaczenie, gdy adaptor robi więcej niż przekazywanie wywołań. Bezpieczna wątkowo kolejka nie może trzymać mutexa przez wywołanie, które może blokować albo rzucić wyjątek, bez przemyślenia własności i kolejności blokad.

Kiedy używać adaptora kontenera

Używaj go, gdy istniejący kontener ma potrzebne przechowywanie, ale interfejs jest zbyt szeroki. Stos, kolejka albo bufor o ograniczonym rozmiarze nie powinny pozwalać usuwać elementów ze środka ani przechodzić po całym magazynie. Adapter to uniemożliwia.

Unikaj go, gdy klienci potrzebują pełnego interfejsu kontenera. Opakowanie wektora w klasę, która wystawia begin, end, operator[], insert i erase, daje koszt opakowania bez żadnego ograniczenia. Użyj kontenera bezpośrednio.

Podsumowanie

Adaptory kontenerów to adaptery obiektowe z semantyką wartości. Posiadają kontener, przekazują niewielki zestaw operacji i ukrywają resztę. Standardowe stos, kolejka i kolejka priorytetowa są dobrymi wzorami dla własnych opakowań, bo pokazują, gdzie się zatrzymać: wystawiaj kontrakt, nie magazyn.