Should STL map::insert support move semantics with move_iterators?

Question

I have a large amount of data to load into a map from file, which is already in sorted order (because it was serialized from the map). I've discovered it is faster to first load the data into a vector, and then bulk-load into a map with insert. This saves just over a second in a 19sec load time.

The value_type is a structure that contains vectors of other structures. I don't need the vector after the load completes, so I use move_iterators in my call to map::insert. Using MSVC 2015 (VC14), the data isn't moved into the map, but instead is copied via const_reference deep inside the STL code.

Is this a standard-compliant implementation, to ignore the moving of data?

template<typename Stream, typename Key, typename Type, typename Traits, typename Allocator>
bool const read(Stream &is, std::map<Key, Type, Traits, Allocator> &map)
{
    size_t size;
    read(is, size);

    std::vector<std::pair<Key, Type>> items(size);
    for (size_t i=0; i<size; ++i)
    {
        auto &item = items[i];
        if (!read(is, item.first)  ||  !read(is, item.second))
            return false;
    }
    map.insert(std::make_move_iterator(items.begin()), std::make_move_iterator(items.end()));

    return !!is;
}

I've overcome the problem replacing the map.insert with

for (auto &item : items)
    map.insert(std::move(item));

but it isn't so neat, but does save another 0.6 seconds.

Answer 1

Is this a standard-compliant implementation, to ignore the moving of data?

The standard says for that insert() function:

Requires: value_type shall be EmplaceConstructible into X from *i.

So it must be possible to construct the value_type from the iterator's reference type, which in this case is an rvalue-reference. That means you can use move-only (i.e. non-copyable) key types and mapped types and as long as the iterator returns rvalues that can be converted to the map's value_type it must work.

The constructor std::pair<const Key, Type>::pair<K2, T2>(pair<K2, T2>&&) should be used to construct the values into the map from the rvalues that come from the iterators.

This works for me with GCC, and with the latest VC++ using an online compiler:

#include <vector>
#include <map>
#include <iterator>

struct MoveOnly {
  MoveOnly() = default;
  MoveOnly(MoveOnly&&) = default;
};

bool operator<(const MoveOnly&, const MoveOnly&) { return false; }

template<typename Key, typename Type, typename Traits, typename Allocator>
void read(std::map<Key, Type, Traits, Allocator> &map)
{
    std::vector<std::pair<Key, Type>> items(1);
    map.insert(std::make_move_iterator(items.begin()), std::make_move_iterator(items.end()));
}

int main()
{
  std::map<MoveOnly, MoveOnly> m;
  read(m);
}