std::set<int * const> won't compile

Question

The const here is the cause of the compilation problem. However, having implemented an AVL tree myself, I can't understand why.

Here's the code:

#include <set>

int main ()
{
    int a;
    
    // I want the set to carry the "promise"
    // to keep the pointers constant
    std::set<int * const> x;
    
    x.insert(&a);
}

And here's the error:

In file included from /usr/include/c++/7/string:48:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from demo.cpp:1:
/usr/include/c++/7/bits/stl_function.h: In instantiation of ‘struct std::_Identity<int* const>’:
/usr/include/c++/7/bits/stl_tree.h:2091:29:   required from ‘std::pair<std::_Rb_tree_iterator<_Val>, bool> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_insert_unique(_Arg&&) [with _Arg = int* const; _Key = int* const; _Val = int* const; _KeyOfValue = std::_Identity<int* const>; _Compare = std::less<int* const>; _Alloc = std::allocator<int* const>]’
/usr/include/c++/7/bits/stl_set.h:510:48:   required from ‘std::pair<typename std::_Rb_tree<_Key, _Key, std::_Identity<_Key>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator, bool> std::set<_Key, _Compare, _Alloc>::insert(std::set<_Key, _Compare, _Alloc>::value_type&&) [with _Key = int* const; _Compare = std::less<int* const>; _Alloc = std::allocator<int* const>; typename std::_Rb_tree<_Key, _Key, std::_Identity<_Key>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator = std::_Rb_tree_const_iterator<int* const>; std::set<_Key, _Compare, _Alloc>::value_type = int* const]’
demo.cpp:11:18:   required from here
/usr/include/c++/7/bits/stl_function.h:877:7: error: ‘const _Tp& std::_Identity<_Tp>::operator()(const _Tp&) const [with _Tp = int* const]’ cannot be overloaded
       operator()(const _Tp& __x) const
       ^~~~~~~~
/usr/include/c++/7/bits/stl_function.h:873:7: error: with ‘_Tp& std::_Identity<_Tp>::operator()(_Tp&) const [with _Tp = int* const]’
       operator()(_Tp& __x) const

Is there a "clean" way to do this? (ie. not a work-around like making a "pointer class" with a comparator for every situation like this)

Answer 1

You cannot modify elements stored in an std::set so the point is moot. It is designed to keep elements in a sorted order and modifications would break that guarantee. That's why the iterators (both std::set<T>::iterator and std::set<T>::const_iterator) both return const references.

There is no way to edit an element short of mutable (or const_cast), in which case you still need to guarantee the ordering remains the same.