Så här använder 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).

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.

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.

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 2¹⁰, 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 = 2¹⁰
₂log(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:

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:

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:

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

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:

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

  ...
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:

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

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.

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.

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

#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().

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

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.

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

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