list::size() O(N)->O(1)

  • Vyacheslav Lanovets

    Why don't cache list items count as MS STL implemenation do?
    I understand that it conforms to the standard but unfortunately we have to cache it on our own much more often than not.
    For node-based container it just does not make sense to save that several bytes of memory.

    • Petr Ovtchenkov

      Petr Ovtchenkov - 2006-12-19

      Either it violate standard, or explain what you mean.

    • Francois Dumont

      Francois Dumont - 2006-12-20

      STLport do not keep a the number of element in the list for memory reason but simply for Standard conformity. According Standard list::splice method have to be constant time operations. If we had to cache the number of elements in the list we would have to call std::distance(first, last) in the splice operations violating the constant time complexity of splice method. Containers size method do not have such a constraint.

      Just a little tip in case you do not know:

      list<int> l;

      if (!l.empty())


      if (l.size() != 0)

      AFAIR I never really need to know the list size, do you really need it? If you really need list size you should perhaps use an other container like a simple vector.

    • Vyacheslav Lanovets

      My one is ISO/IEC 14882:2003 :)

      Please do read (14) of the Standard.
      Also plese take a look at 23.1 (Table 65) about complexity of size() operation for containers.
      So Standard is a very bad argument here :)

      On the other hand I've read some discussions on the list::size vs list::splice complexity so I agree that caching size on my own is easier than writing my own version of list just because splice has a linear time.

      Also I would argue that users of std::list do not need size() at all and can substitute the container with vector :)

      Anyways we use wrapper classes around stl containers so this is not a big problem for us. I just cache the size.


Log in to post a comment.