In my HPC-oriented programming, my go-to choices are typically limited to arrays and vectors because of their memory efficiency. Linked lists and hash maps, being non-contiguous in memory space, rarely find their way into my toolkit. These containers draw upon many classic algorithmic designs. Lately, as I’ve been revisiting fundamental graph algorithms, I’ve also decided to take on the tasks of re-implementing these containers in a simplified illustration.

They are:

C++98: std::map, std::set, std::multimap, and std::multiset
C++11: std::unordered_map, std::unordered_set, std::unordered_multimap, and std::unordered_multiset
C++23: std::flat_map, std::flat_set, std::flat_multimap, and std::flat_multiset

Sequence Containers

Data structures which can be accessed sequentially.

std::array<T,size>
std::vector<T>
std::deque<T>
std::list<T>
std::forward_list<T>

Sequence Containers

Associative Containers

Sorted data structures (i.e., balanced binary search tree) that can be quickly searched (O(log n) complexity).

std::set<T>
std::multiset<T>
std::map<Key, Value>
std::multimap<Key, Value>

Associative Containers

Typically, an associate container consists a data type(s), a comparison function, and an allocator

template<typename Key, 
         typename Value,
         typename Compare = std::less<key>,
         typename Allocator = std::allocator<std::pair<const Key, Value>>>

Unordered Associative Containers

Unsorted data structures (i.e., hashing bucket) that can be quickly searched (O(1) average, O(n) worst-case complexity).

std::unordered_set<T>
std::unordered_map<Key, Value>
std::unordered_multiset<T>
std::unordered_multimap<Key, Value>

Unordered Containers

Typically, an unordered associate container consists a data type(s), a hash function, an equal function and an allocator. The equal function indicates this type of containers does not provide support for comparison.

template<
    typename Key,
    typename T,
    typename Hash = std::hash<Key>,
    typename KeyEqual = std::equal_to<Key>,
    typename Allocator = std::allocator<std::pair<const Key, T>>
>

Container adaptors

A different interface for sequential containers.

std::stack<T>
std::queue<T>
std::priority_queue<T>
std::flat_set (c++23)
std::flat_map (c++23)
std::flat_multiset (c++23)
std::flat_multimap (c++23)

The flat-ordered associative containers in C++23 have the same interface as their C++98 pendants. They adopt from sequence containers, e.g., std::vector by default.