Array-like containers aren’t the only containers we need. Today we’ll look at the non-array containers the C++ Standard Library provides, including its equivalents of Dictionary, HashSet, and LinkedList.

Table of Contents

Unordered Map

The <unordered_map> header provides C++’s Dictionary equivalent: std::unordered_map. As with other containers like std::vector, it “owns” the memory that keys and values are stored in. Here’s a sampling of the API:

#include <unordered_map>
 
void Foo()
{
    // Hash map of int keys to float values
    std::unordered_map<int, float> ifum{};
 
    // Add a key-value pair
    ifum.insert({ 123, 3.14f });
 
    // Read the value that 123 maps to
    DebugLog(ifum[123]); // 3.14
 
    // Try to read the value that 456 maps to
    // There's no such key, so insert a default-initialized value
    DebugLog(ifum[456]); // 0
 
    // Query size
    DebugLog(ifum.empty()); // false
    DebugLog(ifum.size()); // 2
    DebugLog(ifum.max_size()); // Maybe 768614336404564650
 
    // Try to read and throw an exception if the key isn't found
    DebugLog(ifum.at(123)); // 3.14
    DebugLog(ifum.at(1000)); // throws std::out_of_range exception
 
    // insert() does not overwrite
    ifum.insert({ 123, 2.2f }); // does not overwrite 3.14
    DebugLog(ifum[123]); // 3.14
 
    // insert_or_assign() does overwrite
    ifum.insert_or_assign(123, 2.2f); // overwrites 3.14
    DebugLog(ifum[123]); // 2.2
 
    // emplace() constructs in-place
    ifum.emplace(456, 1.123f);
 
    // Remove an element
    ifum.erase(456);
    DebugLog(ifum.size()); // 1
} // ifum's destructor deallocates the memory storing keys and values

A std::unordered_multimap is also available for when there are potentially multiple of the same key. C# has no equivalent of this class template, but it can be approximated with a Dictionary<TKey, List<TValue>>. Here’s how to use it:

#include <unordered_map>
 
void Foo()
{
    // Create an empty multimap that maps int to float
    std::unordered_multimap<int, float> ifumm{};
 
    // Insert two of the same key with different values
    ifumm.insert({ 123, 3.14f });
    ifumm.insert({ 123, 2.2f });
 
    // Check how many values are mapped to the 123 key
    DebugLog(ifumm.count(123)); // 2
 
    // C++20: check if there are any values mapped to the 123 key
    DebugLog(ifumm.contains(123)); // true
 
    // Find one of the key-value pairs for the 123 key
    const auto& found = ifumm.find(123);
    DebugLog(found->first, found->second); // Maybe 123, 3.14
 
    // Loop over all the key-value pairs for the 123 key
    auto range = ifumm.equal_range(123);
    for (auto i = range.first; i != range.second; ++i)
    {
        DebugLog(i->first, i->second); // 123, 3.14 and 123, 2.2
    }
 
    // Remove all the key-value pairs with a given key
    ifumm.erase(123);
    DebugLog(ifumm.size()); // 0
} // ifumm's destructor deallocates key and value memory

C++20 adds the usual std::erase_if non-member function found with the array container types to work with std::unordered_map and std::unordered_multimap:

#include <unordered_map>
 
// Create maps with 2 key-value pairs each
std::unordered_multimap<int, float> umm{ {123, 3.14}, {456, 2.2f} };
std::unordered_map<int, float> um{ {123, 3.14}, {456, 2.2f} };
 
// Erase all the key-value pairs where the key is less than 200
auto lessThan200 = [](const auto& pair) {
    const auto& [key, value] = pair;
    return key < 200;
};
std::erase_if(um, lessThan200);
std::erase_if(umm, lessThan200);
 
// 123 key has 0 values associated with it
DebugLog(um.count(123)); // 0
DebugLog(umm.count(123)); // 0
Map

