vector   O(1)

list        O(n)

deque

以下转自：http://www.07net01.com/2014/09/79439.html

使用C++进行开发，一部分人可能喜欢使用STL，即C++标准模板库。对容器使用可能最多，算法相对比较少。我在开发中基本上也就是使用容器：vector, list, deque, map, hashtable, hash_map。
         在实际情况不是特别要求自己需要实现特殊的数据结构的时候，一般采用STL容器，是又快又好又安全的做法。
         孙子兵法曰：“知己知彼，百战不殆”。
         我们一般人写程序，不可避免要使用别人开发的库来搭积木。其实也讲究这个“知己知彼”：
         知己—-对自己程序要实现的业务逻辑分析清楚，时间上、空间上的复杂度等；
         知彼—-对我们所使用的库也要有一定的了解，了解的越清楚越好；当然我们可能不会去完全了解各个库，这要看个人的修养方向了。
         回到STL容器来说，一般容器都有size()成员函数的实现，我们很明白它返回的是容器里元素的个数，一般可能都认为这个size()应该及其简单，时间复杂度应该是O(1)。实际情况是不是这样呢，我们简单分析下vector, list, deque（我下载的是SGI源代码）。
      先看vector：

以下是代码片段：     class vector {          public:                   size_type size() const                    { return size_type(end() – begin()); }                                      iterator begin() { return _M_start; }                   iterator end() { return _M_finish; }                             protected:               _Tp* _M_start;               _Tp* _M_finish;               _Tp* _M_end_of_storage;       };

      可见，vector的size（）实现在时间复杂度上确实是常量级的，很简单很快，就如我们想像中一样。注意它没有一个_size。

      再看list：

以下是代码片段：       class list{          public:             size_type size() const {                 size_type __result = 0;                 distance(begin(), end(), __result);                 return __result;               }       };

      注意了，尽然不是我们想象的。既不同于vector实现，也没有一个_size, 而是调用的一个全局函数：
      头文件stl_iterator_base.h：

以下是代码片段：       template <class _InputIterator, class _Distance>       inline void distance(_InputIterator __first, _InputIterator __last, _Distance& __n)       {            __STL_REQUIRES(_InputIterator, _InputIterator);            __distance(__first, __last, __n, iterator_category(__first));       }       template <class _InputIterator, class _Distance>       inline void __distance(_InputIterator __first, _InputIterator __last, _Distance& __n, input_iterator_tag)       {            while (__first != __last) { ++__first; ++__n; }       }

      大家看到了吧，它竟然使用迭代器遍历了整个链表，那么size()在时间复杂度上就不再是我们想象中的常量级，而是O(n)。为什么这样呢，这要对iterator和traits有所了解，才明白这么做的必要性。
      所以，如果你的list里数据很多，而你每次操作前还要调用size()来看看是否超过你的最大数目，那执行速度比你想象中要慢很多。所以处理这种情况，如果你必须每次要看看它的元素数目，把list 包装一下，自己维护一个_size算了，也浪费不了多少内存，4字节嘛。

     最后看看deque：       

以下是代码片段：        class deque {           public:                size_type size() const { return _M_finish – _M_start; }          protected:               iterator _M_start;               iterator _M_finish;       }；

      不错，看起来和vector一样，其实不然。
      别忘了c++语法有一个重要概念：运算符重载。

以下是代码片段：       struct _Deque_iterator {             typedef _Deque_iterator<_Tp, _Tp&, _Tp*>             iterator;             typedef ptrdiff_t difference_type;             typedef _Deque_iterator _Self;             difference_type operator-(const _Self& __x) const {                 return difference_type(_S_buffer_size()) * (_M_node – __x._M_node – 1) +                      (_M_cur – _M_first) + (__x._M_last – __x._M_cur);              }        }；

      为什么这么复杂了？这要怪deque采用map作为主控，使用分段连续线性空间的设计。怎么说都比list那个实现快。
       可以说STL的代码风格是让人难受的，当我们无聊而心情又好的时候，读读侯捷的《STL源码剖析》吧，分析对比一下，也有一些乐趣。