Keys are not marked as const when used structured binding during iteration over container

[miszak]

When iterating over robin_hood::unordered_map using C++17's structured bindings the keys are not marked const as expected. This can lead to incorrect programs when keys are modified without updating of hash map internal structure.

As an illustration let's see the program below. In the line 24 incorrect assignment is allowed which leads to the error in the internal structure of the hash map. When std::unordered_map is used (comment line 14 and uncomment line 15) then in the line 24 error is raised by the compiler (as expected) telling that Boxed::value is read-only object.

     1  #include "robin_hood.h"
     2  #include <unordered_map>
     3  #include <iostream>
     4  
     5  struct Boxed {
     6      int value;
     7      bool operator == (const Boxed &other) const { return other.value == value; }
     8  };
     9  
    10  struct RobinHasher {
    11      std::size_t operator()(const Boxed &b) const { return robin_hood::hash_int(b.value); }
    12  };
    13  
    14  using Map = robin_hood::unordered_map<Boxed, int, RobinHasher>;
    15  //using Map = std::unordered_map<Boxed, int, RobinHasher>;
    16  
    17  int main()
    18  {
    19      Map m;
    20      m[Boxed{1}] = 1;
    21      m[Boxed{2}] = 2;
    22  
    23      for (auto &[k, v]: m) {
    24          k.value = k.value + 10; // <- this assignment should be forbidden by `k` being marked as `const`
    25      }
    26  
    27      auto it = m.find(Boxed{2});  // looking for e.g. Boxed{12} fails as well
    28      if (it == m.end()) { std::cout << "FAIL\n"; return 1; }
    29      else { std::cout << "SUCCESS\n"; }
    30      return 0;
    31  }

Link to code in Compiler Explorer: https://gcc.godbolt.org/z/b9xqWxehn

[slavenf]

Hello.

I am not familiar with internals of this library but I would like to write some comment about your problem. Some implementations of unordered maps store keys as non-const values. Doing that makes move operations faster (move constructor and move assignment operator). Suppose that class Boxed from your example is very, very expensive to copy (for example just add some std::vector inside). If robin_hood::unordered_map had stored keys as const values then every reallocation of storage would required to copy keys (because moving const values is not possible, only copying).

For example you can see AssocVector written by Andrei Alexandrescu: https://github.com/snaewe/loki-lib/blob/master/include/loki/AssocVector.h or small_unordered_flat_map written by myself: https://github.com/slavenf/sfl-library/blob/master/include/sfl/small_unordered_flat_map.hpp Both containers store key-value elements as std::pair<Key, T> (keys are non-const).

[martinus]

As @slavenf says, this is to be able to rearange objects, that's one case where unordered_flat_map differs from std::unordered_map. If you need const keys use unordered_node_map.