Linked-list based vector

Question

I was thinking about the downside of using the std::vector container, and was wondering if using a chunked linked-list as a back-end might avoid the copy that occurs when the vector extends.

Something like this.

I guess my question is, is this a practical idea and am I right to assume that reading from the container would have similar runtime as the array-based vector, while the "grow" time would be vastly reduced?

Answer 1

Your data structure is essentially an unrolled linked list. It is a linked list that contains multiple elements per node.

This design allows to improve the locality of references and reduce the number of allocate and deallocate operations for inserting and removing elements, proportional to the number of elements that can be stored in a single node. Furthermore, memory usage can be reduced significantly, since it is not necessary to allocate a new node, which also contains the pointers required for linkage, to prepare space for a single element.

A simple way to implement the unrolled linked list involves the creation of a container adapter, which handles the insert, erase and access operations for the underlying container, defined as a linked list, std::forward_list or std::list, whose nodes contain a dynamic-size array, std::vector. Although the latter requires the allocation of other memory to create the underlying array, it allows to keep track of the number of stored elements and ensures that memory is not initialized by default. This is an important advantage over the std::array container, which would require to add and update an integer to keep track of the number of elements. It also requires to use a technique to prevent elements from being initialized while the container is constructing.

The major limitation of this data structure is the computational cost, which is the same as that of a classic linked list for insert, erase and access operations. This means that it can not be used as a drop-in of a dynamic-size array, implemented in the std::vector container. The most appropriate data structure for your expectations seems to be the hashed array tree, implemented in the std::deque container.

Answer 2

The run-time (random) access of your solution would be greater than that of the std::vector.

In order to access element N, you may have to go through many links to get to the appropriate block, then access an element through the block.

The performance of large vectors can be reduced by allocating a larger size up front.

If insert and removal is frequent, perhaps a vector is the wrong data structure.

Answer 3

You could do some experiment using std::deque, which just work as your description.