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_),