List<T>
Methods |
Complexity (for n elements and count m) |
---|---|
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
|
Stack<T>
Methods |
Complexity (for n elements) |
---|---|
| |
| |
| |
| |
| |
| |
| |
| |
|
Queue<T>
Methods |
Complexity (for n elements) |
---|---|
| |
| |
| |
| |
| |
| |
|
HashSet<T>
Methods |
Complexity (n and m are number of elements) |
---|---|
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
|
SortedSet<T>
Methods |
Complexity (for n elements and count m. l is lower bound and u is upper bound of the view) |
---|---|
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
|
Dictionary<TKey,TValue>
Methods |
Complexity (for n elements) |
---|---|
| |
| |
| |
| |
| |
|
SortedDictionary<TKey,TValue>
Methods |
Complexity (for n elements) |
---|---|
| |
| |
| |
| |
| |
|
The following are the top 20 parameters to consider when selecting a generic collection:
Simple or associative
Random access capability
Lookup speed
Random insertion speed
Edge insertion speed
Random deletion speed
Edge deletion speed
Speed to empty
Time to count
Zero-based indexing
Native sorting capability
Thread safety
Interoperability
Platform portability
Memory requirement
Construction versatility
Native bsearch support
Speed of set operations
Code readability
Least effort to migrate
None of these facilities come in a single collection. So you need to deal with calculated tread-off and strike a balance between computational cost and optimum performance.
The parameters are explained as follows:
Simple or associative:
If you want to store a few elements in a random order then you don’t need an associative collection. Simple lists are IList<T>
based where as associative collections are IDictionary<TKey,TValue>
based.
Random access capability:
If you regularly need to access elements, you would need a collection that supports this functionality to boost performance. Mostly, random access capability is offered by zero-based indexing. Containers that implement IList
offer this functionality.
Lookup speed:
Lookup speed can be crucial in the selection of associative containers. More the speed, the better. Normally, hash-based implementations outperform tree-based or list-based implementations. Thus, accessing an element in SortedDictionary<TKey,TValue>
is faster than SortedList<TKey,TValue>
.
Random insertion speed:
If there are a lot of insertions at random locations in the collection, then you should consider how fast you can insert a few elements at arbitrary locations inside the collection. LinkedList<T>
offers faster random insertion than List<T>
.
Edge insertion speed:
If you know that there will be many insertions at the edges (start or end) of the collection, choose one that is programmed to offer a faster speed. For example, Stack<T>
, Queue<T>
, or LinkedList<T>
. Inserting in an array-based container, such as List<T>
, offers the worst performance as all the elements beyond the point of insertion have to be shifted.
Random deletion speed:
If there are a lot of deletions at random locations in the collection, then you should consider how fast you can delete a few elements at arbitrary locations inside the collection. LinkedList<T>
offers faster random deletion than List<T>
.
Edge deletion speed:
If deletions occur only at the extreme ends of the collection, then you should consider collections optimized for that, such as Stack<T>
, Queue<T>
, or LinkedList<T>
over List<T>
.
Speed to empty:
In many situations, you need to clear all the elements of the collection, perhaps inside a loop. In such situations, you should consider collections that take minimum time to clear all the elements.
Time to count:
It is crucial to count how many elements there are in the collection. If it takes O(n)
that’s not good. In such situations, resort to collections that offer constant time-count operations. Luckily most of them do.
Zero-based indexing:
Zero-based indexing has become the habit of programmers of our time, thanks to C arrays and C++ vectors. If you need random access on a simple sequential collection, resort to the one that offers this, such as List<T>
, rather than using the ElementAt()
method.
Native sorting capability:
If you need to sort the collection every now and then, you can consider those that offer native sorting capabilities such as List<T>
or resort to a sorted collection such as SortedSet<T>
. It is better than using OrderBy()
because a Lambda expression evaluation is generally slower.
Thread safety:
If your collection will be used in a multi-threaded environment, it is better to use new concurrent collections than a primitive locking mechanism.
Interoperability:
Use collections that are more flexible, or in other words, that implement more interfaces. For example, if you need associative storage, then you can use SortedList<TKey,TValue>
. However, SortedDictionary<TKey,TValue>
is also good because it supports serialization. So, in future, it would be easy to serialize.
Platform portability:
If you are programming for a platform limited by memory, then some part of the framework will be absent. Be sure to check for the availability of the collection in the framework targeted to the hardware you are using.
Memory requirement:
If you are in a memory-crunched system, you should also check the storage requirement of the collection. If it takes up too much memory, you might have to resort to something else. For example, if all you need is to add elements at the end and process them from the front, a Queue<T>
would do just fine and you don’t need a List<T>
which is more heavyweight.
Construction versatility:
The easier it is to create the generic container, the better. It’s better if a collection offers more variations in constructor, because you always remain prepared for unprecedented situations. You would never know how much information you would need to create a collection.
Native bsearch support:
Binary search is crucial to finding an item in a long list. You can always use the BinarySearch()
method of an Array
class; however, if native support is available, that’s better. You would save a couple of boxing and unboxing calls.
Speed of set operations:
Although you can perform all set operations via LINQ, resort to one proper set implementation if you need a set.
Code readability:
Make sure to choose a collection that signals your intent more obviously than others, resulting in more readable code.
Least effort to migrate:
Remember that the element of least surprise always works. Select collections that are available conceptually in several other languages.
3.145.12.0