# Bekanta dig med nya flat containers i C++

14 augusti 2025 | https://www.ribomation.se/blog/2025/bekanta-dig-med-nya-flat-containers-i-c++/

C++23 introducerar två nya associativa containrar i standardbiblioteket:  
`std::flat_set` och `std::flat_map`. Dessa har samma API som `std::set` och `std::map`, men är **inte** implementerade som balanserade binära sökträd, utan som sorterade sekvenscontainrar (`std::vector` under huven). Detta gör att de kan vara betydligt snabbare för vissa användningsfall, framför allt när datamängden är relativt liten och när man gör många sökningar men få insättningar/borttagningar.

### Intern representation

En `std::flat_set<Key>` är i grunden en sorterad `std::vector<Key>`. En `std::flat_map<Key, Value>` är i grunden en sorterad `std::vector<std::pair<Key, Value>>`.

Eftersom elementen är lagrade i ett sammanhängande minnesblock ger detta mycket bra cache-lokalitet och snabba sekventiella traverseringar. Sökningsoperationer använder binärsökning (_O(log n)_), medan insättning och borttagning i mitten är dyra (_O(n)_) eftersom elementen måste flyttas.

   ![flat\_set och flat\_map är sorterade vektorer](/blog/2025/bekanta-dig-med-nya-flat-containers-i-c++/flat-containers-1300w.jpeg "flat_set och flat_map är sorterade vektorer")

### `std::flat_set<Key, Compare>`

API:t är nästan identiskt med `std::set`, vilket gör övergången enkel.

```cpp
#include <flat_set>
#include <print>

int main() {
    auto fs = std::flat_set<int>{1, 4, 3, 2, 5};
    std::println("init: {}", fs);

    fs.insert(0);
    fs.insert(3); // duplicat ignoreras
    std::println("after insert: {}", fs);

    if (fs.contains(4)) std::println("found 4");
}
```

```shell
init: {1, 2, 3, 4, 5}
after insert: {0, 1, 2, 3, 4, 5}
found 4
```

Notera att insättningar alltid placerar elementet på rätt position för att behålla sorteringen.

Definitionen av denna container ser ut så här (hämtat från cppreference.com)

```cpp
template<
    typename Key,
    typename Compare = std::less<Key>,
    typename KeyContainer = std::vector<Key>
> class flat_set;
```

Här kan vi se att default key-container är std::vector, men att den är utbytbar. Det finns inga övriga containrar i biblioteket du kan använda, utan detta är till för att man har någon egenutvecklad container att plugga in i flat\_set.

### `std::flat_map<Key, Value, Compare>`

En flat\_map fungerar som en vanlig map, men är internt sorterad på nycklar i en vektor.

```cpp
#include <flat_map>
#include <string>
#include <print>
using namespace std::string_literals;

int main() {
    auto fm = std::flat_map<std::string, int>{
        {"Anna"s, 42}, {"Berit"s, 37}
    };

    fm["Carin"s] = 50;  // skapar nytt element
    fm["Anna"s] += 1;   // uppdaterar befintligt

    for (auto&& [name, age] : fm)
        std::println("{} -> {}", name, age);
}
```

```shell
Anna -> 43
Berit -> 37
Carin -> 50
```

Precis som för std::map kan du använda at() för bounds-checkad åtkomst.

Definitionen av denna container ser ut så här (hämtat från cppreference.com)

```cpp
template<
    typename Key,
    typename Value,
    typename Compare = std::less<Key>,
    typename KeyContainer = std::vector<Key>,
    typename ValueContainer = std::vector<Value>
> class flat_map;
```

Här ser vi att flat-map innehåller två stycken vector, en för nycklar och en för värden. Den sistnämnda lagrar värdena i samma indexordning som nycklarna.

```text
KeyContainer:    [ "Anna",   "Berit",   "Carin" ]
ValueContainer:  [  42,        37,        50    ]
```

På så vis behöver inte flat\_map lagra std::pair<Key, Value> som en vanlig std::map gör. Detta sparar minne (ingen padding mellan key och value, ingen pekarstruktur) och kan ge bättre cachelokalitet.

Som standard är båda containrarna std::vector, men mallparametern gör det möjligt att byta ut dem mot något annat som uppfyller de nödvändiga krav (t.ex. std::deque om man vill ha annorlunda insättningsbeteende). Exempel: Om du av någon anledning vill använda std::deque för värdena men behålla std::vector för nycklarna:

```cpp
#include <flat_map>
#include <deque>
#include <string>

int main() {
    using std::string;
    using std::less;
    using std::vector;
    using std::deque;
    auto tbl = std::flat_map<string, int,                           //key & value types
                             less<std::string>,                     //comparator
                             vector<std::string>, deque<int>>{};    //key & value storage
}
```

   ![flat\_map interna vectors](/blog/2025/bekanta-dig-med-nya-flat-containers-i-c++/flat-map-internals-1300w.jpeg "flat_map interna vectors")

Prestandaegenskaper
-------------------

