I get const_iterator instead of iterator from std::set

Question

I have the following code which does not compile at all. It says that I cannot convert const Node to Node& but Node is not const nor methods of A refer to a const this nor std::set is const.

Where am I wrong?

#include <set>
#include <string>

struct Node
{
    std::string name;
};

struct NodeNameComparator
{
    using is_transparent = void;
    bool operator()(const Node &a, const std::string &b) const { return a.name < b; }
    bool operator()(const std::string &a, const Node &b) const { return a < b.name; }
    bool operator()(const Node &a, const Node &b) const { return a.name < b.name; }
};


struct A
{
    std::set<Node, NodeNameComparator> nodeset;
    Node &add_or_get_node(const std::string &name)
    {
        std::set<Node, NodeNameComparator>::iterator it = nodeset.template find(name);
        // IT WORKS BUT IT IS A WORKAROUND.
        //return it == nodeset.end() ? const_cast<Node&>(*(nodeset.insert(*new Node{name}).first)) : const_cast<Node&>(*it);
        //ERROR!!!
        return it == nodeset.end() ? *(nodeset.insert(*new Node{name}).first) : *it;
    };
};

int main() { return 0; }

Answer 1

std::set is not just a set of elements, it is a sorted set of unique elements. Elements of std::set are immutable by design, so that you cannot break std::set invariant by modifying its elements. That's the reason why std::set::iterator and std::set::const_iterator are both constant iterators.

Cppreference on std::set reads:

Member type       Definition 

iterator          Constant LegacyBidirectionalIterator
const_iterator    Constant LegacyBidirectionalIterator

See also this LWG issue:

Keys in an associative container are immutable. ... For associative containers where the value type is the same as the key type, both iterator and const_iterator are constant iterators.

Rationale: ... if elements were mutable, there would be no compile-time way to detect of a simple user oversight which caused ordering to be modified. There was a report that this had actually happened in practice, and had been painful to diagnose. If users need to modify elements, it is possible to use mutable members or const_cast.