Så här använder du adapter-containrar i C++

Containrar i STL tillhör en av två kategorier antingen sekvens- eller associativa containrar. Men det finns också en tredje kategori: adapter-containrar.
En adapter fungerar som ett lager ovanpå en annan container, och begränsar åtkomsten till elementen så att de beter sig som en stack, en kö eller en prioritetskö. I min förra artikel beskrev jag det senaste tillägget av adaptrar som kom i C++23; flat-containers. I denna tar jag upp de ursprungliga adaptrarna.

Gemensamt för adapter-containrarna är att de använder en underliggande sekvenscontainer (vanligtvis std::deque eller std::vector) och tillhandahåller ett mer specialiserat API. En adapter-container:

• Har ingen egen datastruktur utan bygger på en existerande container.
• Begränsar API:t till en viss åtkomstmodell (t.ex. LIFO eller FIFO).
• Tar container-typen som en template-parameter.

std::stack<T, Container>

En stack är en LIFO-struktur (Last In, First Out). Stackar används när du behöver tillfällig lagring där ordningen är omvänd mot insättningen, t.ex., vid rekursion eller text-tolkning. Så här ser definitionen av std::stack ut (hämtad från cppreference.com).

template<typename T, typename Container = std::deque<T>>
class stack;

Endast tre operationer är centrala, vid användning av denna adapter container:

• push() – lägg på toppen
• pop() – ta bort från toppen
• top() - returnerar en referens till översta elementet

Utöver det finns det några till som är av intresse

• size() / empty() - storleks info
• emplace() - som push, men tar konstruktor-argument och initierar elementen direkt på plats internt
• push_range() - tar ett container objekt och utför push på respektive element

Här följer ett enkelt användningsexempel. Notera att precis som för övriga STL containrar, så gäller att uttag av ett element görs i två steg; peka på element (top) och sen tag bort det (pop).

#include <stack>
#include <print>

int main() {
    auto s = std::stack<int>{};
    s.push(1);
    s.push(2);
    s.push(3);

    for (; not s.empty(); s.pop()) {
        std::println("top = {}", s.top());
    }
}

Som standard används en deque som underliggande container. Vill man ha en annan, som t.ex., en dubbel-länkad lista, så bifogas denna som template-parameter nummer 2. Kraven på en dylik container är att den måste vara en sekvens-container och ha metoderna

• back()
• push_back()
• pop_back()

#include <stack>
#include <list>

int main() {
    auto s = std::stack<int, std::list<int>>{};
    //...
}

std::queue<T, Container>

En kö är en FIFO-struktur (First In, First Out). Köer används ofta i scheduleringsproblem, meddelandeköer och buffertar. Så här ser definitionen av std::queue ut (hämtad från cppreference.com).

template<typename T, typename Container = std::deque<T>> 
class queue;

Endast fyra operationer är centrala, vid användning av denna adapter-container:

• push() – lägg till i slutet
• pop() – ta bort från början
• front() - returnerar en referens till första elementet
• back() – returnerar en referens till sista elementet

Utöver det finns det några till som är av intresse

• size() / empty() - storleks info
• emplace() - som push, men tar konstruktor-argument och initierar elementen direkt på plats internt
• push_range() - tar ett container objekt och utför push på respektive element

#include <queue>
#include <print>

int main() {
    auto q = std::queue<int>{};
    q.push(10);
    q.push(20);
    q.push(30);

    for (; not s.empty(); s.pop()) {
        std::println("front = {}", s.front());
    }
}

Som standard används även för denna, en deque som underliggande container. Vill man ha en annan, som t.ex., en dubbel-länkad lista, så bifogas denna som template-parameter nummer 2. Kraven på en dylik container är liknande som för stack att den måste vara en sekvens-container och ha metoderna

• front()
• back()
• push_back()
• pop_front()

#include <queue>
#include <list>

int main() {
    auto s = std::queue<int, std::list<int>>{};
    //...
}

std::priority_queue<T, Container, Compare>

En prioritetskö är en variant på queue där det alltid är det största (eller minsta) elementet som ligger först. Analogt med LIFO och FIFO, så är en prioritetskö en PIFO-struktur (Priority In, First Out). Så här ser definitionen av std::priority_queue ut (hämtad från cppreference.com).

template<
    typename T,
    typename Container = std::vector<T>,
    typename Compare   = std::less<typename Container::value_type>
> class priority_queue;

Endast tre operationer är centrala, vid användning av denna adapter-container:

• push() – sätt in ett element och sortera containern, så att elementet hamnar på rätt plats i prioritetsordning
• pop() – ta bort elementet i början av kön
• top() - returnerar en referens till elementet i början av kön

Utöver det finns det några till som är av intresse

• size() / empty() - storleks info
• emplace() - som push, men tar konstruktor-argument och initierar elementen direkt på plats internt
• push_range() - tar ett container objekt och utför push på respektive element

#include <queue>
#include <print>

int main() {
    auto q = std::priority_queue<int>{};
    q.push(10);
    q.push(20);
    q.push(30);

    for (; not s.empty(); s.pop()) {
        std::println("top = {}", s.top());
    }
}