The <map> header provides ordered versions of std::unordered_map and std::unordered_multimap. They’re called, naturally, std::map and std::multimap. The basics of their APIs are very similar to the unordered counterparts, which helps with generic programming, but there are also some differences.

Let’s start with std::map, which is typically a red-black tree. The closest C# equivalent to this container is OrderedDictionary, but that class doesn’t support generic key and value types unlike std::map and Dictionary. Here’s a sampling of the std::map functionality:

#include <map>
 
void Foo()
{
    // Create a map with three keys
    std::map<int, float> m{ {456, 2.2f}, {123, 3.14}, {789, 42.42f} };
 
    // Many functions from other containers are available
    DebugLog(m.size()); // 3
    DebugLog(m.empty()); // false
    m.insert({ 1000, 2000.0f });
    m.erase(123);
    m.emplace(100, 9.99f);
 
    // Ordering by key is guaranteed
    for (const auto& item : m)
    {
        DebugLog(item.first, item.second);
        // Prints:
        //   100, 9.99
        //   456, 2.2
        //   789, 42.42
        //   1000, 2000
    }
} // m's destructor deallocates key and value memory

Like std::unordered_multimap, std::multimap also has no C# equivelent. We can approximate it with an OrderedDictionary whose values are List<TValue> objects but with the same downside of OrderedDictionary not supporting generic key and value types. Regardless, std::multimap supports mapping multiple of the same key and is also typically a red-black tree. Values are stored in insertion order:

#include <map>
 
void Foo()
{
    // Create a multimap with three keys: two are duplicated
    std::multimap<int, float> mm{ {456, 42.42f}, {123, 3.14f}, {123, 2.2f} };
 
    // Many functions from other containers are available
    DebugLog(mm.size()); // 3
    DebugLog(mm.empty()); // false
    mm.insert({ 1000, 2000.0f });
    mm.erase(456);
    mm.emplace(100, 9.99f);
 
    // Ordering by key is guaranteed
    for (const auto& item : mm)
    {
        DebugLog(item.first, item.second);
        // Prints:
        //   100, 9.99
        //   123, 3.14
        //   123, 2.2
        //   1000, 2000
    }
} // mm's destructor deallocates key and value memory
Unordered Set

The <unordered_set> header provides the equivalent of HashSet in C#: std::unordered_set. It’s like a std::unordered_map except that there are only keys so the API is simpler:

#include <unordered_set>
 
void Foo()
{
    // Create a set with four values
    std::unordered_set<int> us{ 123, 456, 789, 1000 };
 
    // Many functions from other containers are available
    DebugLog(us.size()); // 4
    DebugLog(us.empty()); // false
    us.insert(2000);
    us.erase(456);
    us.emplace(100);
    DebugLog(us.count(123)); // 1
} // us's destructor deallocates value memory

A std::unordered_multiset is also available to support multiple of the same value. There’s no C# version of this, but a Dictionary<TKey, int> can be used to approximate it by using the value to count the number of keys. That takes additional memory and is somewhat awkward to use compared the straightforward API of std::unordered_multiset:

#include <unordered_set>
 
void Foo()
{
    // Create a multiset with six values: two are duplicated
    std::unordered_multiset<int> ums{ 123, 456, 123, 789, 1000, 1000 };
 
    // Many functions from other containers are available
    DebugLog(ums.size()); // 6
    DebugLog(ums.empty()); // false
    ums.insert(2000);
    ums.erase(123); // erases both
    ums.emplace(100);
    DebugLog(ums.count(1000)); // 2
} // ums's destructor deallocates value memory
Set

As with maps, ordered versions of the set classes are available. Predictably, the <set> header provides std::set and std::multiset. Both are implemented with more red-black trees. C# has a SortedSet class equivalent to std::set but not equivalent to std::multiset.

The APIs of both std::set and std::multiset are also very similar to their unordered counterparts. Here’s std::set:

