C++ Vector like class in C#

Question

What is the analogous class of C++ std::vector in C#?

I want a class where it keeps an internal array inside and supports insertion at the back in O(1) time.

Solution

Here is a list with some C++ / C# containers that are roughly equivalent (not exact replacements) to each other:

• std::vector -> List<T>

• std::list -> LinkedList<T>

• std::map -> SortedDictionary<Tkey, Tvalue>

• std::set -> SortedSet<T>

• std::unordered_set -> HashSet<T>

• std::multiset -> SortedDictionary<Tkey, int> (int keeping count of the number of Tkeys)

• std::unordered_map -> Dictionary<TKey, TValue>

Comments

[Weyland Yutani]

std::set - HashSet<T> ?

[Cole Tobin]

But the OP wants O(1) insertion time, which doesn't exist in vector or List.

[Weyland Yutani]

surely vector and list are O(1) insert, doesnt say anything about sorting

[harold]

OP only asks for O(1) insertion at the back

[Hamlet Hakobyan]

List<T> have O(1) in add at the back if the size less than capacity. It s very important.

[w128]

Using List.Add() can become O(n) operation if capacity change is needed. LinkedList, however, guarantees O(1) back insertion.

[harold]

List.Add is O(1) amortized, that might count too - actually it probably does, because OP explicitly asks for an array-backed datastructure.

[Sam]

@WeylandYutani: neither List<T> nor vector are O(1) for all insertions (only those that happen at index == count, and if a resize occurs this wouldn't be the case either).

[Weyland Yutani]

ah i was confusing insert in middle with replace

[CMircea]

std::set is equivalent to SortedSet; std::unordered_set is HashSet. Same for std::map.

[Enamul Hassan]

If you have another question, please ask it by clicking the Ask Question button.

[Benji Altman]

std::vector is not backed by a linked list, it specifically stores data contiguously in memory (like an array). Source: cplusplus.com/reference/vector/vector - second paragraph.