[moderator's note: forwarded to C++ committee -sdc]

map::operator[] specification forces inefficient implementation

   Section: 23.3.1.2 lib.map.access
    Status: New
 Submitter: Andrea Griffini
      Date: Sept-02-2001

The current standard describes map::operator[] using a
code example. That code example is however quite
inefficient because it requires several useless copies
of both the passed key_type value and of default
constructed mapped_type instances.
My opinion is that was not meant by the comitee to
require all those temporary copies.

Currently map::operator[] behaviour is specified as:

  23.3.1.2  map element access       [lib.map.access]

  T& operator[](const key_type& x);

  Returns:
    (*((insert(make_pair(x, T()))).first)).second.

This specification however uses make_pair that is a
template function of which parameters in this case
will be deduced being of type const key_type& and
const T&. This will create a pair<key_type,T> that
isn't the correct type expected by map::insert so
another copy will be required using the template
conversion constructor available in pair to build
the required pair<const key_type,T> instance.

If we consider calling of key_type copy constructor
and mapped_type default constructor and copy
constructor as observable behaviour (as I think we
should) then the standard is in this place requiring
two copies of a key_type element plus a default
construction and two copy construction of a mapped_type
(supposing the addressed element is already present
in the map; otherwise at least another copy
construction for each type).


Proposed Resolution:

A simple (half) solution would be replacing the description with

  23.3.1.2  map element access       [lib.map.access]

  T& operator[](const key_type& x);

  Returns:
    (*((insert(value_type(x, T()))).first)).second.

This will remove the wrong typed pair construction that
requires one extra copy of both key and value.

However still the using of map::insert requires temporary
objects while the operation, from a logical point of view,
doesn't require any.

I think that a better solution would be leaving free an
implementer to use a different approach than map::insert
that, because of its interface, forces default constructed
temporaries and copies in this case.
The best solution in my opinion would be just requiring
map::operator[] to return a reference to the mapped_type
part of the contained element creating a default element
with the specified key if no such an element is already
present in the container. Also a logarithmic complexity
requirement should be specified for the operation.

This would allow library implementers to write alternative
implementations not using map::insert and reaching optimal
performance in both cases of the addressed element being
present or absent from the map (no temporaries at all and
just the creation of a new pair inside the container if
the element isn't present).
Some implementer has already taken this option but I think
that the current wording of the standard rules that as
non-conforming.

Note that this is a "relaxing" of requirment and won't
make any currently conforming implementation on this
point to become non-conforming because of the change.

There is a small risk that current code may be depending
on the number of temporaries created by map::operator[];
but I think that such dependencies would be present only
in code that is most probably already non portable as
the number of copies of parameters isn't guaranteed by
the standard (in the current wording there's just an
implicit *minimum* number of required copies).


HTH
Andrea
-----------------------------------------------------------------------
 <\___/>  Andrea        email: agriff at tin dot it
 / . . \  "6502"          irc: _6502_@EFNET#italia
(  (")  ) Griffini   homepage: http://www.netservers.com/~agriff



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]