Iterable O(1) insert and random delete collection

I am looking to implement my own collection class. The characteristics I want are:

1. Iterable - order is not important
2. Insertion - either at end or at iterator location, it does not matter
3. Random Deletion - this is the tricky one. I want to be able to have a reference to a piece of data which is guaranteed to be within the list, and remove it from the list in O(1) time.

I plan on the container only holding custom classes, so I was thinking a doubly linked list that required the components to implement a simple interface (or abstr开发者_如何转开发act class).

Here is where I am getting stuck. I am wondering whether it would be better practice to simply have the items in the list hold a reference to their node, or to build the node right into them. I feel like both would be fairly simple, but I am worried about coupling these nodes into a bunch of classes.

I am wondering if anyone has an idea as to how to minimize the coupling, or possibly know of another data structure that has the characteristics I want.

---

It'd be hard to beat a hash map.

---

Take a look at tries.

Apparently they can beat hashtables:

Unlike most other algorithms, tries have the peculiar feature that the time to insert, or to delete or to find is almost identical because the code paths followed for each are almost identical. As a result, for situations where code is inserting, deleting and finding in equal measure tries can handily beat binary search trees or even hash tables, as well as being better for the CPU's instruction and branch caches.

It may or may not fit your usage, but if it does, it's likely one of the best options possible.

---

In C++, this sounds like the perfect fit for std::unordered_set (that's std::tr1::unordered_set or boost::unordered_set to you if you have an older compiler). It's implemented as a hash set, which has the characteristics you describe.

Here's the interface documentation. Note that the hash containers actually offer two sets of iterators, the usual ones and local ones which only go through one bucket.

Many other languages have "hash sets" as well, certainly Java and C#.