Som standard används en vector som underliggande container. Vill man ha en annan, som t.ex., en deque, så bifogas denna som template-parameter nummer 2. Kraven på en dylik container är liknande som för övriga adaptrar att den måste vara en sekvens-container som tillhandahåller en random-access iterator (utesluter std::list), samt ha metoderna

• front()
• push_back()
• pop_back()

Prioritetsordningen är fallande eftersom std::less är standard, men kan enkelt ändras till att vara stigande genom att plugga in std::greater, som template-parameter nummer 3.

#include <queue>
#include <print>

int main() {
    auto q = std::priority_queue<int, std::deque<int>, std::greater<int>>{};
    //...   
}    

Här visar jag ett exempel en prioritetskö med konto-objekt och att de är sorterade i fallande ordningsföljd med avseende på saldo.

#include <print>
#include <queue>
#include "account.hxx"

int main() {
    auto q = std::priority_queue<Account, std::vector<Account>, order_by_balance>{};

    for (auto k = 0; k < 10; ++k) {
        auto a = mk_account();
        q.push(a);
    }

    for (; not q.empty(); q.pop()) {
        std::println("<{}, {}> ", q.top().accno, q.top().balance);
    }
}

<BXBZ-521-5077, 1321>
<VZND-653-7299, 998>
<ADIH-139-8283, 955>
<CEJP-318-3652, 923>
<YATB-643-4952, 846>
<ZVKQ-602-4944, 653>
<RYTC-596-3827, 597>
<BIOM-735-3230, 397>
<MHCD-626-2726, 266>
<PMCO-470-8112, -181>

Process finished with exit code 0

Klassen Account med tillhörande funktioner ser ut så här

#pragma once
#include <random>
#include <string>
#include <sstream>
using std::string;

struct Account {
    string  accno;
    int balance;
    Account(string a, int b) : accno{std::move(a)}, balance{b} {}
};

struct order_by_balance {
    bool operator()(Account const& lhs, Account const& rhs) const {
        return lhs.balance < rhs.balance;
    }
};

inline auto mk_account() -> Account {
    static auto r = std::default_random_engine{997};
    auto digit  = std::uniform_int_distribution{'0', '9'};
    auto letter = std::uniform_int_distribution{'A', 'Z'};
    auto amount = std::normal_distribution{1000.0F, 500.0F};

    auto buf = std::ostringstream{};
    for (auto k = 1; k <= 4; ++k) buf << letter(r);
    buf << "-";
    for (auto k = 1; k <= 3; ++k) buf << digit(r);
    buf << "-";
    for (auto k = 1; k <= 4; ++k) buf << digit(r);

    auto accno   = buf.str();
    auto balance = static_cast<int>(amount(r));
    return {accno, balance};
}

Internt använder priority_queue en så kallad heap. Det är en datastruktur som utgörs av ett implicit binärt sökträd. Med implicit, avses här att elementen ligger i en vector och är organiserade på så sätt att om index för en viss node är k, så är index för vänster child-node 2k och höger child-node 2k+1. Samt, att parent-node för index k är k/2. Detta förutsätter att root-node ligger på index=1. Finessen är att dessa node-operationer kan uttryckas som bitwise-shift operationer och är därför kolossalt snabba.

• 2 * k --> k << 1
• 2 * k + 1 --> (k << 1) | 1
• k / 2 --> k >> 1

Vi kan realisera programmet ovan utan std::priority_queue, men i termer av std::vector och std::push_heap/std::pop_heap.

#include <print>
#include <vector>
#include <algorithm>
#include "account.hxx"

int main() {
    auto q = std::vector<Account>{};

    for (auto k = 0; k < 10; ++k) {
        auto a = mk_account();
        q.push_back(a);
        std::push_heap(q.begin(), q.end(), order_by_balance{});
    }

    for (; not q.empty(); q.pop_back()) {
        std::pop_heap(q.begin(), q.end(), order_by_balance{});
        std::println("<{}, {}> ", q.back().accno, q.back().balance);
    }
}

I båda fallen blir utskriften enligt nedan (jag använder samma init-seed för slumptals-generatorn r)

<BXBZ-521-5077, 1321>
<VZND-653-7299, 998>
<ADIH-139-8283, 955>
<CEJP-318-3652, 923>
<YATB-643-4952, 846>
<ZVKQ-602-4944, 653>
<RYTC-596-3827, 597>
<BIOM-735-3230, 397>
<MHCD-626-2726, 266>
<PMCO-470-8112, -181>

Process finished with exit code 0

Prestanda och egenskaper

Eftersom adapter-containrar bygger på andra containrar, är prestandan beroende av den underliggande typen. Vanligast används std::deque som ger:

• push / pop i O(1)
• top / front / back i O(1)
• För priority_queue: insättning och borttagning i O(log n) tack vare heap-strukturen.

Sammanfattning

Adapter-containrarna i STL (stack, queue, priority_queue) är enkla men kraftfulla byggstenar. De ger snabba och specialiserade åtkomstmönster ovanpå redan befintliga containrar. När du behöver en klassisk datastruktur är de ett självklart val, och tack vare deras standardiserade API slipper du implementera dem från grunden.