find index of element inside a collection, which collection to use?

I have a problem choosing the right data structure/s, these are the requirements:

• I must be able to insert and delete elements
• I must also be able to get the index of the element in the collection (order in the collection)
• Elements has an unique identifier number
• I can sort (if necessary) the elements using any criterium

Ordering is not really a must, the important thing is getting the index of the element, no matters how is internally implemented, but anyway I think that the best approach is ordering. The index of the element is the order inside the collection. So some kind of order has to be used. When I delete an element, the other elements from that to the end change their order/index.

First approach is using a linked list, but I don't want O(n). I have also thinked about using and ordered dictionary, that would give O(log n) for lookup/insert/delete, isn't it? Is there a better approach? I know a TRIE would give O(1) for common operations,开发者_如何学Python but I don't see how to get the index of an element, I would have to iterate over the trie and would give O(n), am I wrong?

---

Sounds like you want an ordered data structure, i.e. a (balanced) BST. Insertion and deletion would indeed be O(lg n), which suffices for many applications. If you also want elements to have an index in the structure, then you'd want an order statistic tree (see e.g., CLR, Introduction to Algorithms, chapter 14) which provides this operation in O(lg n). Dynamically re-sorting the entire collection would be O(n lg n).

If by "order in the collection" you mean any random order is good enough, then just use a dynamic array (vector): amortized O(1) append and delete, O(n lg n) in-place sort, but O(n) lookup until you do the sort, after which lookup becomes O(lg n) with binary search. Deletion would be O(n) if the data is to remain sorted, though.

If your data is string-like, you might be able to extend a trie in the same that a BST is extended to become an order statistic tree.

---

You don't mention an array/vector here, but it meets most of these criteria.

(Note that "Elements has a unique identifer number" is really irrespective of datastructure; does this mean the same thing as the index? Or is it an immutable key, which is more a function of the data you're putting into the structure...)

There are going to be timing tradeoffs in any scenario: you say linked list is O(n), but O(n) for what? You don't really get into your performance requirements for additions vs. deletes vs. searches; which is more important?

---

Well if your collection is sorted, you don't need O(n) to find elements. It's possible to use binary search for example to determine index of element. Also it's possible to write simple wrapper about Entry inside your array, which remember its index inside collection.