Yesterday I wrote:
P0429R6 “A Standard
flat_map”: I don’t honestly think
flat_mapis well-baked enough to put into the Standard Library; but at least it’s been in Boost for a while (if I understand correctly)…
The author of Boost.FlatMap, Ion Gaztañaga, informs me via email that my understanding of
flat_map’s Boostness is incorrect.
Between P0429R1 and P0429R2 there is an important change: the layout of flat_map changes to store keys and mapped types separately […]
[…] I’d say there is no implementation experience in Boost for the proposed
flat_mapat all. It is possible, but I haven’t checked, that other libraries use the [split-storage] approach. However, apart from Boost.FlatMap, Alexandrescu’s original
flat_map, and Folly’s
sorted_vector_mapare based on
std::pair<Key,T> value_types and real references. I think there is widespread existing practice on this design.
I honestly think, unless there are some important performance reasons, that separate keys and values are problematic, at least if we want to have an interface similar to
std::map. It breaks references to
value_types, requires proxy types, and complicates the adapter.
(Ion points to the benchmarks in P0429R1 as evidence that those “important performance reasons” have not materialized.)
Ion also frowns on P0429R1’s removal of the
The reason to remove them is that some custom containers don’t have these methods, and we don’t
want to prevent the programmer from using such containers as the underlying container of a
flat_map. It’s important to keep the surface area of the underlying container as small as possible.
Of the four prior-art implementations listed above, only Folly permits using a custom container at all.
shrink_to_fit unconditionally, which means your custom
container type must provide those methods.
But, we can always provide those members conditionally, so that the
flat_map can be
reserveable if-and-only-if the underlying container is
uses this exact technique for
reserve and for
capacity (and will for
I get around to making the pull request). So it’s quite surprising that P0429
provide the same methods conditionally.
We have the technology!
So, I retract my “at least it’s been in Boost for a while” comment. There is no prior implementation
experience for P0429
flat_map… and as far as I can tell, there is no reference implementation, either.
(Proposal author Zach Laine has a
flat_map repository on GitHub,
but it does not contain any implementation — just the TeX source of the paper proposal.)
If WG21 standardizes P0429
flat_map without any implementation, and against all existing implementations,
it’ll really be striking out on its own — in both senses. I advise strongly against that course of action;
I believe P0429 should be tabled until an implementation can be created and some implementation experience
And I volunteer to work on an implementation in the SG14 repo!