C++ - Containers

Last Updated: 2022-02-05

https://en.cppreference.com/w/cpp/container

TL;DR

std::vector should be the default option for sequences
absl::flat_hash_map and absl::flat_hash_set should be used for most associative containers.

Traits

Pointer Stability

Pointer stability / Reference stability: if a pointer / reference to a key or value in a map is guaranteed to remain valid for the lifetime of the map.

All elements of a container that does not guarantee pointer stability may be invalidated when the container is inserted to (flat_hash_map and btree_map) or removed from (btree_map only).

Saying that a container has pointer stability is the same as saying that it doesn't move elements in memory; their addresses do not change. Pointer stability/invalidation is the same as reference stability/invalidation.

Stable Iteration Order

Stable iteration order: if the order of the elements is consistent across different instances of a container and different runs of the same binary.

For example: std::unordered_set<string> container = {"a", "b", "c"}; or absl::flat_hash_set does not always produce the same output if calling absl::StrJoin(container, ",");.

Choice of maps

Does not require pointer-stability (ordering is not required): use absl::flat_hash_map (A "flat" map is backed by a contiguous array)
Requires pointer-stability of values (but not keys): use absl::flat_hash_map<Key, std::unique_ptr<Value>>.
Requires pointer-stability of both keys and values (ordering is not required): use absl::node_hash_map
If sorted order is required Use absl::btree_map (pointer stability is not required)
std::map provides ordering and pointer stability

flat_hash_map and flat_hash_set

absl::flat_hash_map and absl::flat_hash_set are the recommended unordered containers for general use.

They are more efficient but don't provide guarantees on pointer or iterator stability that std::unordered_map does. The standard maps guarantee that elements that have been inserted are never moved, so that pointers and references to them stay valid so long as the element remains present in the map.

Use absl::node_hash_map and absl::node_hash_set for guaranteed pointer stability. Or use unique_ptr like absl::flat_hash_map<std::string, std::unique_ptr<std::string>>