STL/Boost container like array, storing elements in sorted order, no gaps?

Question

I'd like to insert and 'delete' elements on a fixed-sized array. After each operation the elements are in sorted order and contiguous (no gaps).

The first element will be inserted in the middle.

Are there any existing containers (including Boost) which do this? I can write some of the logic but surely this must be an uncommon requirement?

I can add some of the additional/non-vanilla logic on top.

Answer 1

Have a look at boost::container::flat_set and boost::container::flat_map.

E.g.

Live On Coliru

#include <boost/container/flat_map.hpp>
#include <boost/container/static_vector.hpp>
#include <iostream>
#include <iomanip>

namespace bc = boost::container;

int main() {
    static const bc::flat_map<std::string_view, int> m{
        {"one", 111}, {"two", 222}, {"five", 555}, {"seven", 777}, {"nine", 999},
    };

    for (auto [k,v]: m) {
        std::cout << quoted(k) << " -> " << v << "\n";
    }
}

Prints the expectable

"five" -> 555
"nine" -> 999
"one" -> 111
"seven" -> 777
"two" -> 222

More interestingly, the iterators are random-access and indeed refer to adjacent indices:

auto one = m.find("one");
auto seven = m.find("seven");
for (auto it : {one, seven}) {
    std::cout << "index of " << quoted(it->first) << ": " << (it - m.begin()) << "\n";
}

std::cout << "one and seven are " << (seven - one) << " places apart\n";

Prints Live On Coliru

index of "one": 2
index of "seven": 3
one and seven are 1 places apart

Static/pre-allocation and optimizations

There are optimized constructors/operations to adopt a known-sorted sequence:

bc::flat_set<int> m;
m.adopt_sequence_equal(bc::ordered_unique_range, {111,222,555,777,999});

You can even have them optimized for fixed/small sizes. E.g. a simple statically sized map with max 10 entries:

namespace bc = boost::container;
template <typename K, typename V, typename Cmp = std::less<K>, typename Pair = std::pair<K const, V>>
using Map10 = bc::flat_map<K, V, Cmp, bc::static_vector<Pair, 10>>;

static Map10<std::string_view, int> const m{
    {"one", 111}, {"two", 222}, {"five", 555}, {"seven", 777}, {"nine", 999},
};

Still works the same way.

This has zero runtime allocations.