std::list::size() complexity and 'standard's

C++ bit me again. I always thought that size() on STL sequences was a O(1) operation i.e. "return size_;". Well, never found a good reason why it should not be. And so, I usually dont bother to lock stl sequences to get the size unless it was really required, like in a producer-consumer situation. Until,

Program received signal SIGSEGV, Segmentation fault.
[Switching to Thread 0xb7ae56c0 (LWP 6382)]
0xb7e947dc in std::_List_const_iterator >::operator++ (this=0xbfffd4b0) at /usr/include/c++/4.3/bits/stl_list.h:221
221  _M_node = _M_node->_M_next;
(gdb) bt
#0  0xb7e947dc in std::_List_const_iterator >::operator++ (this=0xbfffd4b0) at /usr/include/c++/4.3/bits/stl_list.h:221
#1  0xb7e9480e in std::__distance > > (__first={_M_node = 0x0}, __last={_M_node = 0xbfffd7c4})
    at /usr/include/c++/4.3/bits/stl_iterator_base_funcs.h:84
#2  0xb7e94872 in std::distance > > (__first={_M_node = 0x8284828}, __last=
      {_M_node = 0xbfffd7c4}) at /usr/include/c++/4.3/bits/stl_iterator_base_funcs.h:119
#3  0xb7e948c6 in std::list, std::allocator > >::size (this=0xbfffd7c4)
    at /usr/include/c++/4.3/bits/stl_list.h:764
#4  0xb7e92e20 in hdb::odb::JobRunner::addJob (this=0xbfffd7bc, j={px = 0xbfffd6b0, pn = {pi_ = 0xbfffd654}}) at job-runner.cxx:152
#5  0xb7e9a390 in hdb::odb::Store::Save (this=0x8093cb0, oid=4703, dbuf=@0xbfffd7a0) at store.cxx:118
#6  0x0806a59a in main (argc=Cannot access memory at address 0x125f

A dig into the standard says "size() should have a constant complexity". After a vent-out-frustration session at the library guys, google pointed out that the word 'should' does not mean 'must' in 'standard' language.

Shyte.