# Så här använder du STL tree containers

28 juli 2025 | https://www.ribomation.se/blog/2025/sa-har-anvander-du-stl-tree-containers/

C++ biblioteket har två typer av associativa containrar; _set_ respektive _map_. Dessa realiseras på några olika sätt. I denna artikel kommer jag beskriva `std::set` och `std::map`, som realiseras internt av binära sökträd, vilket är länkade strukturer. Jag går igenom typiska användnings-exempel, samt beskriver översiktligt hur dessa containrar är implementerade. Detta är del 1 av 2.

En associativ container karakteriseras av att element adresseras med ett nyckelelement (key). För _set_ så utgörs dataelementet av nyckeln själv, medan för map så paras nyckeln ihop med ett datavärde (value).

  ![Associative container](/blog/2025/sa-har-anvander-du-stl-tree-containers/associative-containers-1300w.png "Associative container")

### Binärt Sökträd

Gemensamt för `std::set` och `std::map` är att de implementeras som ett balanserat binärt sökträd; mer exact som ett _red-black tree_. C++ standarden föreskriver inte en speciell data-struktur, men alla de stora toolchain (kompilator-) leverantörerna använder denna.

  ![Red-Black tree](/blog/2025/sa-har-anvander-du-stl-tree-containers/red-black-tree-1300w.png "Red-Black tree")

Givet en nod och dess nyckel, så finns alla nycklar mindre än denna i vänster delträd och alla nycklar större än nodens nyckel i dess hägra delträd. Sedan upprepas detta rekursivt. Det här innebär att alla nycklar ligger i sorterad ordningsföljd och vid iteration över alla element så kommer de ut sorterade.

Vid insättning av samma nyckel flera gånger, så är det bara den första som genomförs och övriga insättningar ignoreras. Är det som så att du verkligen behöver multipla lika nycklar, så finns det `std::multiset` respektive `std::multimap`.

Vid insättning så allokeras en link-node, datavärdet stoppas in och noden länkas in i trädet, samt vid behov så balanseras trädet om. Nodens struktur är nästan densamma för set respektive map. För den senare tillkommer utrymme för tillhörande datavärde.

  ![Link node for std::set](/blog/2025/sa-har-anvander-du-stl-tree-containers/set-node-1300w.png "Link node for std::set")

```cpp
template<typename KeyType>
struct SetNode {
    KeyType   payload{};
    SetNode*  parent = nullptr;
    SetNode*  left   = nullptr;
    SetNode*  right  = nullptr;
};

template<typename KeyType, typename ValueType>
struct MapNode {
    std::pair<KeyType, ValueType>  payload{};
    MapNode*  parent = nullptr;
    MapNode*  left   = nullptr;
    MapNode*  right  = nullptr;
};
```

Accesstiden för att hitta ett element eller insättningsposition är _O(log n)_. Om antalet noder är 1024, vilket är lika med 210, så är antalet "våningar" i sökträdet lika med 10, vilket innebär i genomsnitt 10/2 = 5 jämförelser.

N = 1024 = 210  
2log(N) = 10  
_access time_ = O(log n)

### Jämförelseoperator

För att navigera i sökträdet behöver man utföra jämförelser med nyckeln för respektive nod. Kikar vi närmare på hur `std::set` deklareras, ser vi följande:

```cpp
namespace std {
    template< typename Key, typename Compare = std::less<Key> > 
    class set;
}
```

Som synes, så är det mindre-än operatorn som används vid jämförelser. Containern `std::map` är deklarerad på liknande sätt:

```cpp
namespace std {
    template< typename Key, typename Value, typename Compare = std::less<Key> > 
    class map;
}
```

Här följer några exempel, som illustrerar hur `Compare` används:

```cpp
#include <set>
#include <functional>
#include <print>
#define NUMBERS     1, 6, 6, 1, 2, 2, 5, 5, 5, 3, 3, 4, 4
int main() {
    {
        auto s = std::set<int>{NUMBERS};
        std::println("default   : {}", s);
    }
    {
        auto s = std::set<int, std::less<>>{NUMBERS};
        std::println("ascending : {}", s);
    }
    {
        auto s = std::set<int, std::greater<>>{NUMBERS};
        std::println("descending: {}", s);
    }
}
```

