flat_map.hpp File Reference

Flat (unsorted, contiguous-storage) associative map template. More...

#include <vector>
#include <utility>
#include <algorithm>

Include dependency graph for flat_map.hpp:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	flat_map< Key, Value, Storage >
	Flat associative map with pluggable storage. More...
struct	std::hash< flat_map< K, V, Storage > >
	std::hash specialisation for flat_map, enabling use as an unordered container key. More...

Namespaces
namespace	std

Detailed Description

Flat (unsorted, contiguous-storage) associative map template.

Heavily inspired from https://stackoverflow.com/a/30938947, credits to Yakk - Adam Nevraum @ StackOverflow

flat_map<Key, Value, Storage> is a lightweight associative container that stores key-value pairs in a contiguous sequence (by default a std::vector, but any compatible random-access container works).

**Trade-offs vs. std::map / std::unordered_map**:

• Lookup and insertion are O(n) (linear scan), but for small maps (up to ~20 elements) cache-friendly linear search outperforms pointer- chasing tree or hash-table traversals.
• The storage type is a template parameter so that boost::container::static_vector can be used, enabling stack allocation and avoiding heap allocation entirely for small maps with bounded keys (e.g. keys bounded by the treewidth + 1 of a circuit).
• No iterator invalidation on insertions for static_vector.

ProvSQL uses this as the valuation_t type in dDNNFTreeDecompositionBuilder: a mapping from gate_t to bool for the current bag's truth-value assignment.

A std::hash specialisation is provided so that flat_map can be used as a key in std::unordered_map.

Definition in file flat_map.hpp.