id	summary	reporter	owner	description	type	status	milestone	component	version	severity	resolution	keywords	cc
9839	Improve flat_containers performance during insertion phases	gonzalobg88@…	Ion Gaztañaga	"The problem:

A lot of applications have ""look-up"" phases and ""insertion"" phases. In each phase, lots of lookups/insertions take place. However, inserting elements into a flat_ container is slow.

The current way to do this is: copy data out, insert, sort, unique, copy data back in (using the constructor that takes a sorted_uniqued_range). This requires two times the memory necessary, and performs two unnecessary O(N) traversals (the two copies).

In the mailing list this issue was discussed [0], but no action was taken.

The solutions:

Proposal 1) Allow push_back_unsorted + sort
Proposal 2) Allow underlying vector to be moved out/push_back/sort/unique/move back in/assert its good in debug mode

I prefer Proposal 2) since I think is safer, so I'll elaborate on it.

I propose two expand the interface of flat_containers with the following two methods:
  - Data&& retrieve_data();
  - void adquire_data(Data&& d);

retrieve_data moves the underlying vector container out of the flat_container, makes the flat_container an empty container (s.t. it remains valid, are invariants are fine).

adquire_data copies/moves a vector container of the same type as the one used by flat_containers, it assert in debug mode only that the container is sorted (and uniqued if necessary), and sets all container invariants to match the new data.

IMO the underlying vector type should be configurable, but that is a different topic.

[0] google: Containers-Should-flat-expose-implementation-vector-td3722533, trac doesn't like links :("	Feature Requests	closed	To Be Determined	container	Boost Development Trunk	Optimization	fixed