All geek questions in one place

A data structure that has O (n) iteration, O (1) contains and O (1), gets the key

I am looking for a data structure or a combination of several that can give me behavior that satisfies these conditions:

  • O (n) Iteration (doesn't have to be alright)
  • O (1) Contains
  • O (1) Receive (by key, which is int)
  • O (1) Add
  • O (1) Delete

The three solutions I came up with are something like this, and this is just using the built-in collections in .NET

  • Create your own hash set that provides more internal memory to the outside world, and then the default HashSet<T > in .NET

  • Use Dictionary<int, T> , since the iteration should not be in order, but this application with very high performance and the garbage that is generated when creating the enumerator every time I need to go through the collection bothers me. Anxiety about garbage - this is not what I "composed", it is for real-time simulation and any garbage that can cause the GC basically without an option if it can be avoided.

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

+4
source share
1 answer

There is a generic KeyedCollection that allows you to index objects using an int and a key. The key must be inserted into the value.

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

+3
source

Source: https://habr.com/ru/post/1384318/

More articles:


All Articles