Boost C++ Libraries: Ticket #9839: Improve flat_containers performance during insertion phases

Thu, 24 May 2018 13:08:36 GMT

Why can't flat_* sort it by itself when pushing the data back?

anonymous — Thu, 24 May 2018 13:56:40 GMT

That would mean that each push back has a complexity of O(N), which means that push_back in a loop has a complexity of O(N^{2). The approach proposed in this issue makes the complexity of bulk insertion O(NlogN) which is much better than O(N}2).

Thu, 24 May 2018 14:03:56 GMT

No no, I meant sort it inside void adquire_data(Data&& d) itself.

anonymous — Thu, 24 May 2018 14:27:07 GMT

Ah, I see. Well, it can. I wrote that it should just assert in debug mode that the data is sorted, which is O(N). This allows the user to choose the sorting algorithm that suits best whatever it's doing.

An alternative is to always sort the data, or to provide two methods:

adquire_data which always sorts the data,
adquire_data_sorted which assumes the data is sorted (and checks it in debug mode)

Ion Gaztañaga — Thu, 24 May 2018 20:36:03 GMT

This was already implemented:

https://www.boost.org/doc/libs/1_67_0/doc/html/boost/container/flat_map.html

See members:

sequence_type extract_sequence(); void adopt_sequence(sequence_type &&); void adopt_sequence(ordered_unique_range_t, sequence_type &&);

using these functions a user can use a sequence_type (vector, by default), fill it, and do a single "adopt_sequence" call to sort data.

Fri, 25 May 2018 06:41:16 GMT

OMG, thanks, this is the second time I missed something.

status changed; resolution set

Ion Gaztañaga — Sun, 17 Jun 2018 10:50:30 GMT

status new → closed
resolution → fixed

Resolving it as it was implemented in Boost 1.67. Thanks for the report.