Does a vector have to store the size twice?

Question

This is a rather academic question, I realise it matters little regarding optimization, but it is just out of interest.

From what I understand, when you call new[size], additional space is allocated to store the size of the allocated array. This is so when delete [] is called, it is known how much space can be freed.

What I've done is written how I think a vector would roughly be implemented:

#include <cstddef>

template <class T>
class Vector
{
public:
  struct VectorStorage
  {
    std::size_t size;
    T data[];
  };

  Vector(std::size_t size) : storage(new VectorStorage[size])
  {
    storage->size = size;
  }

  std::size_t size() 
  { 
    return storage->size; 
  }

  ~Vector() 
  { 
    delete[] storage; 
  }
private:
  VectorStorage* storage;
};

As far as I can tell, size is stored twice. Once in the VectorStorage object directly (as it needs to be so the size() function can work) but again in a hidden way by the compiler, so delete[] can work.

It seems like size is stored twice. Is this the case and unavoidable, or is there a way to ensure that the size is only stored once?

You're blatantly ignoring the [rule of three](http://stackoverflow.com/q/4172722/46642). — R. Martinho Fernandes, Sep 30 '11 at 01:46
As in, the assignment operator? This was just an example, not a full implementation of vector. — Clinton, Sep 30 '11 at 01:59

score 3 · Answer 1 · answered Sep 30 '11 at 01:49

Vectors don't usually store the size. The usual implementation keeps a pointer past the end of the last element and one past the end of the allocated memory, since one can reserve space without actually storing elements in it. However, there is no standard way to access the size stored by new (which may not be stored to begin with), so some duplication is usually needed.

score 3 · Answer 2 · answered Sep 30 '11 at 01:50

Yes. But that's an implementation detail of the heap allocator that the compiler knows nothing about. It is almost certainly not the same as the capacity of the vector since the vector is only interested in the number of elements, not the number of bytes. And a heap block tends to have extra overhead for its own purposes.

score 3 · Accepted Answer · answered Sep 30 '11 at 02:07

3

std::vector does not allocate memory; std::allocator, or whatever allocator you give the vector, is what allocates the memory. The allocator interface is given the number of items to allocate/deallocate, so it is not required to actually store that.

answered Sep 30 '11 at 02:07

Nicol Bolas

449,505
63
781
982

What is a way an allocator could avoid storing the size? – Clinton Sep 30 '11 at 02:13
1

@Clinton: I'm not sure what you're asking. An allocator can do whatever it wants. It could have a private heap. It could use direct OS calls to get blocks of heap and manage memory itself. It can do whatever it wants. – Nicol Bolas Sep 30 '11 at 02:31

score 0 · Answer 4 · answered Sep 30 '11 at 01:52

0

You have size in the wrong place -- you're storing it with every element (by virtue of an array of VectorStorage), which also contains an array (per instance of VectorStorage) of T. Do you really mean to have an array inside an array like that? You're never cleaning up your array of T in your destructor either.

answered Sep 30 '11 at 01:52

Joe

41,484
20
104
125

Joe: I mean one struct with a `size_t` followed by an array of T of size `size`. How can I allocate that with `new`? – Clinton Sep 30 '11 at 02:02

Does a vector have to store the size twice?

4 Answers4