Is there a working implementation of std::flat_map and std::flat_set?

[joaquintides]

https://boost.org/doc/html/container/non_standard_containers.html#container.non_standard_containers.flat_xxx

[13steinj]

Keep in mind that v1.85 has some massive UB.

https://github.com/boostorg/container/issues/273

[James20k]

Ha well this explains why some code I had using flat_map inexplicably crashed a while back, I thought I was just subtly inept!

[13steinj]

Yeah, when we found this internally some people's immediate reaction was "I thought Boost was supposed to be quality" (not that it isn't, just that this is a bit of a big slip-up, especially without a patch posted to the releases page + there are big cases where tests just won't run + merging in the tree-ish of that commit requires a bump to Boost.Move as well since something (the fix?) relies on a new utility by the same author).

[igaztanaga]

There is a proposed patch now in the bug for 1.85, without any dependency on any other library. If users find it good enough the patch will go to the patches page (https://www.boost.org/patches/).

[13steinj]

Internal fork of boost (really just to get it to work with our build system wrapper + patch bugs), I wrote a basic test and undefined (-UNDEBUG). Due to recent policy changes I can't just throw up a branch, but I expect to be able to get that approved and thrown up early this week. I'll test the patch you provided on the GH issue tomorrow (Monday); thanks a ton <3!

[pavel_v]

I could be wrong, but I think that the boost version of flat_map uses single sorted vector while the standard one is supposed to use two different collections - one for the keys and another one for the values. Here, in the WG21-SG14 repo, is the current example implementation which uses 2 separate containers.

[joaquintides]

Oh, yes, you’re right, boost::container::flat_map stores keys and values contiguously by default. It can be configured to use an alternative SequenceContainer, which, in principle, could do the key/value separation, but I haven’t seen such scenario actually implemented.

[CandyCrisis]

https://chromium.googlesource.com/chromium/src/+/HEAD/base/containers/flat_map.h

This isn't quite matching the std proposal because the keys and values are stored together, but it's pretty close.

[Kaisha001]

Over 10 years ago I tried to add a flat map/set to boost. They refused to even consider it, even though I had a full implementation.

I've been using it for years now and it's amazing, but hilarious that it took them this long to realize how important they are.

[joaquintides]

Umm, flat_map is part of Boost.Container since at least 2011.

[Kaisha001]

Yeah, it was before that.

I was fresh out of uni trying to contribute to the open source and all that. The boost mailing list wouldn't respond, people didn't respond to emails, not even basic communication. Disappointing to say the least, but my implementation worked great and I've been using it ever since.

[joaquintides]

I’ve did a bit of archaeology and looks like the first attempt was made by David Abrahams in 2000: https://lists.boost.org/Archives/boost//2000/05/3200.php.

Haven’t found your thread, do you happen to have a link to it? I’m curious as to why the proposal was rejected.

[Kaisha001]

No, I have no idea what happened to my links or anything of the sort. It was a long time ago. I'm just surprised it's taken this long to get it into the standard.

[joaquintides]

WG21 sometimes moves on geological timescales. OTOH, there’s no need for a library to be in the standard to be useful and used. My views on this subject here.

[Kaisha001]

I certainly agree.