1. empty()和size()

无论是序列化容器(vector、list、deque等)还是关联式容器(如map、multimap、set、multiset等)中，都提供了empty()和size()这两个成员函数，它们的作用分别是用来判断容器是否为空，以及获取容器大小。在开发中，我们通常需要对容器进行判空操作。empty()和size()都能够达到效果。如下演示代码：

//定义一个list模板对象L. 该模板中元素类型是int.
list<int> L{1,2,3,4,5};

//(1) 使用size()
if(L.size()){
 // 逻辑业务处理
}

//(2) 使用empty()
if(!L.empty()){
   // 逻辑业务处理
}

从效果上看，它们都能达到预期的结果；但是从效率上来看，这两者有着很大的差距。

2. empty()函数STL源码实现

empty()函数的时间复杂度基本上是O(1)(这里以list容器为例, 不同容器实现上有所差异)。因为list是一个双向链表，所以只需要判断next指针和当前节点_M_node的值即可得知是否为空。如果为空，next肯定等于_M_node，反之则不相同。

 // [23.2.2.2] capacity
      /**
       *  Returns true if the %list is empty.  (Thus begin() would equal
       *  end().)
       */
      _GLIBCXX_NODISCARD bool
      empty() const _GLIBCXX_NOEXCEPT
      { return this->_M_impl._M_node._M_next == &this->_M_impl._M_node; }

3. size()函数的STL源码实现

从STL的源码实现可以看到(这里以list模板进行讲解)，size()函数底层调用了_M_node_count()。函数_M_node_count()会返回当前容器中的节点数量。

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

而在_M_node_count()中，又间接调用了std::distance()算法来获取迭代器区间(begin()和end())的节点数。

 // count the number of nodes
    size_t
    _M_node_count() const
    { return std::distance(begin(), end()); }

distance()函数的实现原理如下。它通过遍历给定的迭代器__first和 __last，而计算出节点当前容器中的元素节点数量。遍历耗时与当前容器中的节点数量有关，即O(n)。

template<typename _InputIterator, typename _Distance>
    inline void
    __distance(_InputIterator __first, _InputIterator __last,
        _Distance& __n, std::input_iterator_tag)
    {
      // concept requirements
      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
      while (__first != __last)
 {
   //从__first开始遍历指针，知道__first == __last。
   ++__first;
   //每遍历一次，累增遍历n， 该变量表示节点数量。
   ++__n;
 }
    }

size()函数的底层实现调用流程如下图所示：

5. 示例演示

我们通过下面的示例代码来验证因empty()和size()底层的实现机制不同而带来的性能差异。在该代码中，用clock_gettime()来获取系统时间, 因为该函数的参数struct timespec可以精确到纳秒级别。我们分别在empty()和size()函数调用之前和之后获取系统时间(精确到纳秒)，然后两者之差进行比较，即可大致得出两个函数的效率差异。

#include 
#include 
#include 
#include 
using namespace std;

const int max_size = 100000000;
int main()
{
    struct timespec t1, t2;
    list<int> v;

    int i = 0;
    for(; i < max_size; i++)
        v.push_back(i);

    clock_gettime(CLOCK_REALTIME, &t1);
 
 // （1） 调用empty()
    cout << "v.empty():" << v.empty() << endl;
    // （2） 调用size()
    cout << "v.size():"  << v.size()  << endl;

    clock_gettime(CLOCK_REALTIME, &t2);
    long long diff = ((long long) t2.tv_sec * 1000000000 + (long long) t2.tv_nsec) - ((long long) t1.tv_sec * 1000000000 + (long long) t1.tv_nsec);

    cout << "diff: " << diff << endl;
    return 0;
}

4.1 empty()函数耗时

list容器对象v的数量一致，都是max_size。

clock_gettime(CLOCK_REALTIME, &t1);
 
// （1） 调用empty()
cout << "v.empty():" << v.empty() << endl;

clock_gettime(CLOCK_REALTIME, &t2);
long long diff = ((long long) t2.tv_sec * 1000000000 + (long long) t2.tv_nsec) - ((long long) t1.tv_sec * 1000000000 + (long long) t1.tv_nsec);

cout << "diff: " << diff << endl;

共耗时：87944ns，等于0.087944ms。如下图所示：

4.2 size()函数耗时

list容器对象v的数量一致，都是max_size。

clock_gettime(CLOCK_REALTIME, &t1);

// （2） 调用size()
cout << "v.size():"  << v.size()  << endl;

clock_gettime(CLOCK_REALTIME, &t2);
long long diff = ((long long) t2.tv_sec * 1000000000 + (long long) t2.tv_nsec) - ((long long) t1.tv_sec * 1000000000 + (long long) t1.tv_nsec);

cout << "diff: " << diff << endl;