Can I use const in vectors to allow adding elements, but not modifications to the already added?

Question

My comments on this answer got me thinking about the issues of constness and sorting. I played around a bit and reduced my issues to the fact that this code:

#include <vector>

int main() {
    std::vector <const int> v;  
}

will not compile - you can't create a vector of const ints. Obviously, I should have known this (and intellectually I did), but I've never needed to create such a thing before. However, it seems like a useful construct to me, and I wonder if there is any way round this problem - I want to add things to a vector (or whatever), but they should not be changed once added.

There's probably some embarrassingly simple solution to this, but it's something I'd never considered before. I probably should not have mentioned sorting (I may ask another question about that, see this for the difficulties of asking questions). My real base use case is something like this:

vector <const int> v;     // ok (i.e. I want it to be OK)
v.push_back( 42 );        // ok
int n = v[0];             // ok
v[0] = 1;                 // not allowed

Answer 1

Well, in C++0x you can...

In C++03, there is a paragraph 23.1[lib.containers.requirements]/3, which says

The type of objects stored in these components must meet the requirements of CopyConstructible types (20.1.3), and the additional requirements of Assignable types.

This is what's currently preventing you from using const int as a type argument to std::vector.

However, in C++0x, this paragraph is missing, instead, T is required to be Destructible and additional requirements on T are specified per-expression, e.g. v = u on std::vector is only valid if T is MoveConstructible and MoveAssignable.

If I interpret those requirements correctly, it should be possible to instantiate std::vector<const int>, you'll just be missing some of its functionality (which I guess is what you wanted). You can fill it by passing a pair of iterators to the constructor. I think emplace_back() should work as well, though I failed to find explicit requirements on T for it.

You still won't be able to sort the vector in-place though.

Answer 2

Types that you put in a standard container have to be copyable and assignable. The reason that auto_ptr causes so much trouble is precisely because it doesn't follow normal copy and assignment semantics. Naturally, anything that's const is not going to be assignable. So, you can't stick const anything in a standard container. And if the element isn't const, then you are going to be able to change it.

The closest solution that I believe is possible would be to use an indirection of some kind. So, you could have a pointer to const or you could have an object which holds the value that you want but the value can't be changed within the object (like you'd get with Integer in Java).

Having the element at a particular index be unchangeable goes against how the standard containers work. You might be able to construct your own which work that way, but the standard ones don't. And none which are based on arrays will work regardless unless you can manage to fit their initialization into the {a, b, c} initialization syntax since once an array of const has been created, you can't change it. So, a vector class isn't likely to work with const elements no matter what you do.

Having const in a container without some sort of indirection just doesn't work very well. You're basically asking to make the entire container const - which you could do if you copy to it from an already initialized container, but you can't really have a container - certainly not a standard container - which contains constants without some sort of indirection.

EDIT: If what you're looking to do is to mostly leave a container unchanged but still be able to change it in certain places in the code, then using a const ref in most places and then giving the code that needs to be able to change the container direct access or a non-const ref would make that possible.

So, use const vector<int>& in most places, and then either vector<int>& where you need to change the container, or give that portion of the code direct access to the container. That way, it's mostly unchangeable, but you can change it when you want to.

On the other hand, if you want to be able to pretty much always be able to change what's in the container but not change specific elements, then I'd suggest putting a wrapper class around the container. In the case of vector, wrap it and make the subscript operator return a const ref instead of a non-const ref - either that or a copy. So, assuming that you created a templatized version, your subscript operator would look something like this:

const T& operator[](size_t i) const
{
    return _container[i];
}

That way, you can update the container itself, but you can't change it's individual elements. And as long as you declare all of the functions inline, it shouldn't be much of a performance hit (if any at all) to have the wrapper.

Answer 3

You can't create a vector of const ints, and it'd be pretty useless even if you could. If i remove the second int, then everything from there on is shifted down one -- read: modified -- making it impossible to guarantee that v[5] has the same value on two different occasions.

Add to that, a const can't be assigned to after it's declared, short of casting away the constness. And if you wanna do that, why are you using const in the first place?

Answer 4

You're going to need to write your own class. You could certainly use std::vector as your internal implementation. Then just implement the const interface and those few non-const functions you need.

Answer 5

Although this doesn't meet all of your requirements (being able to sort), try a constant vector:

int values[] = {1, 3, 5, 2, 4, 6};
const std::vector<int> IDs(values, values + sizeof(values));

Although, you may want to use a std::list. With the list, the values don't need to change, only the links to them. Sorting is accomplished by changing the order of the links.

