std::set 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)

I'm pointing this because a `int* const` is a value which can't be changed, which implies that any internal structure of the `std::set` won't be copy-constructible or assignable, which is against the requirements of any STL collection. You want to prevent changes to the pointed data, but storing pointers which can't be changed makes no sense as you are not directly working with the internal structure. — Jack, Feb 01 '19 at 03:37
I'm confused, elements in a set [cannot be modified](https://stackoverflow.com/questions/9600666/how-to-change-a-set-element), which is the guarantee you're looking for — kmdreko, Feb 01 '19 at 03:41

kmdreko · Answer 1 · 2019-02-01T11:10:11.853

9

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.

edited Feb 01 '19 at 11:10

answered Feb 01 '19 at 04:12

kmdreko

42,554
6
57
106

1

I had stupidly forgotten that std::set forces this const-ness anyway. Thanks for your answer. – Elliott Feb 01 '19 at 04:25
But still, if you want to make use of const corectness features of c++ and at some point you have only const pointers to T available, you will not be able to make use of std::set. – marcinj Feb 01 '19 at 04:48
1

You can usually copy a `const T` to a `T` and `int*` isn't an exception. – kmdreko Feb 01 '19 at 06:34
Final point: "It is designed to keep elements in a sorted order and modifications would break that guarantee." I would just like to say that this isn't strictly true - you only need to keep the key constant (anything that effects the < operator) - it's implemented like this in std::map. However, std::set *does* provide *only* const access to the whole element. Just a technicality, but perhaps you could edit the answer to clarify this? – Elliott Feb 01 '19 at 10:59
1

@ElliottSmith that is true, I've edited in that possibility, but I'd like to keep the initial wording as-is because `mutable` or `const_cast` are exceptions to the rule. – kmdreko Feb 01 '19 at 11:12

marcinj · Accepted Answer · 2019-02-01T04:45:54.763

More formal answer is that std::set meets the requirements of being AllocatorAwareContainer:

A set satisfies all of the requirements of a container, of a reversible container ([container.requirements]), of an associative container ([associative.reqmts]), and of an allocator-aware container (Table 65).

and in [allocator.requirements] in table 33 you can read:

T, U, C any cv-unqualified object type ([basic.types])

where T is same as X::value_type where X is an allocator class for type T. This means std::allocator<int * const> does not meets above requirements.

This is true for many other containers, for example vector, you may read more here: Does C++11 allow vector<const T>?

[edit[

Visual Studio gives slightly more descriptive error:

C:\Program Files (x86)\Microsoft Visual Studio 14.0\VC\INCLUDE\xmemory0(585): error C2338: The C++ Standard forbids containers of const elements because allocator is ill-formed.

with clang you may see that first error lines directs to allocator headers:

../include/c++/5.5.0/ext/new_allocator.h:93:7: error: multiple overloads of 'address' instantiate to the same signature '__gnu_cxx::new_allocator::const_pointer (__gnu_cxx::new_allocator::const_reference) const noexcept' (aka 'int *const *(int *const &) const noexcept') address(const_reference __x) ........

score 1 · Answer 3 · answered Feb 01 '19 at 03:17

1

Here's a simple program to demonstrate the problem you are seeing:

int main(int argc, char ** argv)
{
   int * const a = NULL;
   int * const b = NULL;

   b = a;   // error: cannot assign to variable 'b' with const-qualified type
}

Note that it's a compile-time error to change the value of a variable of int * const, because the variable is considered read-only.

std::set internally has the same problem -- it needs to modify variables of the specified type, and it cannot do so if its specified type is read-only.

Changing the type to const int * instead is probably what you want to do, as that type allows the pointers to be overwritten when necessary (while not allowing modifications to the ints that they point to).

answered Feb 01 '19 at 03:17

Jeremy Friesner

70,199
15
131
234

Nice explanation. The error visual studio throw caught highlights this too.. `The C++ Standard forbids containers of const elements because allocator is ill - formed` – sjsam Feb 01 '19 at 03:20
Isn't the element of the set the pointer though? and a set never modifies the elements (and so I would assume that std::set implementation uses const on the data type regardless?) – Elliott Feb 01 '19 at 03:20
3

The `set` has to store its elements somewhere -- perhaps e.g. in an internal array (or similar). As the `set` gets updated, it will need to add/remove items to/from that internal array. Therefore, the items in the array must be modifiable or the `set` can't do its job. – Jeremy Friesner Feb 01 '19 at 03:21
"Changing the type to const int * instead is probably what you want to do, as that type allows the pointers to be overwritten when necessary (while not allowing modifications to the ints that they point to)." This isn't want I wanted to do. I'm re-writing a quadtree and want a set < const class_name * const >. I simplified it as much as possible for the question, and the first const (for the data) wasn't causing the problem. – Elliott Feb 01 '19 at 03:30
1

I really don't see why you need `const class_name* const`, just work with `const_iterator`. How does preventing the pointer to be changed internally in the `std::set` affects your code? – Jack Feb 01 '19 at 03:34
1

@ElliottSmith `I want to be able to add/delete/find in log(n) time, but not edit.` imho, that is exactly what set does. Why can't you consider `&a` as just another number? – sjsam Feb 01 '19 at 03:37
@ElliottSmith • Ahh, in that case a `std::set` is not the thing to use. – Eljay Feb 01 '19 at 03:57
@Jack, The question's example is obviously a great simplification of my real problem. Pointers get shared around in my QTree class and I don't want any of the functions to change any of the pointers to the nodes, as there are many shallow-copies. I can easily do this by not using the "const" and instead make sure not to do anything stupid, but I'm trying to use const where it is suitable (ie. changes to pointers here would cause false results or segfault). STL/RBT can easily do this - so I don't see why std::set cannot? – Elliott Feb 01 '19 at 04:03
2

@ElliottSmith I'm not sure I understand your comment -- can you give me an example of how a user could edit the elements of a `std::set` ? (AFAICT you can insert or remove elements, but not modify them in-place, although I might be missing something) – Jeremy Friesner Feb 01 '19 at 04:13
1

Ok, pointers are shared around, which is fine. Then they're copied by value inside a `std::set`, which is still fine. If they're `const int*` you can't change the value indeed so where's your problem? I think that there're a basic misunderstanding here, could you provide a real case scenario in which you need it to be `const int* const` INSIDE the `std::set`? – Jack Feb 01 '19 at 04:22
1

@JeremyFriesner: Given that it never moves any elements, a `std::set` certainly *doesn’t* need to modify any `T` : you can *initialize* a const object, after all. But it needs it to be non-const for other reasons (as given in marcinj’s answer). – Davis Herring Mar 09 '20 at 01:31

std::set won't compile

3 Answers3