[Moderator's note: this defect report has been forwarded to
 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-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Mark Rodgers wrote:

> 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

---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

"Gillmer J. Derge" wrote:
>
> 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)

---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]