Comparison of C++ STL collections and C# collections?

Question

I'm still learning C# and was surprised to find out that a List<T> is much more like a std::vector than a std::list. Can someone describe all the C# collections in terms of the STL (or if STL comparisons are difficult, standard conceptual data types with Wikipedia links? I expect the reference would be widely useful.

A minimal list of collections of interest include (feel free to add others):

• Array
• List
• ArrayList
• HashTable
• Dictionary
• ListDictionary
• SortedDictionary
• SortedList
• Queue
• Stack

Answer 1

Incomplete list:

• Array - C array
• List/ArrayList - std::vector or std::deque
• HashTable/Dictionary - std::unordered_map (in C++0x)
• SortedDictionary - std::map
• Queue - std::queue (adapter class)
• Stack - std::stack (adapter class)
• LinkedList - std::list or std::deque
• SortedSet (.NET 4) - std::set
• HashSet (.NET 3.5) - std::unordered_set (in C++0x)

std::deque seems to be some sort of hybrid between a std::list and a std::vector. That's why it's listed at two different places.

Answer 2

Here's what I've found (ignoring the old non-generic collections):

• Array - C array, though the .NET Array can have a non-zero starting index.
• List<T> - std::vector<T>
• Dictionary<TKey, TValue> - hash_map<Key, Data> (not standard)
• HashSet<T> - hash_set<Key> (not standard)
• SortedDictionary<TKey, TValue> - std::map<Key, Data>
• SortedList<TKey, TValue> - equivalent to a std::vector<T> but keeping it ordered by using binary search + insert when adding elements.
• SortedSet<T> - std::set<Key>
• Queue<T> - std::queue<T>
• Stack<T> - std::stack<T>
• LinkedList<T> - std::list<T>

Notably missing from the .NET collections are the "multi-" variants, e.g., multiset, multimap, etc. However, they have added a number of very useful threadsafe collections: the "Concurrent-" variants, e.g., ConcurrentDictionary, ConcurrentQueue, etc.