I have been trying to find a efficient Linear Container Data Structure which can support:

1. Fast access to any index
2. Fast insert after any index

For example:

Initial structure:

Index:  0  1  2  3  4  5
Data:   7 19  1  3 12  2

Accessing index 4 gives 12
Accessing index 5 gives 2
After I insert 5 after index 2:

Index:  0  1  2  3  4  5  6
Data:   7 19  1  5  3 12  2

Accessing index 4 now gives 3
Accessing index 5 gives 12

Vectors:

Vectors perform well for operation 1 (Access index i).

Linked lists:

Linked lists can perform well for operation 2 (Insert after index i) if we have a pointer to the node at index i.

Balanced binary trees:

1. We can assign indices to every value inserted
2. If the index is a b-bit number, the first value inserted gets index 2**(b-1)-1
3. Every new value inserted is assigned an index that is an average of indices of previous and next elements.
4. In this scheme, we can quickly reach a point where two values have neighboring indices. (Worst case O(b) operations.)

Does anyone have a better solution to handle these operations?