std::flat_map, std::flat_set and reserving storage?

Question

I am excited to use std::flat_map and std::flat_set in my code base. There are a handful of cases where I need to persist a searchable, ordered set of data as contiguous memory and then pass that down into another function as a plain C-style array. Historically I have done that by manually inserting sorted into a std::vector, or bulk inserting and then invoking std::sort(). I wrap std::lower_bound() in an accessor for searching, access std::vector::data() and there you go.

With std::flat_map I get all of this in the standard. However, the API seems to have no way of reserving the storage prior to creating the adapter. I have solved this by first creating the containers for key and value myself, reserving each, and them moving them into the adapter, but it is cumbersome. It also prevents me from reserving additional storage later, should a bulk insert happen, or the knowledge of a perceived upper bound change.

It seems the internal containers are private, as per the standard, so subclassing to get to it is not possible. The std::flat_map::keys() and std::flat_map::values() both return const references, so that's no help. I suppose I could use std::flat_map::extract() to return the containers, and then reserve more storage, and then in-place new the original map?

It all seems a bit clunky. My goal is to reduce reallocation (and fragmentation) in my environment where I do not have the benefits of virtual memory manager, and allocation costs are not insignificant.

Answer 1

However, the API seems to have no way of reserving the storage prior to creating the adapter.

Yes, this is because the underlying containers are required to be SequenceContainer, which does not require a reserve method. Of the SequenceContainers in std, only std::vector and std::inplace_vector have reserve, and std::inplace_vector::reserve does nothing when it doesn't throw std::bad_alloc.

You could write a function to reserve a new capacity in both containers, but you can't give it the strong exception guarantee, as if the second reserve throws, you've already modified the first container. Below I use a macro to ensure that we put the map back together before propagating any exceptions, which is at least the basic exception guarantee.

template<class...Args>
void reserve_map(std::flat_map<Args...>& map, std::size_t new_cap) {
    auto [keys, values] = map.extract();

    ON_SCOPE_EXIT(map.replace(std::move(keys), std::move(values)));

    if constexpr(requires { keys.reserve(new_cap); }) {
        keys.reserve(new_cap);
    }

    if constexpr(requires { values.reserve(new_cap); }) {
        values.reserve(new_cap);
    }
};

Answer 2

Use the std::flat_map::replace function to move the extracted data back:

mp.replace(
   std::move(ex.keys), 
   std::move(ex.values)
);

You could define a resize function too:

using my_flat_map = std::flat_map<my_keys, my_values>;

void reserve_map(my_flat_map& mp, std::size_t ks, std::size_t vs = ks){
    auto ex = mp.extract();

    ex.ks.reserve(ks);
    ex.vs.reserve(vs);

    mp.replace(
       std::move(ex.keys), 
       std::move(ex.values)
    ); // mp.replace
};