You may have to expend some brain power and write your own. :-(

Answer 6

I would have all my const objects in a standard array.
Then use a vector of pointers into the array.
A small utility class just to help you not have to de-reference the objects and hay presto.

#include <vector>
#include <algorithm>
#include <iterator>
#include <iostream>


class XPointer
{
    public:
        XPointer(int const& data)
            : m_data(&data)
        {}

    operator int const&() const
    {
        return *m_data;
    }

    private:
        int const*  m_data;

};

int const               data[]    =  { 15, 17, 22, 100, 3, 4};

std::vector<XPointer>   sorted(data,data+6);


int main()
{
    std::sort(sorted.begin(), sorted.end());
    std::copy(sorted.begin(), sorted.end(), std::ostream_iterator<int>(std::cout, ", "));
    int x   = sorted[1];
}

Answer 7

I'm with Noah: wrap the vector with a class that exposes only what you want to allow.

If you don't need to dynamically add objects to the vector, consider std::tr1::array.

Answer 8

It is true that Assignable is one of the standard requirements for vector element type and const int is not assignable. However, I would expect that in a well-thought-through implementation the compilation should fail only if the code explicitly relies on assignment. For std::vector that would be insert and erase, for example.

In reality, in many implementations the compilation fails even if you are not using these methods. For example, Comeau fails to compile the plain std::vector<const int> a; because the corresponding specialization of std::allocator fails to compile. It reports no immediate problems with std::vector itself.

I believe it is a valid problem. The library-provided implementation std::allocator is supposed to fail if the type parameter is const-qualified. (I wonder if it is possible to make a custom implementation of std::allocator to force the whole thing to compile.) (It would also be interesting to know how VS manages to compile it) Again, with Comeau std::vector<const int> fails to compiler for the very same reasons std::allocator<const int> fails to compile, and, according to the specification of std::allocator it must fail to compile.

Of course, in any case any implementation has the right to fail to compile std::vector<const int> since it is allowed to fail by the language specification.

Answer 9

If constness is important to you in this instance I think you probably want to work with immutable types all the way up. Conceptually you'll have a fixed size, const array of const ints. Any time you need to change it (e.g. to add or remove elements, or to sort) you'll need to make a copy of the array with the operation performed and use that instead. While this is very natural in a functional language it doesn't seem quite "right" in C++. getting efficient implementations of sort, for example, could be tricky - but you don't say what you're performance requirements are. Whether you consider this route as being worth it from a performance/ custom code perspective or not I believe it is the correct approach.

After that holding the values by non-const pointer/ smart pointer is probably the best (but has its own overhead, of course).

Answer 10

I've been thinking a bit on this issue and it seems that you requirement is off.

You don't want to add immutable values to your vector:

std::vector<const int> vec = /**/;
std::vector<const int>::const_iterator first = vec.begin();

std::sort(vec.begin(), vec.end());

assert(*vec.begin() == *first); // false, even though `const int`

What you really want is your vector to hold a constant collection of values, in a modifiable order, which cannot be expressed by the std::vector<const int> syntax even if it worked.

I am afraid that it's an extremely specified task that would require a dedicated class.

Answer 11

Using just an unspecialized vector, this can't be done. Sorting is done by using assignment. So the same code that makes this possible:

sort(v.begin(), v.end());

...also makes this possible:

v[1] = 123;

Answer 12

You could derive a class const_vector from std::vector that overloads any method that returns a reference, and make it return a const reference instead. To do your sort, downcast back to std::vector.

Answer 13

std::vector of constant object will probably fail to compile due to Assignable requirement, as constant object can not be assigned. The same is true for Move Assignment also. This is also the problem I frequently face when working with a vector based map such as boost flat_map or Loki AssocVector. As it has internal implementation std::vector<std::pair<const Key,Value> > . Thus it is almost impossible to follow const key requirement of map, which can be easily implemented for any node based map.

However it can be looked, whether std::vector<const T> means the vector should store a const T typed object, or it merely needs to return a non-mutable interface while accessing. In that case, an implementation of std::vector<const T> is possible which follows Assignable/Move Assignable requirement as it stores object of type T rather than const T. The standard typedefs and allocator type need to be modified little to support standard requirements.Though to support such for a vector_map or flat_map, one probably needs considerable change in std::pair interface as it exposes the member variables first & second directly.

Answer 14

Compilation fails because push_back() (for instance) is basically

underlying_array[size()] = passed_value;

where both operand are T&. If T is const X that can't work.

Having const elements seem right in principle but in practice it's unnatural, and the specifications don't say it should be supported, so it's not there. At least not in the stdlib (because then, it would be in vector).