0

I require a data structure that is dynamic (Add/Remove) and that is the most efficient for

  • Contains()
  • Iteration

Both actions are called more often than (add/remove)

What about a combination from a List and a HashSet?

Mechandrius
  • 323
  • 2
  • 12

2 Answers2

2

As mentioned in the comments by @Ross Gurbutt the HashSet satisfies your requirements. It does not, however, maintain the order of items inserted into it (or more precisely, it might not. See this answer by Jon Skeet).

If the fidelity of the order is important to you, then the SortedSet might be what you're looking for.

Edit: The above recommendations go on the assumption that you do not want to allow for duplicates in your collection(s).

Also, as @Ross Gurbutt kindly pointed out (and as I should have mentioned originally):

SortedSet.Contains is O(log n) whereas HashSet.Contains is O(1)

Darren Ruane
  • 2,385
  • 1
  • 8
  • 17
  • 1
    Agree, although it should be noted that SortedSet.Contains is O(log n) whereas HashSet.Contains is O(1). As @Heretic Monkey says above. It depends on which areas you care about the most and what your exact needs are – Ross Gurbutt Nov 22 '19 at 16:07
  • Contains in O(1) is quite important .. I think the HashSet is what I need. I will do some testing and pbbly mark this as the answer. – Mechandrius Nov 22 '19 at 16:10
0

You can use more than one data structure.

Contains

Use a HashSet to get an O(1) access time to any element.

Find and Iteration

Use a List<> to add/remove items by index or to the end of the list: O(1).

That List can also be searched by a binary search if it's ordered: O(log(n)). If it is not ordered, that search is linear, O(n).

Iteration is iteration: always O(n)... in this case over your List.

Kit
  • 20,354
  • 4
  • 60
  • 103
  • Adding to a `List` is only O(1) if the number of elements in it is smaller than its `Capacity`. Otherwise, it is an O(n) operation, where n is the `Count`. Removing from a `List` by index is not O(1) but is, in fact, O(n), where n is (Count - index) as can be read in the docs [here](https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.list-1.removeat?redirectedfrom=MSDN&view=netframework-4.8#remarks). – Darren Ruane Nov 22 '19 at 16:26
  • @DarrenRuane that's not what I meant. I'll fix it. – Kit Nov 22 '19 at 18:25
  • I got the feeling that iterating over a dictionary or a set is slower than over a list. Is there really no difference? – Mechandrius Nov 24 '19 at 13:00