STL like container with O(1) performance.

Question

Hi,

I couldn't find an answer but I am pretty sure I am not the first one looking for this. Did anyone know / use / see an STL like container with bidirectional access iterator that has O(1) complexity for Insert/Erase/Lookup ?
Thank you.

Answer 1

There is no abstract data type with O(1) complexity for Insert, Erase AND Lookup which also provides a bi-directional access iterator.

Edit:

This is true for an arbitrarily large domain. Given a sufficiently small domain you can implement a set with O(1) complexity for Insert, Erase and Lookup and a bidirectional access iterator using an array and a doubly linked list:

std::list::iterator array[MAX_VALUE];
std::list list;

Initialise:

for (int i=0;i<MAX_VALUE;i++)
    array[i] = list.end();

Insert:

if (array[value] != list.end())
    array[value] = list.insert(value);

Erase:

if (array[value] != list.end()) {
    array[value].erase();
    array[value] = list.end();
}

Lookup:

array[value] != list.end()

Answer 2

Associative arrays (hashtable) have O(1) lookup complexity, while doubly linked lists have O(1) bidi iteration.

Answer 3

You won't be able to fit all of your requirements into one container... something's gotta give ;) However, maybe this is interesting for you: http://www.cplusplus.com/reference/stl/

Answer 4

tr1's unordered_set (also available in boost) is probably what you are looking for. You don't specify whether or not you want a sequence container or not, and you don't specify what you are using to give O(1) lookup (ie. vectors have O(1) lookup on index, unordered_set mentioned above has O(1) average case lookup based on the element itself).

Answer 5

One trick I've done when messing about storage optimization is to implement a linked list with an add of O(1)[1], then have a caching operation which provides a structure with a faster O(n) lookup[2]. The actual cache takes some O(n) time to build, and I didn't focus on erase. So I 'cheated' a bit and pushed the work into another operation. But if you don't have to do a ton of adds/deletes, it's not a bad way to do it.

[1] Store end pointer and only add onto the end. No traversal required.
[2] I created a dynamic array[3] and searched against it. Since the data wasn't sorted, I couldn't binsearch against it for O(lg n) time. Although I suppose I could have sorted it.
[3]Arrays have better cache performance than lists.

Answer 6

Full list of all the complexity gurantees for the STL can be found here:
http://stackoverflow.com/questions/181693/what-are-the-complexity-guarantees-of-the-standard-containers

Summary:

---

• Insert: No container gurantees O(1) for generic insert.
  • The only container that has a genric insert gurtantee is: the 'Associative Container'. And this is O(ln(n))

• There are containers the provide limited insert gurantees

  • Forward sequece gurantee an insert at head of O(1)
  • Back sequence gurantee an insert at tail of O(1)

    ---

• Erase

  • The Associative containers gurantee O(1) for erase (If you have an iterator).

    ---

• Lookup:

  • If you mean element access by lookup (as no container has O(1) find capabilities).
  • Then Random Access container is the only container with O(1) accesses

    ---

So the answer is based on container types.
This is what the standard gurantees are defiend for how does this translate to real containers:

std::vector:    Sequence,   Back        Sequence,                   Forward/Reverse/Random Container
std::deque:     Sequence,   Front/Back  Sequence,                   Forward/Reverse/Random Container
std::list:      Sequence,   Front/Back  Seuqence,                   Forward/Reverse Container
std::set:       Sorted/Simple/Unique    Associative Container,      Forward Container
std::map:       Sorted/Pair/Unique      Associative Container,      Forward Container
std::multiset:  Sorted/Simple/Multiple  Associative Container,      Forward Container
std::multimap:  Sorted/Pair/Multiple    Associative Container,      Forward Container

Answer 7

In practice, it may be sufficient to use array (vector) and defer costs of inserts and deletes.

Delete element by marking it as deleted, insert element into bin at desired position and remember offset for larger indices.

Inserts and deletes will O(1) plus O(N) cleanup at convenient time; lookup will be O(1) average, O(number of changes since last cleanup) worst case.