CppCon 2019

The proposed new STL containers "flat_set" and "flat_map" work like "priority_queue" in that they adapt some existing container, such as std::vector or std::deque, by combining it with other user-provided components, such as a comparator. Such composed types generally impose vague semantic requirements on their components; for example, a composed type might implicitly require that copy-construction and assignment do "the natural thing." These semantic requirements are hardly ever stated explicitly in the Standard; instead, they fall out of common vendor implementations.

In committee discussion of "flat_map", it was noticed that container adaptors such as "priority_queue" also implicitly require some sort of exception guarantee. Not only does the library require that successful copy-assignment actually do assignment, but also, the library generally requires that unsuccessful copy-assignment should do nothing at all — a property referred to as the "strong exception guarantee."

Arthur will show some examples where a user-provided comparator that throws can break the class invariants of "priority_queue". Once the class invariants of a container have been broken, we say that the container is in a "mostly invalid" state — a different and even more dangerous state than the "valid but unspecified" state of a moved-from object. We'll walk through several strategies for inserting values into a flat_map and show how each one breaks down when confronted with a throwing move-constructor, a throwing comparison, or both. Finally, Arthur will suggest a path forward for formalizing the currently underspecified behavior of STL types that rely on user-provided components.