STL-like vector with arbitrary index range

Question

What I want is something similar to STL vector when it comes to access complexity, reallocation on resize, etc. I want it to support arbitrary index range, for example there could be elements indexed from -2 to +7 or from +5 to +10. I want to be able to push_front efficiently. Also I want two-way resize...

I know I could write something like this myself, but if there is an already written library that supports this please tell me.

Answer 1

Deque is very much like a vector in that it supports random access and efficient insertion at the end and it also supports efficient insertion at the beginning.

Map supports access based on arbitrary keys, you can have any range you want, or even a sparsely populated array. Iteration over the collection is slow.

Unordered map (tr1) is similar to map except it supports better iteration.

As a general rule of thumb, use a vector (in your case adapt it to the behaviour you want) and only change when you have evidence that the vector is causing slowness.

Answer 2

It seems the only difference between what you want and a vector is the offset you require for accessing elements, which you take care if by overloading operator [] or something. Unless I didn't understand what you meant by two-way resize.

Answer 3

Here you go, double-ended vector

http://dl.dropbox.com/u/9496269/devector.h

usage:

• to reserve memory before begin(), use reserve(new_back_capacity, new_front_capcity);

• except for when using push_front(), pop_front() and squeeze() the front capcity is always preserved.

• squeeze() flushes all unused memory

• default namespace; stdext

concept:

• in most cases equivalent to ::std::vector but with ability to push_front

• no performance differences compared to ::std::vector (as different from ::std::deque)

• four bytes of overhead compared to ::std::vector

Answer 4

If you want 2 way resize, etc... you could create your own vector class with 2 vectors inside one for the 0 and positive values and another for the negative ones.

Then just implement the common functions and add new ones (ex: push_begin to add to the negative indexes vector), and update the correspndent vectors inside.