Section: 23.4.3.3 [map.access] Status: CD1 Submitter: Andrea Griffini Opened: 2001-09-02 Last modified: 2016-01-28
Priority: Not Prioritized
View all other issues in [map.access].
View all issues with CD1 status.
Discussion:
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:
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).
A simple (half) solution would be replacing the description with:
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.
Proposed resolution:
Replace 23.4.3.3 [map.access] paragraph 1 with
-1- Effects: If there is no key equivalent to x in the map, inserts value_type(x, T()) into the map.
-2- Returns: A reference to the mapped_type corresponding to x in *this.
-3- Complexity: logarithmic.
[This is the second option mentioned above. Howard provided wording. We may also wish to have a blanket statement somewhere in clause 17 saying that we do not intend the semantics of sample code fragments to be interpreted as specifing exactly how many copies are made. See issue 98 for a similar problem.]
Rationale:
This is the second solution described above; as noted, it is consistent with existing practice.
Note that we now need to specify the complexity explicitly, because
we are no longer defining operator[] in terms of
insert.