Stored Types

struct with_particle { using comparable_particle = int; };
struct without_particle {};
static_assert(has_comparable_particle<with_particle>::value, "Should have comparable_particle");
static_assert(!has_comparable_particle<without_particle>::value, "Should not have comparable_particle");

Otherwise, exposes can_be_mapping_type_ itself as ::type.

using pair = mapping<int, std::string>;
static_assert(std::is_same_v<mapping_key_type_or_itself<pair>::type, int>, "Must be int");
static_assert(std::is_same_v<mapping_key_type_or_itself<double>::type, double>, "Must be double");

Otherwise, exposes void as ::type.

using pair = mapping<int, std::string>;
static_assert(std::is_same_v<mapped_value_type_or_void<pair>::type, std::string>, "Must be string");
static_assert(std::is_same_v<mapped_value_type_or_void<double>::type, void>, "Must be void");

Correctness of Comparisons

For std::set, std::map, or similar containers we only require the keys to provide strict-weak-ordering comparisons. It's enough to simply define a comparator that returns a boolean result for two comparable objects. Since C++ 20, comparisons are better formalized:

• std::strong_ordering - equivalent values are fully interchangeable, all are comparable!
• std::weak_ordering - equivalent values may be non-interchangeable, but all are comparable!
• std::partial_ordering - equivalent values may be non-interchangeable or incomparable!

Assuming that float values can be NaN and thus incomparable, we shouldn't be able to construct a std::set<float> since the ordering is only partial, but GCC still compiles it.

Optimization Opportunities

Oftentimes, when dealing with heavy objects as keys (e.g., strings, composite structures), we want to avoid storing many copies of the full object just to perform comparisons and lookups. Instead, we can distill a lightweight "particle" from the heavy object that captures its identity for ordering purposes. Examples may be:

• Non-owning std::string_view for std::string keys
• Integer identifiers extracted from composite structures

If the comparator_type_ has a value_type member - indicating some form of a unique identifier can be distilled from comparable_type_ - we expose it via ::type. Else, if the comparable_type_ is a mapping, we use its key_type as the identifier. Else, we use the comparable_type_ itself as the identifier.

A node-based container returns a reference to the element it holds, so the two coincide; an open-addressed table keeps keys and values in separate regions and can only view an entry as a pair of references, which nothing above it can own, copy, or version.

An ordered surface walks nodes directly; an open-addressed table has none to walk, and naming one unconditionally would break the adapter at its own definition rather than at the call.

An integer identity below 2^64 has a zero high and its value in low.

Saves a .status() at the call site, and reads the way the question is asked out loud. C++20 synthesizes the reversed and negated forms, so this one definition covers all four spellings.

Converting an identifier into itself would ask for its copy constructor, which a key owning its bytes deletes in favour of copy.

Useful for generic code that works with both mappings and simple keys.

Sized rather than measured: a cache line is 64 bytes on most cores and 128 on others, and a page is 4096 bytes until an operating system is configured otherwise, so neither is a constant this header could state. A block sits between them and divides evenly by every key width here.