C++: Assigning values to non-continuous indexes in vectors?

Question

If I want to declare a vector of unknown size, then assign values to index 5, index 10, index 1, index 100, in that order. Is it easily doable in a vector?

It seems there's no easy way. Cause if I initialize a vector without a size, then I can't access index 5 without first allocating memory for it by doing resize() or five push_back()'s. But resize clears previously stored values in a vector. I can construct the vector by giving it a size to begin with, but I don't know how big the vector should.

So how can I not have to declare a fixed size, and still access non-continuous indices in a vector?

(I doubt an array would be easier for this task).

Answer 1

Would an std::map between integer keys and values not be an easier solution here? Vectors will require a contiguous allocation of memory, so if you're only using the occasional index, you'll "waste" a lot of memory.

Answer 2

Resize doesn't clear the vector. You can easily do something like:

  if (v.size() <= n)
      v.resize(n+1);
  v[n] = 42;

This will preserve all values in the vector and add just enough default initialized values so that index n becomes accessible.

That said, if you don't need all indexes or contigous memory, you might consider a different data structure.

Answer 3

resize() doesn't clear previously stored values in a vector.
see this documentation

I would also argue that if this is what you need to do then its possible that vector may not be the container for you. Did you consider using map maybe?

Answer 4

Data structures which do not contain a contiguous set of values are known as sparse or compressed data structures. It seems that this is what you are looking for.

If this is case, you want a sparse vector. There is one implemented in boost, see link text

Sparse structures are typically used to conserve memory. It is possible from your problem description that you don't actually care about memory use, but about addressing elements that don't yet exist (you want an auto-resizing container). In this case a simple solution with no external dependencies is as follows:

Create a template class that holds a vector and forwards all vector methods to it. Change your operator[] to resize the vector if the index is out of bounds.

// A vector that resizes on dereference if the index is out of bounds.
template<typename T>
struct resize_vector
{
    typedef typename std::vector<T>::size_type size_type;
    // ... Repeat for iterator/value_type typedefs etc

    size_type size() const { return m_impl.size() }
    // ... Repeat for all other vector methods you want

    value_type& operator[](size_type i)
    {
        if (i >= size())
            resize(i + 1); // Resize
        return m_impl[i];
    }
    // You may want a const overload of operator[] that throws
    // instead of resizing (or make m_impl mutable, but thats ugly).

private:
    std::vector<T> m_impl;
};

As noted in other answers, elements aren't cleared when a vector is resized. Instead, when new elements are added by a resize, their default constructor is called. You therefore need to know when using this class that operator[] may return you a default constructed object reference. Your default constructor for <T> should therefore set the object to a sensible value for this purpose. You may use a sentinel value for example, if you need to know whether the element has previously been assigned a value.

The suggestion to use a std::map<size_t, T> also has merit as a solution, provided you don't mind the extra memory use, non-contiguous element storage and O(logN) lookup rather than O(1) for the vector. This all boils down to whether you want a sparse representation or automatic resizing; hopefully this answer covers both.