```shell
default   : {1, 2, 3, 4, 5, 6}
ascending : {1, 2, 3, 4, 5, 6}
descending: {6, 5, 4, 3, 2, 1}
```

Blir det kompileringsfel om jämförelse-operatorn saknas? Låt oss kika på ett belysande exempel:

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

struct Person {
    std::string  name{};
    Person() = default;
    Person(std::string const& n) : name{n} {}    
};

template<>
struct std::formatter<Person> {
    std::formatter<std::string>  fmt;

    constexpr auto parse(std::format_parse_context& ctx) {
        return fmt.parse(ctx);
    }

    auto format(Person const& p, std::format_context& ctx) const {
        auto txt = std::format("Person({})", p.name);
        return fmt.format(txt, ctx);
    }
};

template<>
struct std::formatter< std::set<Person> > {
    std::formatter<std::string>  fmt;

    constexpr auto parse(std::format_parse_context& ctx) {
        return fmt.parse(ctx);
    }

    auto format(std::set<Person> const& persons, std::format_context& ctx) const {
        auto txt = "["s;
        auto ix = 0;
        for (auto const& p : persons)
            txt += std::format("{}{}", (ix++ == 0 ? "" : ", "), p);
        txt += "]"s;

        return fmt.format(txt, ctx);
    }
};

int main() {
    auto persons = std::set<Person>{
        Person{"Nisse"s}, Person{"Anna"s}, Person{"Berit"s}, Person{"Carl"s}
    };
    std::println("persons: {}", persons);
}
```

```shell
  ...
error: no match for 'operator<' (operand types are 'const Person' and 'const Person')
  405 |       { return __x < __y; }
  ...
```

Som synes så klagar kompilatorn på att det saknas en mindre-än operator (`<`). Om vi då lägger till en mindre-än operator, så funkar det:

```cpp
bool operator <(Person const& a, Person const& b) {
    return a.name < b.name;
}
```

```shell
persons: [Person(Anna), Person(Berit), Person(Carl), Person(Nisse)]
```

### Insättning i `std::set<KeyType, Comparator>`

Förutom insättning via konstruktorn, vilket vi redan sett exempel på här ovan, så kan man sätta in element via metoden `insert()` respektive `emplace()`. Låt oss börja med den första.

```cpp
auto s = std::set<std::string>{};
s.insert("berit");

std::string txt[] = {"carin", "anna"};
s.insert(std::begin(txt), std::end(txt));

auto a = std::array{"carl"s, "adam"s, "bertil"s};
s.insert_range(a);

std::println("text: {}", s);
//text: {"adam", "anna", "berit", "bertil", "carin", "carl"}
```

Som synes, finns det lite olika överlagrade varianter. Den första visar insättning av ett enstaka element, sen kommer insättning av ett interval, och till sist insättning av en range/container (`insert_range`). För enkla datatyper så fungerar detta utmärkt.

Emellertid, om du har en egendefinierad typ och avser att sätta in objekt av denna typ, så är en viktig designfråga huruvida objekten redan är skapade någon annanstans eller om de skapas i samband med insättning. Om det sista är fallet är det betydligt mer effektivt att använda metoden emplace, eftersom då skickar du med kontruktor-argumenten och objektet skapas direkt på plats i en link-node.

```cpp
struct Person {
    std::string  name{};
    unsigned     age{};
    auto operator <=>(Person const&) const = default;
};

auto s = std::set<Person>{};

s.insert( Person{"Anna Conda"s, 42} );  //1
s.emplace("Per Silja"s, 37);            //2
```

Här ovan kan du jämföra de två metoderna. Vid (1) skapar vi först objektet och sen flyttas det in i containern, medan vid (2) så skickas bara argumenten och objektet skapas på plats.

Du kan skriva en egen komparator om det behövs. Här visar jag ett exempel på en case-insensitive sådan för en `std::set< std::string >`.

```cpp
#include <set>
#include <algorithm>
#include <print>
#include <cctype>
#include <string>
using namespace std::string_literals;

struct CaseInsensitiveComparator {
    bool operator()(const std::string& a, const std::string& b) const {
        return std::lexicographical_compare(
            a.begin(), a.end(), b.begin(), b.end(),
            [](unsigned char ac, unsigned char bc) {
                return std::tolower(ac) < std::tolower(bc);
            });
    }
};

