Re: [container] Draft development plan for Boost.Container

From: Marc Glisse (marc.glisse_at_[hidden])
Date: 2024-05-26 20:53:07

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/cow_string.h;h=5d81bfc1230e44fc841098148586f6ca1e4770d1;hb=HEAD#l72

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