Array of vectors

[maheshravishankar]

I was just wondering if it is a good idea to have an array of vector. For example,
if I have a graph where I know the number of nodes, ( say nnodes) but dont know the number of successors each node has, i could have the adjacency list ( or alist ) stored as follows

vector<int> alist[nnodes]

I am trying to think how the memory would be allocated and would there be a heavy cost of increasing the memory allocated to each vector as its size grows, i.e. as elements of alist[0] are added would it result in copying of memory for all the vectors alist[1 - (nnodes-1)]

[jsmith]

Why not a vector of vectors?

Inserts at the front or the middle of a vector are expensive, as it does, as you asked, require all subsequent elements
in the vector to be copied (moved) to make space (assuming you are using std::vector<>::push_front() or
std::vector<>::insert(); std::vector<>::operator[] does not insert elements).

To mitigate this, it is often recommended to use a std::deque<> instead of a std::vector<>, and only use
std::vector<> when it is important that all elements be stored in contiguous memory. However, understand
that as T grows in size, std::deque<T> approaches the performance of std::list<T>, however for small T,
it is a good choice.

[maheshravishankar]

Hi jsmith, thanks for that

But if it is ensured that I am always adding to the end of the list, the cost of push_back to vector is very small compared to the cost of insert to a queue.

With vector of vectors, this is how i see it working. If push_back an element into a alist[nnodes/2], the cost will be same as inserting an element into the middle of a vector. I tried to get around it by heap allocating an array, such that all elements of the array are pointers to a vector object. The below code illustrates that:

vector<int> **alist;
alist = new vector<int>*[nnodes];
for( i =0 ; i < nnodes ; i++ )
    alist[i] = new vector<int>;

First of all, I would like to know if the above method is bad in the first place. The way I see it, the array alist holds pointer to a vectors. So adding an element to alist[nnodes/2] would not require relocation of all element of vector alist[nnodes/2+1] - alist[nnodes] ( as it would by my understanding of a vector of vectors ).

If it is not a bad representation, then if I want to avoid the cost of heap allocation, how would the memory management work for stack objects of similar type. The representation in my first post was to do exactly this ( on the stack, and not on the heap )

Once again, i thank you in advance for all your replies

[jsmith]

But if it is ensured that I am always adding to the end of the list, the cost of push_back to vector is very small compared to the cost of insert to a queue.

That isn't necessarily true. In fact, in some cases, it is quite false. If you push_back() onto a vector that has insufficient space, the entire vector gets copied. If you push_back() onto a deque that has insufficient space, none of your elements are copied (though some of deque's internal housekeeping may, but that is fairly insignificant). push_back() onto a deque with sufficient space is as fast as push_back() onto a vctor with sufficient space.

The trouble lies in that most vector<> implementations I know of use one of the worst possible allocation schemes: any time the vector must grow, it doubles in size. It has been shown that this will tend to fragment your heap because each successive doubling of size cannot reuse any of the memory space it used before. In fact, the best way to grow the vector is by the golden ratio. But anyway, given that vector doubles in size, if your vector starts out empty, you'll reallocate when you insert the 1st, 2nd, 4th, 8th, 16th, 32nd, and so forth elements. If your vector is only going to grow to a maximum of 10 elements, you'll reallocate 4 times, and in the process copy 11 elements (on the 2nd insert, you'll copy 1; on the 4th, you'll copy the existing 3; on the 8th insert you'll copy the existing 7). Which is essentially 21 object constructions (11 copies plus the 10 you put in). With std::deque, you'll get 10 constructions period.

(EDIT: Of course you can mitigate the above by using std::vector<>::reserve() before doing any inserts).

If you are afraid of copying whole vectors because you need to insert a new vector in alist between elements i and i+1, then I'd suggest using a std::list< std::vector > instead. While it might be ever so slightly slower, it alleviates you from having to manage
the memory.