Реализация std::list, сложность list::size()

size() const _GLIBCXX_NOEXCEPT
      { return std::distance(begin(), end()); }

typedef std::bidirectional_iterator_tag    iterator_category;

  template<typename _InputIterator>
    inline typename iterator_traits<_InputIterator>::difference_type
    __distance(_InputIterator __first, _InputIterator __last,
               input_iterator_tag)
    {
      // concept requirements
      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 
      typename iterator_traits<_InputIterator>::difference_type __n = 0;
      while (__first != __last)
    {
      ++__first;
      ++__n;
    }
      return __n;
    }

#if _GLIBCXX_USE_CXX11_ABI
size_t _M_get_size() const { return _M_impl._M_node._M_data; }
void _M_set_size(size_t __n) { _M_impl._M_node._M_data = __n; }
void _M_inc_size(size_t __n) { _M_impl._M_node._M_data += __n; }
void _M_dec_size(size_t __n) { _M_impl._M_node._M_data -= __n; }
size_t _M_distance(const __detail::_List_node_base* __first, const __detail::_List_node_base* __last) const
{ return _S_distance(__first, __last); }
// return the stored size
size_t _M_node_count() const { return _M_impl._M_node._M_data; }
#else
// dummy implementations used when the size is not stored
size_t _M_get_size() const { return 0; }
void _M_set_size(size_t) { }
void _M_inc_size(size_t) { }
void _M_dec_size(size_t) { }
size_t _M_distance(const void*, const void*) const { return 0; }
// count the number of nodes
size_t _M_node_count() const
{
    return _S_distance(_M_impl._M_node._M_next,
    std::__addressof(_M_impl._M_node));
}
#endif

 static size_t
    _S_distance(const __detail::_List_node_base* __first,
        const __detail::_List_node_base* __last)
    {
        size_t __n = 0;
        while (__first != __last)
          {
            __first = __first->_M_next;
            ++__n;
          }
        return __n;
    }

 /** Returns the number of elements in the %list. */
size_type
size() const _GLIBCXX_NOEXCEPT
{ return this->_M_node_count(); }

size_t _M_node_count() const { return _M_impl._M_node._M_data; }

#include <list>
#include <iostream>
 
#include <ctime>
#include <cstdio>
 
int main(void)
{
  std::list<int> l;
  const int N = 1000000;
  for (int i = 0; i < N; i++)
      l.push_back(1);
 
  double start = clock();
  for (int i = 0; i < 1000; i++)
      l.size();
  std::cout << (clock() - start) / CLOCKS_PER_SEC << std::endl;
 
  return 0;
}

    _LIBCPP_INLINE_VISIBILITY
    size_type size() const _NOEXCEPT     {return base::__sz();}
 
    typedef __list_imp<_Tp, _Alloc> base;
    _LIBCPP_INLINE_VISIBILITY
          size_type& __sz() _NOEXCEPT {return __size_alloc_.first();}
 
    __compressed_pair<size_type, __node_allocator> __size_alloc_;