#include <set>
 
void Foo()
{
    // Create a set with four values
    std::set<int> s{ 123, 456, 789, 1000 };
 
    // Many functions from other containers are available
    DebugLog(s.size()); // 4
    DebugLog(s.empty()); // false
    s.insert(2000);
    s.erase(456);
    s.emplace(100);
    DebugLog(s.count(123)); // 1
 
    // Ordering by key is guaranteed
    for (int x : s)
    {
        DebugLog(x);
        // Prints:
        //   100
        //   123
        //   789
        //   1000
        //   2000
    }
} // s's destructor deallocates value memory

And here’s std::multiset:

#include <set>
 
void Foo()
{
    // Create a multiset with six values: two are duplicated
    std::multiset<int> ms{ 123, 456, 123, 789, 1000, 1000 };
 
    // Many functions from other containers are available
    DebugLog(ms.size()); // 6
    DebugLog(ms.empty()); // false
    ms.insert(2000);
    ms.erase(123); // erases both
    ms.emplace(100);
    DebugLog(ms.count(1000)); // 2
 
    // Ordering is guaranteed
    for (int x : ms)
    {
        DebugLog(x);
        // Prints:
        //   100
        //   456
        //   789
        //   1000
        //   1000
        //   2000
    }
} // ms's destructor deallocates value memory
List

Next up is the <list> header and it’s std::list class template that implements a doubly-linked list. This is equivalent to the LinkedList class in C#. It’s API is similar to std::vector except that operations on the front of the list are also supported and indexing isn’t allowed since that would require an expensive walk of the list:

#include <list>
 
void Foo()
{
    // Create an empty list
    std::list<int> li{};
 
    // Add some values
    li.push_back(456);
    li.push_front(123);
 
    // Grow by inserting default-initialized values
    li.resize(5);
 
    // Query size
    DebugLog(li.empty()); // false
    DebugLog(li.size()); // 5
 
    // Indexing isn't supported. Loop instead.
    for (int x : li)
    {
        DebugLog(x);
        // Prints:
        //   123
        //   456
        //   0
        //   0
        //   0
    }
 
    // Remove values
    li.pop_back();
    li.pop_front();
 
    // Special operations
    li.sort();
    li.remove(0); // remove all zeroes
    li.remove_if([](int x) { return x < 200; }); // remove all under 200
} // li's destructor deallocates value memory
Forward List

A singly-linked list, std::forward_list, is also provided via <forward_list>. C# doesn’t provide an equivalent container. The API is like the reverse of std::vector since only operations on the front of the list are supported. Unlike most other containers, a size function isn’t provided since it would require walking the entire list to count nodes:

#include <forward_list>
 
void Foo()
{
    // Create an empty list
    std::forward_list<int> li{};
 
    // Add some values
    li.push_front(123);
    li.push_front(456);
 
    // Grow by inserting default-initialized values
    li.resize(5);
 
    // Query size
    DebugLog(li.empty()); // false
 
    // Indexing isn't supported. Loop instead.
    for (int x : li)
    {
        DebugLog(x);
        // Prints:
        //   123
        //   456
        //   0
        //   0
        //   0
    }
 
    // Remove values
    li.pop_front();
 
    // Special operations
    li.sort();
    li.remove(0); // remove all zeroes
    li.remove_if([](int x) { return x < 200; }); // remove all under 200
} // li's destructor deallocates value memory
Conclusion

The C++ Standard Library provides a robust and consistent offering of non-array collection types to go along with array collection types like std::vector. The APIs are all very similar, which is great for generic programming as the collection type can easily be made into a type parameter.

Whether we need a set, map, or list, ordering or hashing, and even support for duplicate keys or values, a class template is on offer. In contrast, C#’s offerings are more limited as there’s sometimes no generic version, no support for duplicate keys, or no class that handles ordering. These may be less-common use cases, but it’s nice to have standardized tools available when needed.