Re: [boost] [container] small_flat_set and small_flat_map

Subject: Re: [boost] [container] small_flat_set and small_flat_map
From: Seth (bugs_at_[hidden])
Date: 2016-10-19 16:44:09

On 19-10-16 19:51, Chris Glover wrote:
> But, typically set or map is chosen precisely because there will be many
> items in the container, otherwise you would choose something else, like an
> unsorted array like structure. So, to me the case of optimising for the
> small size makes little sense.

This is anecdotal only. You have to ask WHY is "set or map [typically]
chosen precisely because...". The main reason might well be "because the
cost of node-based data structures is too high for small volumes" not
because they're not a good match.

Quite often I need small collections of characters (say, characters to
be escaped) which are logically best expressed as a set.

It's just a lot more readably to use a set than to use e.g. a your
small_vector<char> and manually maintain sort order and deduplication.
The only reason NOT to use a set when logically it is a set was performance.

Tiny local maps are frequent occurrence too. I find myself writing
linear searches across local vector<pair<Id, reference_wrapper<T const>
>. Imagine how much better it would be with `small_flat_map<Id,
reference_wrapper<T const> >`.

Summarizing: I find myself focusing on expressive code and often find
myself hindered by the lack of low-cost small associative/ordered
containers.

My $0.02

Seth