Defect Report: a.insert(p,t) is incorrectly specified
Mark Rodgers
the C++ committee. -moderator.]
Section 23.1.2 [lib.associative.reqmts] paragraph 7 (table 69)
Closed issue 192 raised several problems with the specification of
this function, but was rejected as Not A Defect because it was too big
a change with unacceptable impacts on existing implementations.
However, issues remain that could be addressed with a smaller change
and with little or no consequent impact.
Issues:
1. The specification is inconsistent with the original proposal and
with several implementations.
The initial implementation by Hewlett Packard only ever looked
immediately _before_ p, and I do not believe there was any
intention to standardise anything other than this behaviour.
Consequently, current implementations by several leading
implementers also look immediately before p, and will only
insert after p in logarithmic time. I am only aware of one
implementation that does actually look after p, and it
looks before p as well. It is therefore doubtful that existing
code would be relying on the behaviour defined in the standard,
and it would seem that fixing this defect as proposed below would
standardise existing practice.
2. The specification is inconsistent with insertion for sequence
containers.
This is difficult and confusing to teach to newcomers. All
insert operations that specify an iterator as an insertion
location should have a consistent meaning for the location
represented by that iterator.
3. As specified, there is no way to hint that the insertion should
occur at the beginning of the container, and the way to hint
that it should occur at the end is long winded and unnatural.
For a container containing n elements, there are n+1 possible
insertion locations and n+1 valid iterators. For there to
be a one-to-one mapping between iterators and insertion locations,
the iterator must represent an insertion location immediately
before the iterator.
4. When appending sorted ranges using insert_iterators, insertions
are guaranteed to be sub-optimal.
In such a situation, the optimum location for insertion is
always immediately after the element previously inserted. The
mechanics of the insert iterator guarantee that it will try and
insert after the element after that, which will never be correct.
However, if the container first tried to insert before the
hint, all insertions would be performed in amortised constant
time.
Proposed Resolution
In 23.1.2 [lib.associative.reqmts] paragraph 7, table 69, make
the following changes in the row for a.insert(p,t):
assertion/note pre/post condition
Change the last sentence from
"iterator p is a hint pointing to where the insert should
start to search."
to
"iterator p is a hint indicating that immediately before p
may be a correct location where the insertion could occur."
complexity
Change the words "right after" to "immediately before".
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std...@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html ]
Gillmer J. Derge
> Issues:
>
> 4. When appending sorted ranges using insert_iterators, insertions
> are guaranteed to be sub-optimal.
>
> In such a situation, the optimum location for insertion is
> always immediately after the element previously inserted. The
> mechanics of the insert iterator guarantee that it will try and
> insert after the element after that, which will never be correct.
> However, if the container first tried to insert before the
> hint, all insertions would be performed in amortised constant
> time.
This is a nit, but isn't nitpicking sort of the purpose of language
standards?
It seems that this case is not so much "guaranteed to be sub-optimal" as it
is permitted to be sub-optimal at the implementor's discretion. Take the
case of an implementation that checks both before and after the hint. Such
an implementation is conforming (according to the current standard) but also
provides amortized constant (optimal) performance for appending sorted
ranges. The problem with the current standard is not that it prohibits this
behavior but that it does not require it.
-----
Gillmer J. Derge
Pete Becker
>
> This is a nit, but isn't nitpicking sort of the purpose of language
> standards?
>
No, it's a side effect.
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
Contibuting Editor, C/C++ Users Journal (http://www.cuj.com)