Bug in STL list<> template?

[Gregory Bond <gnb at itga dot com dot au>]

G'day.

I'm not sure who to send this to as it appears to be a problem with the SGI 
STL code as shipped with egcs 1.1b & earlier.

According to my reading of the C++ spec (CD2 section 23.1
[lib.container.requirements], table 3) we see the following requirements for
the size() routine of any container a:

  |a.size()     size_type           a.end()-a.begin()               (Note A)   |

where the notes say
	Those entries marked ``(Note  A)'' should have constant complexity.

In the SGI list<> template, the size() member does
 size_type size() const {
    size_type result = 0;
    distance(begin(), end(), result);
    return result;
  }
which is clearly linear complexity.

I discovered this when trying to speed up some code using the STL list<> and
this turned one of my algorithms from linear to quadratic time!

Greg.