There seems to be a confusion about what is counted as a part of
complexity requirement for container operations.

In N2923 "Specifying the complexity of size()(Revision 1)",  the
complexity of std::list::size() was discussed obviously assuming the
operation on list nodes (pointing to the contained objects) are counted
as a part of complexity.

But, 23.2.1 p2 (in N2914) says:
>
> > All of the complexity requirements in this Clause are stated solely in
> > terms of the number of operations on the contained objects.
> > [ Example: the copy constructor of type vector <vector<int> > has
> > linear complexity, even though the complexity of copying each
> > contained vector<int> is itself linear.    end example ]

Based on this wording, a bug report for GCC about complexity of
std::deque::push_back() was rejected.
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=13537
>>
>> >> It seems (and I am not familiar with deque's implementation at all) that >> a "map" of pointers is maintained in the deque, and insertions at the front or >> back can cause the map to be reallocated.  This takes O(N) time, even if the >> map's size is N / 4096 or whatever.
>
> >
> > You are talking about complexity in terms of the number of operations performed
> > on pointers to the contained objects.

I think the wording at 23.2.1 p2 should be more clear about these
operations (on the list nodes, or on pointers in deque) are counted as a
part of complexity or not.

The wording seems have been added since 1996.
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/1996/N0937R1.asc
(See Issue Number 20-036)
Many complexity requirements on std::list or other containers should
have been written in disregard of this addition.

If they are counted as a part of complexity, the requirement for
deque::push_back should be changed to amortized constant time (not real
constant time) to allow the implementation in GCC as conforming.

Sorry for coming without a proposed resolution. But I want to hear
first if I'm missing something or not.
--
k_satoda

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