Re: The design and evolution of STL containers, the case of std::map.size()
On 2008-03-05 16:52:51 -0500, Carl Barron <cbarron413@adelphia.net> said:
In article <47cef1d5$0$14992$4f793bc4@news.tdc.fi>, Juha Nieminen
<nospam@thanks.invalid> wrote:
I wish std::list had an element counter like std::map has.
Unfortunately in most implementations it doesn't, and std::list::size()
is an O(n) operation.
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."
In standardese, "should" means that something is recommended, but not
required. "shall" means required.
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.
That's one view. The other is that if the time complexity of size is
constant, then splice in some cases has to be linear. You can't do
both, and neither is required, so implementations differ.
--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]