c++unordered-set

Constness with std::unordered_set & transparent hash


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

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.