*   Sökning: O(log n), snabb tack vare binärsökning och cache-vänlig datastruktur.
*   Iteration: mycket snabb (sekventiell åtkomst i vektor).
*   Insättning/borttagning: O(n), då element måste flyttas för att behålla sorteringsordningen.

Detta innebär att flat\_set och flat\_map är särskilt bra när:

*   Datamängden är liten till medelstor.
*   Antalet ändringar är få jämfört med antalet uppslagningar/iterationer.
*   Du vill ha bättre cache-lokalitet än med trädstrukturer.

Prestandajämförelse
-------------------

```cpp
#include <chrono>
#include <print>
#include <random>
#include <string>
#include <map>
#include <unordered_map>
#include <flat_map>
namespace cr = std::chrono;

template <typename Container>
void benchmark(std::string const& type, unsigned N) {
    auto r = std::default_random_engine{std::random_device{}()};
    auto U = std::uniform_int_distribution<unsigned>{1, N * 10U};

    auto target = Container{};
    {
        auto start = std::chrono::steady_clock::now();
        for (auto i = 0U; i < N; ++i) target[U(r)] = i;
        auto stop = std::chrono::steady_clock::now();
        auto elapsed = cr::duration_cast<cr::milliseconds>(stop - start);
        std::println("{} insert  : {:4} ms", type, elapsed.count());
    }
    {
        auto start = std::chrono::steady_clock::now();
        for (auto i = 0U; i < N; ++i) target.contains(U(r));
        auto stop = std::chrono::steady_clock::now();
        auto elapsed = cr::duration_cast<cr::milliseconds>(stop - start);
        std::println("{} lookup  : {:4} ms", type, elapsed.count());
    }
    {
        auto start = std::chrono::steady_clock::now();
        for (auto e : target) {
            auto _ = e.first + e.second;
        }
        auto stop = std::chrono::steady_clock::now();
        auto elapsed = cr::duration_cast<cr::milliseconds>(stop - start);
        std::println("{} traverse: {:4} ms", type, elapsed.count());
    }
}

int main() {
    auto const N = 1'000'000U;
    benchmark< std::map<int, int> >          ("binary-tree  ", N);
    std::println("----");
    benchmark< std::unordered_map<int, int> >("hash-table   ", N);
    std::println("----");
    benchmark< std::flat_map<int, int> >     ("single-block ", N);
}
```

Typiskt resultat (kan variera beroende på dataset):

```shell
binary-tree   insert  : 1350 ms
binary-tree   lookup  : 1618 ms
binary-tree   traverse:  118 ms
----
hash-table    insert  :  779 ms
hash-table    lookup  :  340 ms
hash-table    traverse:   61 ms
----
single-block  insert  : 56754 ms
single-block  lookup  :  561 ms
single-block  traverse:   21 ms

Process finished with exit code 0
```

Här kan du se att flat-map är pinsamt långsam för insättning av osorterad data, men den snabbaste för traversering.

Sammanfattning
--------------

#### Fördelar

*   Mycket snabb iteration och sökning tack vare sekventiell lagring.
*   Låg minnesanvändning jämfört med pekarbaserade träd.
*   API-kompatibel med `std::set` och `std::map`.

#### Nackdelar

*   Långsamma insättningar/borttagningar i mitten.
*   Ingen stabil iterator vid insättning/borttagning (p.g.a. `std::vector` under huven).

#### När ska man välja dem?

*   När datastrukturen är **liten till medelstor** och du har **få ändringar** men **många sökningar**.
*   När cache-prestanda är viktig.
*   När du enkelt vill byta från tree container till något snabbare för iteration.

* * *

### Jämförelse: Tree containers vs Hash-table containers vs Flat containers

Egenskap

`std::set` / `std::map`

`std::unordered_set` / `std::unordered_map`

`std::flat_set` / `std::flat_map`

Intern struktur

Balanserat binärt sökträd

Hash-tabell

Sorterad `std::vector`

Sorteringsordning

Ja

Nej

Ja

Sökning

O(log n)

O(1) genomsnitt / O(n) värsta fall

O(log n)

Iteration

Snabb (träd-traversering)

Snabb men osorterad

Mycket snabb (sekventiell åtkomst)

Insättning/borttagning

O(log n)

O(1) genomsnitt / O(n) värsta fall

O(n)

Minnesåtgång

Medel (pekare, noder)

Högre (buckets + element)

Låg (contiguous storage)

Stabilitet iterators

Hög

Hög vid insättning, låg vid rehash

Låg vid insättning/borttagning

Nyckelkrav

`<`\-operator (eller Compare)

Hash-funktion + `==`

`<`\-operator (eller Compare)

Passar bäst för

Behov av sorterad data

Snabb uppslagning utan sortering

Små/medelstora dataset med få ändringar och många läsningar

   ![Jämförelse mellan de tre container familjerna](/blog/2025/bekanta-dig-med-nya-flat-containers-i-c++/container-internals-1299w.jpeg "Jämförelse mellan de tre container familjerna")

Med `std::flat_set` och `std::flat_map` får du som C++-programmerare ytterligare ett par specialiserade verktyg, som fyller gapet mellan snabba sekvenscontainrar och mer flexibla men långsammare trädstrukturer.