C++ std::list.size() has linear complexity

size_type size() const {
    size_type __result = 0;
    distance(begin(), end(), __result);

    return __result;
  }

在sgi stl的实现版本中看到关于size member的实现。

这里的distance是一个全局函数。

对于random_access iterator 而言是两个迭代器相减，具有O（1）的复杂度，而对于其他类型的迭代器则是++first到last的形式，具有O（n）的复杂度。

Why islist<>::size()linear time?
Thesize()member function, forlistandslist, takes time proportional to the number of elements in the list. This was a deliberate tradeoff. The only way to get a constant-timesize()for linked lists would be to maintain an extra member variable containing the list's size. This would require taking extra time to update that variable (it would makesplice()a linear time operation, for example), and it would also make 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 choice is permitted by the C++ standard. The standard says thatsize()"should" be constant time, and "should" does not mean the same thing as "shall". This is the officially recommended ISO wording for saying that an implementation is supposed to do something unless there is a good reason not to.

One implication of linear timesize(): you should never write

if (L.size() == 0) ...

Instead, you should write

if (L.empty()) ...

在VC下面是保存了一个size_t的静态变量来保存list中的size，但是这样做就需要在插入删除的操作中进行这个变量的维护，在例如splice的操作中复杂度将达到O（n）。这样对于list中插入和删除都是const complexity的特性就不符合了。