C++轮子 · STL 序列容器

STL中大家最耳熟能详的可能就是容器，容器大致可以分为两类，序列型容器（SequenceContainer）和关联型容器（AssociativeContainer）这篇文章中将会重点介绍STL中的各种序列型容器和相关的容器适配器。主要内容包括

  • std::vector
  • std::array
  • std::deque
  • std::queue
  • std::stack
  • std::priority_queue
  • std::list
  • std::forward_list

std::vector

提到STL，大部分人的第一反应是容器，而提到容器大部分人首先想到的是std::vector。斯特劳斯特卢普的观点来说，std::vector是所有的容器中的首先，如果你不清楚应该使用哪个容器，那就选std::vector吧（当然，你不应该不清楚选哪个容器，合格是程序员对自己写的代码应该要了如指掌）。

std::vector的使用非常简单，下面是一个简单的例子。

#include <vector>                               // 1

int main(int argc, char* argv[]) {
    std::vector<int> ages = { 1, 2, 3, 4 };     // 2
    return 0;
}

头文件

// 1中引入了std::vector的头文件，需要注意的是所有C++标准库的头文件都是没有.h结尾的。这么做是为了区分，C标准库的头文件和C++标准库的头文件。比如最具代表性的：

#include <string.h>     // C 标准库头文件，包含 strlen，memset 等函数
#include <string>       // C++ 标准库头文件，包含 std::string 类

此外对于所有C标准库头文件，如果你是在C++项目中引用，你应该使用#include <cxxx>这种方式而不是#include <xxx.h>这种形式。也就是说我们应该使用#include <cstring>而不是#include <string.h>

std::vector 还是 vector

我见过很多的人（包括很多书）的习惯是在源文件头部写上using namespace std;然后在代码中使用vector<int>，而不是直接使用std::vector<int>。

我个人的习惯是直接使用std::vector<int>，因为namespace对我来说是一个模块，写明了std::有更强的模块内聚表达力，而且也不太容易出现名字碰撞。

初始化

// 2在构造std::vector的时候直接给了初始值，这是C++11的特性，在C++11之前不能这样写，有一种大致等同的写法如下：

int initilizer[4] = { 1, 2, 3, 4 };
std::vector<int> ages(initilizer, initilizer + 4);

std::vector<int> ages = { 1, 2, 3, 4 }这种写法实际上从语法分析上来说是分成下面几个步骤的：

  1. { 1, 2, 3, 4 } 被编译器构造成一个临时变量std::initializer_list<int>，然后使用临时变量构造一个临时变量 std::vector<int>，然后再用 std::vector<int>的拷贝构造函数构造最终的ages
std::initializer_list<int> initilizer;
std::vector<int> tmp(initilizer);
std::vector<int> ags(tmp);

当然上面的分析只是语法上的分析，绝大部分编译器都可以优化掉tmp，而且因为{1, 2, 3, 4}转换成std::initializer_list是编译器在编译器完成的事情，所以其实效率比我们想象中要高一些。

std::vector

std::vector有一个特化版本std::vector<bool>，用于实现dynamic bitset，需要注意的是，这个特化版本并不是容器，它的迭代器无法很好的适配STL中的所有算法。它的存在是为了节省空间，它的每一个元素只占用一位而不是一个字节。为了实现这种优化，operator[]返回的是一个代理类，你没有办法取单个元素的地址。通常的建议是，如果你不需要动态的bitset，你可以使用std::bitset，如果你需要dynamic bitset你可以考虑使用std::deque<bool>替代。

push_back vs emplace_back

C++11在容器尾部添加一个元素调用的函数是push_back，它在libcxx中的实现如下：

template <class _Tp, class _Allocator>
inline _LIBCPP_INLINE_VISIBILITY
void
vector<_Tp, _Allocator>::push_back(const_reference __x)
{
    if (this->__end_ != this->__end_cap())
    {
        __RAII_IncreaseAnnotator __annotator(*this);
        __alloc_traits::construct(this->__alloc(),
                                  _VSTD::__to_raw_pointer(this->__end_), __x);
        __annotator.__done();
        ++this->__end_;
    }
    else
        __push_back_slow_path(__x);
}

这里存在两次元素的构造，一次是 __x 参数的构造，一次是容器内部原始的拷贝构造。也就是说使用拷贝构造在末尾构造一个新的元素。emplace_back是C++11为减少其中一次拷贝而引入的新的接口，在libcxx中的实现如下

template <class _Tp, class _Allocator>
template <class... _Args>
inline
#if _LIBCPP_STD_VER > 14
typename vector<_Tp, _Allocator>::reference
#else
void
#endif
vector<_Tp, _Allocator>::emplace_back(_Args&&... __args)
{
    if (this->__end_ < this->__end_cap())
    {
        __RAII_IncreaseAnnotator __annotator(*this);
        __alloc_traits::construct(this->__alloc(),
                                  _VSTD::__to_raw_pointer(this->__end_),