STL：调用empty()而不是检查size()是否为0

如果要判断一个容器是否为空，如何判断呢？

一种方式是，调用size()函数，判断其是否等于0：

stl_container a;
if (a.size() == 0) 
{
  std::cout << " a is empty!" << std::endl;
 }

另一种方式是，调用empty()函数。各类STL容器都提供了empty()函数，如果为空，则empty()返回true；否则返回false。

两种方式都可以，而且本质上都是判断容器的size是否为0。在日常开发中，出于个人习惯，并不会特别在意非要调用哪一种。

而《Effective STL》给出的建议是，调用empty()。

为什么呢？

因为不同容器的empty()实现，一定是耗费常数时间，而size()则不一定。

为此，我查看了我工作环境上的几个容器的empty()实现，分别如下（说明，g++ 7.5.0, c++14）。

std::vector

bool empty()
{
  return begin() == end();
}

vector是检查首尾两个迭代器是否相等。vector底层是一块连续的内存，其迭代器本质上是指向这块内存首尾位置的两个指针。所以empty()函数是在检查这两个指针是否指向同一位置，若是，则说明容器为空，返回true。这当然是常数时间。

std::deque

bool empty()
{
  return M.finish == M.start;
}

和vector一样，也是检查首尾指针是否指向同一处，也是常数时间。deque底层是分段连续的内存组成的一块“表面”连续的buffer，这是和vector的区别，所以其迭代器的实现多有区别，不过迭代器的本质仍旧是指针。

std::array

bool empty()
{
  return size() == 0;
}

array的实现，则是直接调用size()函数，判断其内部维护的私有变量M_Nm是否为0。

std::string

bool empty()
{
  return size() == 0;
}

string的size()返回的是内部维护的私有变量M_string_length。

std::list

bool empty()
{
  return this->M_node->next == &this->M_node;
}

list的empty()是判断当前节点的next指针是否指向自己，同样是常数时间的操作。

std::set

bool empty()
{
  return this->node_count == 0;
}

set的底层是红黑树，维护了一个node_count的变量，通过判断node_count是否为0可以在常数时间内得到结果。

std::unordered_set

unordered_set的emtpy()实现也是判断size()==0。而size()返回的是内部维护的私有变量M_element_count。

我没有再查看其他容器的实现，上述列出的容器几乎代表所有stl容器类型。尽管上述各个容器的empty()的实现和其容器底层密切相关，但总体都是耗费常数时间。

那么size()的实现就不是常数时间了吗？

上面可以看到，array，set，unordered_set都是内部维护了一个私有成员变量size，其各个改变容器成员大小的成员函数都会更新这个size。这些容器的size()同样是常数时间的操作。

也可以想见，vector的size()实现，是将首尾两个迭代器相减，因为vector底层是一块内存连续的buffer。两个指针相减，这也是常数时间。同理，deque也是。

既然如此，为什么不推荐使用size() == 0呢？

答案是，list的一些实现，size耗费线性时间，即list独有的splice操作。不过这取决于各家的编译器的实现。

splice会将指定链表对象上指定范围内的元素切下来接到目标对象的指定位置后，会同时改变两个链表对象的size。

我查看了我的编译器版本上的splice的实现：

void splice(iterator __position, list& __x, iterator __first, iterator __last)
{
  if (__first != __last)
  {
      if (this != std::__addressof(__x))
        _M_check_equal_allocators(__x);

      size_t __n = _S_distance(__first, __last);
      this->_M_inc_size(__n);
      __x._M_dec_size(__n);

      this->_M_transfer(__position._M_const_cast(),
            __first._M_const_cast(),
            __last._M_const_cast());
  }
}

可以看到，list内部也维护了类似于size的成员，上面代码中调用_S_distance函数以获得被切链表部分的长度__n的目的，即是更新当前链表和被切链表的size信息。所以这个版本的list的size()也是常数时间。

我顺带查看了list的erase()、insert()等函数的实现，发现它们内部都在维护size的状态。这说明，这版编译器为了使得size(）为常数时间性能，牺牲了部分成员函数——如splice()——的性能。比如splice()函数内部的_S_distance()函数，由链表的本质可以知道，它一定会遍历，从而耗费线性时间。

那么如果splice的实现中，没有去更新两个链表的size信息呢？那么当用户调用size()的时候，这个size()函数返回什么呢？它一定是去遍历整个链表，耗费线性时间后，得到size信息，再返回给用户。

而《Effective C++》这一节所强调的，正是stl中各个容器设计时关于empty()函数与别的成员函数之间的性能取舍问题。当然，如上所述，性能优劣并不是绝对的，取决于各家编译器的实现。Anyway，可以保证的是，empty()函数，一定是常数时间的性能。

所以，如果在开发中遇到需要判断容器是否为空的时候，推荐大家使用empty()，而不是判断size() == 0。