A set that maintains the insertion order and allows access to elements by its index

Question

I basically need a data structure that works just like Set , but not only maintains the insertion order, as it allows me to get them later using the get(index) method.

Which data structure is best suited to achieve this? I would have no problem having to implement one if necessary. In the worst case, I could just use both ArrayList and HashSet, but I wonder if there is a specialized data structure right down to the task.

Performance is of the utmost importance (otherwise I could just do an O(n) search on a regular list!) And I'm not worried about spatial complexity.

Answer 1

Something like that? Change As Jeddo noted, this structure cannot effectively remove elements. ArrayList + Set is easier if efficient removal is not required, so this structure is not very good for many.

 import java.util.*; public class ArraySet<T> { private final Map<Integer, T> indexToElem; private final Map<T, Integer> elemToIndex; public ArraySet() { indexToElem = new HashMap<Integer, T>(); elemToIndex = new HashMap<T, Integer>(); } public T get(int index) { if (index < 0 || index >= size()) throw new IndexOutOfBoundsException(); return indexToElem.get(index); } public void add(T elem) { if (!contains(elem)) { int index = indexToElem.size(); indexToElem.put(index, elem); elemToIndex.put(elem, index); } } // Doesn't work; see comment. /*public void remove(T elem) { int index = elemToIndex.get(elem); indexToElem.remove(index); elemToIndex.remove(elem); }*/ public boolean contains(T elem) { return elemToIndex.containsKey(elem); } public int size() { return indexToElem.size(); } } 

Answer 2

How about an OrderedDictionary ?

Represents a collection of key / value pairs that are accessible by key or index.

http://msdn.microsoft.com/en-us/library/system.collections.specialized.ordereddictionary.aspx

Answer 3

Can you use existing code? Apache Commons has a ListOrderedSet class that seems to fit all your requirements. Even worse, you can study the source code and implement it in C #.