Re: The design and evolution of STL containers, the case of std::map.size()

From:

Juha Nieminen <nospam@thanks.invalid>

Newsgroups:

comp.lang.c++.moderated

Date:

Thu, 6 Mar 2008 10:42:40 CST

Message-ID:

<47cffaf4$0$15002$4f793bc4@news.tdc.fi>

Carl Barron wrote:

The standard [container.requirements] table 87 [n2521.pdf] states
the complexity of size is (Note A). Below that table it states
"Those entries marked ?(Note A)? should have constant complexity."

I read this to be is for list. further evidence is that the complexity
of std::list<T,A>::splice(iterator,std::list<T,A>&,iterator,iterator)
has linear complexity. If size were linear complexity this operation
can easily be O(1) since only involves changing a fixed number of
internal pointers.

   The implementation of std::list::size() in gcc 4.1.2 is the following:

       size_type
       size() const
       { return std::distance(begin(), end()); }

   Since neither begin() nor end() are random access iterators, I believe
this to be an O(n) operation.

   The implementation of splice() cannot be deduced from the gcc headers
alone, but I would be quite surprised if it wasn't an O(1) operation.

--
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated. First time posters: Do this! ]