Constness with std::unordered_set & transparent hash

March 22, 2023

Suppose I have a type whose values I want to store in a std::unordered_set that looks like this:

struct S {
    int key; // key is conceptually a part of S and S needs access to it. 
    int data;
    
    bool operator==(S const& rhs) const { return key == rhs.key; }
    bool operator==(int key) const { return this->key == key; }
};

and an accompanying hasher

struct SHash {
    using is_transparent = void;
    // Assume std::hash<int> is the identity function. 
    size_t operator()(S const& s) const { return s.key; }
    size_t operator()(int key) const { return key; }
};

Now I can lookup values in the hashtable by their keys:

int main() {
    std::unordered_set<S, SHash, std::equal_to<>> s;
    s.insert(S{ .key = 0, .data = 1 });
    s.insert(S{ .key = 1, .data = 2 });
    assert(s.find(0)->data == 1);
}

However I cannot change the values in the hashtable:

s.find(0)->data = 3; // Does not compile

This is expected and makes a lot of sense since changing the key would corrupt the hashtable and the returned iterator cannot know what my key is or what my hasher is actually hashing.

Now if I need to modify the rest of the S object, I can either

use std::unordered_map (which internally is more or less an unordered_set of std::pair‘s) and accept to store the key twice
cast away const-ness of the reference returned by .find() and just hope that I will always remember not to change the key. I’m pretty certain that const_cast used like that would be legal as long as I don’t change the key, but it feels really sketchy.

Both options aren’t really beautiful. Are there any other solutions to this problem?

Note that using operator== like this isn’t really best practice and just done to keep the example terse.

Play around with the code on Godbolt if you like.

>Solution :

You cannot modify elements in the unordered_set. Even with non const iterators you cannot modify them. I am not sure if they are const but in any case they are effectively constant. You cannot modify them. From cppreference:

Container elements may not be modified (even by non const iterators) since modification could change an element’s hash and corrupt the container.

What you want to do can be done via std::unodered_set::extract. The example from cppreference:

#include <algorithm>
#include <iostream>
#include <string_view>
#include <unordered_set>
 
void print(std::string_view comment, const auto& data)
{
    std::cout << comment;
    for (auto datum : data)
        std::cout << ' ' << datum;
 
    std::cout << '\n';
}
 
int main()
{
    std::unordered_set<int> cont{1, 2, 3};
 
    print("Start:", cont);
 
    // Extract node handle and change key
    auto nh = cont.extract(1);
    nh.value() = 4; 
 
    print("After extract and before insert:", cont);
 
    // Insert node handle back
    cont.insert(std::move(nh));
 
    print("End:", cont);
}

You cannot modify the elements in the container, but you can extract it, modify, and insert back in.