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

[Yotam Medini]

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;
}