CODEWITHSUNDEEP
c#.netdata-structures
thr
thr

Reputation: 19476

Data structure that has O(n) iteration, O(1) contains and O(1) get by key

I'm looking for a data-structure, or combination of several, that can give me a behaviour that satisfies these conditions:

  1. O(n) Iteration (does not have to be in-order)
  2. O(1) Contains
  3. O(1) Get (by key, which is an int)
  4. O(1) Add
  5. O(1) Remove

The three solutions I've come up with is something like this, which both are just uses of the built in collections in .NET

  1. Build my own hash set which exposes more of the internal storage to the outside world then the default HashSet<T> in .NET

  2. Use an Dictionary<int, T>, as the iteration does not have to be in-order, but this is a very high performance application and the garbage that gets generated by creating the enumerator each time I need to step through the collection worries me. The worrying about garbage is not one I "made up", this is for a real time simulation and any garbage that could trigger a GC basically a non-option if it can be avoided.

  3. Use a combination of a Dictionary<int, int> and a T[], basically store the key + index into the array in the dictionary, and store the elements in the T[].

Upvotes: 4

Views: 687

Answers (1)

Guillaume
Guillaume

Reputation: 13128

There is a generic KeyedCollection that allows objects to be indexed by an int and a key. The key must be embeded in the value.

You can use a for(int i...) to iterate over it without an IEnumerable.

Upvotes: 3

Related Questions