C++11 compilation errors with std::move and std::make_move_iterator

Question

Can somebody explain to me why does this fail to compile:

#include <iterator>
#include <iostream>
#include <unordered_set>
#include <utility>
#include <set>

template<typename T>
std::unordered_set<T> FailMove(std::set<T> &&set) {
  std::unordered_set<T> response;
  response.insert(std::make_move_iterator(set.begin()),
                  std::make_move_iterator(set.end()));
  return response;
}

int main(int argc, char **argv) {
  std::set<int> set{1, 3, 5, 7};

  auto res = FailMove(std::move(set));
  std::cout << res.size() << '\n';

  return 0;
}

The clang output (command: clang++ -std=c++11 -otest test.cpp) is:

In file included from test.cpp:1:
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/iterator:948:14: error: cannot
      cast from lvalue of type 'const value_type' (aka 'const int') to rvalue reference type 'reference' (aka 'int &&'); types are not
      compatible
      return static_cast<reference>(*__i);
             ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/unordered_set:830:34: note: in
      instantiation of member function 'std::__1::move_iterator<std::__1::__tree_const_iterator<int, std::__1::__tree_node<int, void *> *,
      long> >::operator*' requested here
        __table_.__insert_unique(*__first);
                                 ^
test.cpp:10:12: note: in instantiation of function template specialization 'std::__1::unordered_set<int, std::__1::hash<int>,
      std::__1::equal_to<int>, std::__1::allocator<int> >::insert<std::__1::move_iterator<std::__1::__tree_const_iterator<int,
      std::__1::__tree_node<int, void *> *, long> > >' requested here
  response.insert(std::make_move_iterator(set.begin()),
           ^
test.cpp:18:14: note: in instantiation of function template specialization 'FailMove<int>' requested here
  auto res = FailMove(std::move(set));
             ^
1 error generated.

gcc output (command: g++ -std=c++11 -otest test.cpp):

In file included from /usr/include/c++/4.8/iterator:63:0,
                 from test.cpp:1:
/usr/include/c++/4.8/bits/stl_iterator.h: In instantiation of 'std::move_iterator<_Iterator>::value_type&& std::move_iterator<_Iterator>::operator*() const [with _Iterator = std::_Rb_tree_const_iterator<int>; std::move_iterator<_Iterator>::reference = int&&; std::move_iterator<_Iterator>::value_type = int]':
/usr/include/c++/4.8/bits/hashtable_policy.h:647:18:   required from 'void std::__detail::_Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>::insert(_InputIterator, _InputIterator) [with _InputIterator = std::move_iterator<std::_Rb_tree_const_iterator<int> >; _Key = int; _Value = int; _Alloc = std::allocator<int>; _ExtractKey = std::__detail::_Identity; _Equal = std::equal_to<int>; _H1 = std::hash<int>; _H2 = std::__detail::_Mod_range_hashing; _Hash = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<false, true, true>]'
/usr/include/c++/4.8/bits/unordered_set.h:393:4:   required from 'void std::unordered_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator, _InputIterator) [with _InputIterator = std::move_iterator<std::_Rb_tree_const_iterator<int> >; _Value = int; _Hash = std::hash<int>; _Pred = std::equal_to<int>; _Alloc = std::allocator<int>]'
test.cpp:10:3:   required from 'std::unordered_set<T> FailMove(std::set<T>&&) [with T = int]'
test.cpp:18:37:   required from here
/usr/include/c++/4.8/bits/stl_iterator.h:963:37: error: invalid initialization of reference of type 'std::move_iterator<std::_Rb_tree_const_iterator<int> >::reference {aka int&&}' from expression of type 'std::remove_reference<const int&>::type {aka const int}'
       { return std::move(*_M_current); }

However this code does compile in both compilers without problems:

#include <iterator>
#include <iostream>
#include <unordered_map>
#include <utility>
#include <map>

template<typename K, typename V>
std::unordered_map<K, V> FailMove(std::map<K, V> &&map) {
  std::unordered_map<K, V> response;
  response.insert(std::make_move_iterator(map.begin()),
                  std::make_move_iterator(map.end()));
  return response;
}

int main(int argc, char **argv) {
  std::map<int, int> map{{1, 1}, {3, 3}, {5, 5}, {7, 7}};

  auto res = FailMove(std::move(map));
  std::cout << res.size() << '\n';

  return 0;
}

clang version tested:

Apple LLVM version 6.1.0 (clang-602.0.53) (based on LLVM 3.6.0svn)
Target: x86_64-apple-darwin14.3.0
Thread model: posix

gcc version tested:

g++ (Ubuntu 4.8.2-19ubuntu1) 4.8.2
Copyright (C) 2013 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Answer 1

The short version is set::begin() returns a const_iterator while map::begin() returns an iterator. You cannot move from a const_iterator.

The long version is that the "Key" component of associative containers are treated as const within the container. A set contains nothing but a Key component. A map contains both a Key component and a Value component. The values of set are Keys. The values of map are std::pair< const Key, Value >.

This is because modifying the Key component of a standard container in a way that changes the order of elements breaks the invariants of the container. This is true even if you intend to shortly discard it, as even traversal, destruction, or anything else can be broken (in theory) by editing Key components!

---

When you move from an iterator it, it tries to cast *it to value_type&&. For a const iterator, *it returns value_type const&, and the cast fails.

In the case of map, the move will move the Value component, and copy the Key component.