Skip to content

Sets and Maps

The small set/map classes use a more cache-friendly flat set/map and all other optimizations mentioned above for internal algorithms. As with other small containers, a custom template parameter can be used to define the number of inline elements in the container.

The small::default_inline_storage and small::is_relocatable trait can also be defined for custom types, and all the usual set/map, ordered/unordered, uni/multi variants are also provided:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
//
// Copyright (c) 2022 alandefreitas (alandefreitas@gmail.com)
//
// Distributed under the Boost Software License, Version 1.0.
// https://www.boost.org/LICENSE_1_0.txt
//

#include <small/map.hpp>
#include <small/set.hpp>
#include <iostream>

// A relocatable custom type whose default inline storage should be at least 10
// elements
struct my_type
{
    int a;
    double b;
    friend bool
    operator<(const my_type &lhs, const my_type &rhs) {
        return lhs.a < rhs.a;
    }
};

namespace small {
    template <>
    struct is_relocatable<my_type> : std::true_type
    {};
    template <>
    struct default_inline_storage<my_type> : std::integral_constant<size_t, 10>
    {};
} // namespace small

int
main() {
    // Inline storage for at least 5 elements
    small::max_size_map<int, my_type, 5> v1 = {
        {1, { 1, 1.1 }},
        {2, { 2, 2.2 }},
        {3, { 3, 3.3 }},
        {4, { 4, 4.4 }},
        {5, { 5, 5.5 }}
    };
    for (const auto &x: v1) {
        std::cout << '<' << x.first << ',' << '<' << x.second.a << ','
                  << x.second.b << '>' << '>' << ' ';
    }
    std::cout << "\n";

    // Default inline storage for at least 10 elements
    small::unordered_multiset<my_type> v2 = {
        {1, 1.1},
        {2, 2.2},
        {3, 3.3},
        {4, 4.4},
        {5, 5.5}
    };
    for (const auto &x: v2) {
        std::cout << '<' << x.a << ',' << x.b << '>' << ' ';
    }
    std::cout << "\n";

    return 0;
}

Unlike a small::vector or small::string, the asymptotic time complexities of flat sets/maps are very different from their std:: counterparts and should only be used when they are small. Because they are internally implemented as arrays, manipulating these containers costs O(n).

For large containers, you can use std containers with custom allocators. Or for efficient large containers, you can use the abseil containers, implemented as B+-trees.