STL like container with O(1) performance

Question

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

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).