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

16 augusti 2025 | https://www.ribomation.se/blog/2025/sa-har-anvander-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).

```cpp
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_).

```cpp
#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()

```cpp
#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).

```cpp
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

```cpp
#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()

```cpp
#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).

```cpp
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

```cpp
#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.

```cpp
#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.

```cpp
#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);
    }
}
```

```shell
<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

```cpp
#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.

```cpp
#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_)

```shell
<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.

Egenskap

`std::stack` (LIFO)

`std::queue` (FIFO)

`std::priority_queue` (Heap)

Åtkomst

Senast insatta

Först insatta

Största/minsta elementet

Intern struktur

`deque` / `vector`

`deque` / `list`

`vector` + heap-algoritmer

push/pop-komplexitet

O(1)

O(1)

O(log n)

top/front/back

O(1)

O(1)

O(1)

Sorteringsordning

Nej

Nej

Delvis (heap)

Passar bäst för

Rekursion, parsing

Buffertar, scheduler

Prioriterade jobb, algoritmer

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.