On Wed, 24 Jul 2013, Howard Hinnant wrote:

> This is a crude model of std::map<T, U>::value_type that would allow
> map's copy assignment operator to recycle nodes, instead of deleting all
> nodes in the lhs prior to inserting new ones. Here is a an example
> chart of the performance of the copy assignment of a map<int, int> when
> the rhs has 1000 values, the lhs has between 0 and 2000 values (prior to
> the assignment), and the implementation is varied between a simple
> clear()/insert(), a structural copy (avoids rebalancing the lhs at each
> insert), and recycling nodes using something very similar to what is
> sketched above with the union V.
>
> As it stands today, even though no compiler gets this wrong, if I want
> this code to be completely guarded against a future optimizer exploiting
> the undefined behavior in V 10 years from now, I need to write the map
> copy assignment operator in assembly (which would be extraordinarily
> challenging - so much so it will never happen).
>
> The compiler writer's drive to eek out a few % optimization, and backed
> by this committee, is preventing me from delivering a 2X to 3X
> performance optimization in std::map's copy assignment operator. That
> means something is wrong. I hope we can fix it, and have every faith
> that we can with everyone's help here.

What I am wondering is if you are trying to compensate for a bad design in
the library's API by asking for more core features. I may have missed many
points, so please be patient and don't take it as a criticism against the
people who designed std::map.

If I understand correctly, if instead of pair<const K, T> we used pair<K,
T> as the value type in the map, your technique would be completely
straightforward. Now we are not doing that because we want to make it not
too easy for a user to modify the key. So we would like to have a
pair<K,T> internally but present to the user something like a pair<const
K, T> interface. Well, that seems hard. But if we didn't insist on using a
simple aggregate and instead had a regular class with accessors (use
first() instead of first, etc), it wouldn't be hard to present a different
interface to the user and to the internal functions of std::map.

Does that make sense?

-- 
Marc Glisse