complexity of list::size(), list::size(Itr, list&, Itr, Itr)

[Matt Austern]

You're certainly right that list::size() and slist::size() are
linear rather than constant time.  You're also right that this is
a change from the HP STL, in which list::size() was constant.

This was a deliberate change.  We did it because the only way to
get a constant-time size() for lists is to maintain an extra
member variable containing the list's size.  This requires taking
extra time to update that variable (extra time in splice, for example),
and it also makes the list larger.   Many list algorithms don't require
that extra word (algorithms that do require it might do better with
vectors than with lists), and, when it is necessary to maintain an
explicit size count, it's something that users can do themselves.

This changes is, in fact, conforming.  The standard says that size()
and swap() "should" be constant time, but that they are not required
to be.  That is, implementors are encouraged to make those member
functions constant time if practical, but an implementation in which
they are not constant time is still conforming.

(Incidentally, I'm puzzled by the comment that splice() in our
implementation is linear.  The member function splice() just turns
around and calls the internal member function transfer().  And
transfer() has no loops at all.  It's just a handfull of pointer
assignments.  One of the whole points of this change was so that
splice() would be constant time.)

			--Matt Austern







--- Forwarded mail from Yotam Medini <yotam@tmai.com>

Date: Wed, 11 Feb 1998 12:38:13 -0800
From: Yotam Medini <yotam@tmai.com>
To: genstl@graphics.Stanford.Edu, stl@sgi.com, egcs-bugs@cygnus.com
Subject: complexity of list::size(), list::size(Itr, list&, Itr, Itr)
CC: ccs.support@objectspace.com, brianb@tmai.com
Sender: owner-stl-maintainers@palladium.corp.sgi.com
Reply-To: Yotam Medini <yotam@tmai.com>


Hello STLees,

While stepping in debuggers (gdb, dbx) using the
attached below pogram I noticed that g++2.8.0 with the SGI's STL
implementation seem to have _linear_ time performing
    list<T>::size()
and
    list<T>::splice(list<T>::iterator before, list<T>& x,
		    list<T>::iterator b, list<T>::iterator e);
    even when x is 'this'.

Shouldn't these take a constant time?

By the way, ObjectSpace implementation seem to do both
in constant time.

-- yotam
Yotam Medini ----------------------------:)--h--o--m--e---------------------\
<< Avant! Corporation, Inc.              >> 1144 Craig Dr.          // Lost  |
<< 46871 Bayside Pkwy, Fremont, CA 94538 >> San Jose, CA 95129-2913 // my    |
<< yotam_medini@tmai.com                 >> yotam@blueneptune.com   // smart |
<< (510) 413-8141  [fax (510)4137743]    >> (408) 257-0840          // quote |
<<                      http://www.blueneptune.com/~yotam/                   |
------------------------------------------------------------------------
#include <iostream.h>
#include <algorithm>
#include <iterator>
#include <list>

int main(int, char**)
{
   list<int>  lp;
   lp.push_back(7);
   lp.push_back(13);
   lp.push_back(17);
   lp.push_back(101);
   cout << "lp.size=" << lp.size() << endl;

   list<int>::iterator   lpb = lp.begin(), lpe = lp.end();
   ostream_iterator<int>  oi(cout, " ");

   cout << "before splice ";  copy(lpb, lpe, oi); cout << endl;

   list<int>::iterator  i13 = find(lpb, lpe, 13);
   list<int>::iterator  i17 = find(lpb, lpe, 17);
   lp.splice(lpb, lp, i13, i17);
   cout << "after splice ";  copy(lp.begin(), lp.end(), oi); cout << endl;

   return 0;
}


--- End of forwarded mail from Yotam Medini <yotam@tmai.com>