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.

std::flat_set<Key, Compare>

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

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

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)

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.

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

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)

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.

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:

#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
}

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

#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):

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

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.