On Wed, 19 Oct 2016 at 13:21 Sam Kellett <samkellett@gmail.com> wrote:

done: https://svn.boost.org/trac/boost/ticket/12536

i'm happy to take a stab at implementing this if you're happy to review it?

While I hesitate to assume I know the best solution to anyone else's particular problem, I have to question the real usefulness of this in terms of flat_set and flat_map. Typically, such a small space optimisation is applicable when 90% of one's use cases fall within the small size. For strings and vectors, this makes sense because there could be anywhere from a few items, to many items. 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. -- chris

I would say that it's likely the opposite - larger flat containers will have more expensive insert and erase.

That's true, but often the data is relatively stable, in which case the flat containers are a good choice.

Flat containers are especially useful with small number of (small) elements because they are cache-friendly, and small size optimization makes perfect sense to improve that use case even further.

It is my experience that the flat containers *always* outperform the node based containers on searching. So when the data is stable, I always use a flat container regardless of how many elements are in the container. One of the problems with that approach is that, because insert is slow, I often have to build up a std::vector of items, sort it and then copy them into the flat container using the ordered_unique_t overload. If this change was done in a way that allowed me to pass ownership of that sorted vector to the flat_* container, that would be an additional optimisation I would find useful. -- chris

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