int main() {
    auto s = std::set<std::string, CaseInsensitiveComparator>{
        "Carl"s, "Anna"s, "Berit"s, "ANNA"s, "DORIS"s, "CARIN"s, "doris"s, "anna"s
    };
    std::println("names: {}", s);
}
//names: {"Anna", "Berit", "CARIN", "Carl", "DORIS"}
```

Namnet Anna förekommer tre gånger, stavat på lite olika sätt. Som synas är det bara den första varianten som återfinns, övriga har ignorerats.

### Uppslagning av element i `std::set<KeyType, Comparator>`

Att kontrollera om ett element finns, kan enkelt göras med metoden `contains()`, om du kompilerar med c++20 (eller senare). I annat fall måste du använda metoden `count()` och kontrollera returvärdet är större än 0. För std::set, kan det bara bli 0 eller 1, men för std::multiset kan returvärdet vara större än 1. Sen finns också metoden `find()` som returnerar en iterator till elementet om det fanns, annars värdet av `end()`.

```cpp
auto s = std::set{
    "Carl"s, "Anna"s, "Berit"s, "Carin"s,
    "Adam"s, "Eva"s, "Doris"s, "Anna"s
};
std::println("names: {} ({})", s, s.size());

std::println("-- using contains() --");
if (s.contains("Carin")) std::println("s contains 'Carin'");
if (not s.contains("Nisse")) std::println("s contains not 'Nisse'");

std::println("-- using count() (pre c++20) --");
if (s.count("Anna") > 0) std::println("s contains 'Anna'");
if (s.count("Frida") == 0) std::println("s contains not 'Frida'");

std::println("-- using find() --");
if (auto it = s.find("Doris"s); it != s.end())
    std::println("found: {}", *it);
if (auto it = s.find("Kurt"s); it == s.end())
    std::println("not found: {}", "Kurt"s);
```

```shell
names: {"Adam", "Anna", "Berit", "Carin", "Carl", "Doris", "Eva"} (7)
-- using contains() --
s contains 'Carin'
s contains not 'Nisse'
-- using count() (pre c++20) --
s contains 'Anna'
s contains not 'Frida'
-- using find() --
found: Doris
not found: Kurt
```

### Borttagning av element i `std::set<KeyType, Comparator>`

Du kan radera element med metoden `erase()`, vilken har några överlagrade varianter. Till denna finns funktionen `std::erase_if()` för att radera element givet ett visst kriterium. Utöver detta finns metoden `merge()` som flyttar element från en std::set till en annan. Här kommer ett exempel som visar all tre.

```cpp
#include <random>
#include <print>
#include <set>

int main() {
    auto r = std::random_device{};
    auto U = std::uniform_int_distribution{1, 20};
    auto N = 100;
    auto numbers = std::set<int>{};
    for (auto k=0; k<N; ++k) numbers.insert( U(r) );
    std::println("numbers  : {} ({})", numbers, numbers.size());

    numbers.erase( 10 );
    std::println("drop 10  : {} ({})", numbers, numbers.size());

    numbers.erase( numbers.find(20) );
    std::println("drop 20  : {} ({})", numbers, numbers.size());

    numbers.erase( numbers.begin(), numbers.find(5) );
    std::println("drop 1..4: {} ({})", numbers, numbers.size());

    std::erase_if(numbers, [](auto x){ return x % 2 == 1; });
    std::println("drop odd : {} ({})", numbers, numbers.size());

    auto s2 = std::set<int>{15,16,17,18,19,20};
    numbers.merge(s2);
    std::println("merge   : {} ({}), s2={}", numbers, numbers.size(), s2);
}
```

```shell
numbers  : {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20} (20)
drop 10  : {1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20} (19)
drop 20  : {1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19} (18)
drop 1..4: {5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19} (14)
drop odd : {6, 8, 12, 14, 16, 18} (6)
merge   : {6, 8, 12, 14, 15, 16, 17, 18, 19, 20} (10), s2={16, 18}
```

Fortsättning följer i nästa bloggartikel, där jag går igenom API:et för `std::map<KeyType, ValueType, Comparator>`.