Boost Unordered Flat Map and not copyable / not movable types

Question

Following code compile (MSVC C++ latest) using std::unordered_map but not with the new boost:unordered_flat_map:

#include "boost/unordered/unordered_flat_map.hpp"
#include <unordered_map>
    class Foo
    {
    public:
        Foo() = default;
        explicit Foo(int x) : m_x_(x) {};
    private:
        int m_x_;
        std::mutex mtx;
        
    };
    
    int main(int argc, char** argv)
    {
        boost::unordered_flat_map<int,Foo> map_test; //compile with std::unordered_map
        map_test.try_emplace(1,1);
        return 0;
    }

I dont expect it to work with flat_map as with std::map , guessing as the map need reordering, elements need to be able to move/copy. But I dont get why its working with unordered_map and not boost:unordered_flat_map.

Answer 1

The leading factor is not whether the container uses ordered storage organization. It's not as if the collection is reordered (because key properties are immutable, the comparator is fixed and needs to be referentially transparent /idempotent).

Node Based vs. Flat Containers

Instead, the leading factor is how struggle is allocated. Flat maps are called flat because they allocated their elements into a flat region, like a vector. This causes reallocation when the container grows.

In short, move is required on reallocation. By contrast, both std::map and std:: unordered_map are node-based containers, i.e. they perform allocation per element (wrapped in nodes that may contain extra metadata).

In node based containers elements don't need to be moved even if their relation inside the container chances. This is also what gives nude based containers their reference/iterator stability characteristics.

Ordering Invariants

In addition to reallocation, flat containers may need to move elements on insertion/removal to maintain the ordering invariant.

You figured this part, but the inverse doesn't hold because of the reallocation requirements.