flat_set.hpp File Reference

Flat (unsorted, contiguous-storage) set template. More...

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

Include dependency graph for flat_set.hpp:

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

Go to the source code of this file.

Classes
struct	flat_set< T, Storage, hash >
	Flat set with pluggable storage. More...
struct	std::hash< flat_set< T, Storage, h > >
	std::hash specialisation for flat_set, enabling use as an unordered container key. More...

Namespaces
namespace	std

Detailed Description

Flat (unsorted, contiguous-storage) set template.

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

flat_set<T, Storage, hash> is a lightweight set container that stores elements in a contiguous sequence. It is the set analogue of flat_map, with the same trade-offs: O(n) membership tests but cache-friendly performance for small sets, and pluggable storage for stack allocation.

ProvSQL uses this as the suspicious_t type in dDNNFTreeDecompositionBuilder (a set of gates bounded by the treewidth + 1 of the circuit), and as the bag type Bag in TreeDecomposition.

A std::hash specialisation is provided so that flat_set can be used as a key in std::unordered_map (via the hash template parameter for the element hash).

Definition in file flat_set.hpp.