[ Forwarded to C++ committee. -sdc ]

Paragraph 2 of 23.3.4.3 [lib.vector.modifiers] describes the complexity
of vector::insert:

   Complexity: If first and last are forward iterators, bidirectional
   iterators, or random access iterators, the complexity is linear in
   the number of elements in the range [first, last) plus the distance
   to the end of the vector. If they are input iterators, the complexity
   is proportional to the number of elements in the range [first, last)
   times the distance to the end of the vector.

First, this fails to address the non-iterator forms of insert.

Second, the complexity for input iterators misses an edge case --
it requires that an arbitrary number of elements can be added at
the end of a vector in constant time.

At the risk of strengthening the requirement, I suggest simply

   Complexity: The complexity is linear in the number of elements
   inserted plus the distance to the end of the vector.

For input iterators, one may achieve this complexity by first
inserting at the end of the vector, and then using rotate.

I looked to see if deque had a similar problem, and was surprised
to find that deque places no requirement on the complexity of inserting
multiple elements (23.2.1.3 [lib.deque.modifiers], paragraph 3):

   Complexity: In the worst case, inserting a single element into a
   deque takes time linear in the minimum of the distance from the
   insertion point to the beginning of the deque and the distance
   from the insertion point to the end of the deque. Inserting a
   single element either at the beginning or end of a deque always
   takes constant time and causes a single call to the copy constructor
   of T.

I suggest:

   Complexity: The complexity is linear in the number of elements
   inserted plus the shorter of the distances to the beginning and
   end of the deque.  Inserting a single element at either the
   beginning or the end of a deque causes a single call to the copy
   constructor of T.

                                                --Lisa Lippincott



[ 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              ]

"Lisa Lippincott" <lisa_lippincott@bigfix.com> wrote in message
news:060620001600279111%lisa_lippincott@bigfix.com...
>
>
> [ Forwarded to C++ committee. -sdc ]
>
> Paragraph 2 of 23.3.4.3 [lib.vector.modifiers] describes the complexity
> of vector::insert:
>
>    Complexity: ... If they are input iterators, the complexity
>    is proportional to the number of elements in the range [first, last)
>    times the distance to the end of the vector.
...
> Second, the complexity for input iterators misses an edge case --
> it requires that an arbitrary number of elements can be added at
> the end of a vector in constant time.

I'm not sure this is an issue.  Isn't

  O(M*N) equivalent to O((M+c1)*(N+c2)*c3 + c4)

where the various ci are constants?

> ...  (23.2.1.3 [lib.deque.modifiers], paragraph 3):
>
>    Complexity: In the worst case, inserting a single element into a
>    deque takes time linear in the minimum of the distance from the
>    insertion point to the beginning of the deque and the distance
>    from the insertion point to the end of the deque. Inserting a
>    single element either at the beginning or end of a deque always
>    takes constant time and causes a single call to the copy constructor
>    of T.

May I add that the wording "worst case" and "always" would seem to indicate
that these are not amortized requirements.  Real-world deque implementations
have a non-amortized worst-case O(N) cost for push_back/push_front (when the
underlying vector of pointers must be resized).  If you measure complexity
only in terms of number of calls to T's copy constructor the existing
description is correct.

It is possible to implement deque so that the worst-case complexity for
push_back (and insert at end) is constant, but I'd be mildly surprised to
learn that any existing implementations do so, or that the standard writers
intended the stricter meaning.



---
[ 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              ]