On Sat, 25 May 2024, Ion Gaztañaga via Boost wrote:
- vector optimized for the empty case: I was going to suggest it, but I now see you have added it to the document since the initial post :-)
Thanks. Do you know any public reference implementation of this idea or some talk/paper that explains the advantages, some benchmark etc.? I tried to find some information when writing the plan, but I couldn't find something relevant.
I didn't have much success with a quick google search either, so I'll have to go from memory. I seem to remember from previous discussions on the subject that there were several partial implementations in the wild, with one in a famous web browser in particular, but that was a long time ago. On the other hand, the reference-counted version of std::string that libstdc++ can still use in compatibility mode does use this strategy of a pointer to a region that contains both a header and the actual elements. https://gcc.gnu.org/git/?p=gcc.git;a=blob;f=libstdc%2B%2B-v3/include/bits/co... My use-case (though we did something else in the end) would have been for a tree where nodes can have an arbitrary number of children, and leaves are more numerous than internal nodes. The vector would have been hidden in a flat_map. -- Marc Glisse