STL序列容器（一）

发表于2021-12-15更新于2023-04-25字数统计4k阅读时长22分阅读次数

摘要

C++ STL是C++ 标准库中及其重要的一部分，对C++ STL的使用是每一位 C++ 程序员都应该熟悉的，在实际开发中，利用好这些前人造的轮子，能够提高开发效率且减少出错的概率。我个人认为C++ STL最重要的内容分为两块，其一是容器类，其二是算法类。本篇文章对STL容器类中的序列容器进行介绍，主要涉及内部实现、常用接口。当然所谓的内部实现是很早版本的STL容器的实现，随着标准库的不断更新，实现更加高效、安全，但是很多内部使用的数据结构和实现思想是没有改变的。了解这些内部实现的目的是更好的使用这些容器，知道何种容器的何种操作耗时等。
本篇文章对STL容器中的部分序列容器进行介绍，主要参考资料为侯捷老师的《STL源码剖析》，其它相关的参考链接在文末列出。

STL六大组件

C++ STL主要分为六大组件，分别是容器(container)，算法(algorithm)，迭代器(iterator)，仿函数(functors)，适配器(adapters)，配置器(allocators) 。
它们之间的相互关系如下：
六大组件

上图中六大组件：

  1. 容器(container) ：各种数据结构，如vector、list、deque、set、map等，是一种class template，用来存放数据。
  2. 算法(algorithm) ：各种常用算法如：sort、search、copy等，是一种function template。
  3. 迭代器(iterator) ：作为容器和算法之间的桥梁，是所谓的泛型指针。从实现的角度看，它是重载了oeprator*,operator->,operator++,operator--等运算符的class template。 每种容器都有相应的迭代器。
  4. 仿函数(functors) ：行为类似函数，从实现的角度来看是实现了operator()的class，函数指针也可以看作是狭义的仿函数functor。
  5. 适配器(adapters) ：一种用于修饰容器或仿函数或迭代器的东西，例如stack和queue，虽然看似容器，内部完全借助deque进行实现，只能看作是一种adapter。
  6. 配置器(allocators) ：负责空间的分配和管理，是实现了动态空间配置和管理的class template。

std::vector

概述

vector为可变大小数组，支持快速随机访问。在尾部之外的位置插入或删除元素可能很慢。实际开发中，选择容器通常来说使用vector是最好的选择，除非你有很好的理由选择其他容器。vector提供的迭代器类型为Random Access Iterators，这种迭代器支持随机访问元素，即支持自加、自减和加减常数等操作。
vector的声明如下：

1
template <class T, class Alloc = allocator<T> > class vector;

容器模板中两个参数分别是：

  • T：容器中元素类型，可以用vector::value_type访问。
  • Alloc：空间分配和释放时使用的分配器(allocator)，默认使用allocator<T>分配器进行空间分配，一般不需要指定。

就像数组一样，vector内部使用连续的内存空间存储元素，不同的是它的大小可以改变。 其基本内部实现为：首先预先分配一定大小(假设为n个element的大小)的连续空间，当容器不断添加元素使得容器元素个数大于n时，vector会进行空间的重新分配，例如重新找到一片大小为 2n 个 element 的连续空间，将原空间的所有元素拷贝至新空间，并继续添加新元素。这个重新分配并拷贝的过程是很慢的。
这个过程如下图(当然2倍空间增长只是其中一种实现方法，标准库不对实现方式进行规定）：
vector重新分配

常用接口

这里只列举部分常用的接口函数，完整接口参考 http://www.cplusplus.com/reference/

  • 构造函数(省略了拷贝和移动构造函数)
1
2
3
4
5
6
7
8
9
10
11
12
13
//default (1) 
explicit vector (const allocator_type& alloc = allocator_type());
//fill (2)    
explicit vector (size_type n);
         vector (size_type n, const value_type& val,
                 const allocator_type& alloc = allocator_type());
//range (3)   
template <class InputIterator>
  vector (InputIterator first, InputIterator last,
          const allocator_type& alloc = allocator_type());
//initializer list (6)    
vector (initializer_list<value_type> il,
       const allocator_type& alloc = allocator_type());

实例：

1
2
3
4
5
6
7
8
9
10
11
12
13
int main ()
{
  // constructors used in the same order as described above:
  std::vector<int> first;                                // empty vector of ints
  std::vector<int> second (4,100);                       // four ints with value 100
  std::vector<int> third (second.begin(),second.end());  // iterating through second

  // the iterator constructor can also be used to construct from arrays:
  int myints[] = {16,2,77,29};
  std::vector<int> fifth (myints, myints + sizeof(myints) / sizeof(int) );

  vector<int> sixth{1,2,3}; //initailizer list
}
  • 大小
1
2
3
size_type size() const noexcept;  //当前存储的元素个数
size_type max_size() const noexcept;  //最多可以存储的个数(不是capacity，由内存大小决定)
bool empty() const noexcept;  //未存储元素时返回true
  • 添加/删除元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void push_back (const value_type& val); //在vector末尾添加元素
void pop_back(); //删除末尾的元素

template <class... Args>
void emplace_back (Args&&... args);  //构造一个元素并在末尾插入，和push_back的区别是，push_back参数是一个已经存在的对象，而emplace_back参数是对象的构造参数。

void clear() noexcept;

//以下操作很慢
iterator insert (const_iterator position, const value_type& val);  //往迭代器position位置插入新元素
iterator insert (const_iterator position, size_type n, const value_type& val);  //插入n个相同元素val
template <class InputIterator>
iterator insert (const_iterator position, InputIterator first, InputIterator last);

template <class... Args>
iterator emplace (const_iterator position, Args&&... args);  //在position指定的位置进行构造并插入

iterator erase (const_iterator position);  //返回的迭代器指向删除元素后的第一个元素
iterator erase (const_iterator first, const_iterator last);
  • 获取元素或迭代器
1
2
3
4
5
6
7
8
9
10
11
//除以下之外，还有反向迭代器未列出
iterator begin() noexcept;
iterator end() noexcept;
const_iterator cbegin() const noexcept;
const_iterator cend() const noexcept;

reference operator[] (size_type n);
reference at (size_type n);  //和operator[]效果一样，但是会检查n是否越界，越界会抛出out_of_range异常
//分别获取最后一个元素和第一个元素，对空vector的行为是未定义的
reference back();
reference front();

std::list

概述

list是具有常数插入和删除元素操作的顺序容器，其内部实现为双向链表，有些实现还是环状双向链表。list的最大缺点是它不支持直接索引，为了访问链表中的第6个元素，必须从已知的位置(例如头迭代器或尾迭代器)逐个地访问过去，这消耗的时间的线性的。list提供的迭代器类型为Bidirectional Iterators,这种迭代器支持自加、自减操作，但是不能够加或减去常数，即只允许迭代器指针单个元素移动，而不能够一次性跨越多个元素。
list的声明和vector一致：

1
template < class T, class Alloc = allocator<T> > class list;

下图是双向循环链表结构：
list

常用接口

  • 构造函数(和vector基本一致)
1
2
3
4
5
6
7
8
9
10
11
12
13
explicit list (const allocator_type& alloc = allocator_type());
//fill (2)    
explicit list (size_type n);
         list (size_type n, const value_type& val,
                const allocator_type& alloc = allocator_type());
//range (3)   
template <class InputIterator>
  list (InputIterator first, InputIterator last,
         const allocator_type& alloc = allocator_type());

//initializer list (6)    
list (initializer_list<value_type> il,
       const allocator_type& alloc = allocator_type());
  • 大小
1
2
3
size_type size() const noexcept;
size_type max_size() const noexcept;
bool empty() const noexcept;
  • 添加/删除元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void push_back (const value_type& val);
void pop_back();

void push_front (const value_type& val);  //相比于vector，此函数为特有的，这也是双向链表带来的特点，两头插入
void pop_front();
void clear() noexcept;

template <class... Args>
void emplace_front (Args&&... args);
template <class... Args>
void emplace_back (Args&&... args);
template <class... Args>
iterator emplace (const_iterator position, Args&&... args);

iterator insert (const_iterator position, const value_type& val);
iterator insert (const_iterator position, size_type n, const value_type& val);
template <class InputIterator>
iterator insert (const_iterator position, InputIterator first, InputIterator last);
iterator insert (const_iterator position, initializer_list<value_type> il);

iterator erase (const_iterator position);
iterator erase (const_iterator first, const_iterator last);
  • 获取元素或迭代器(list不支持下标访问)
1
2
3
4
5
6
7
8
reference back();
reference front();

//除以下之外，还有反向迭代器未列出
iterator begin() noexcept;
iterator end() noexcept;
const_iterator cbegin() const noexcept;
const_iterator cend() const noexcept;
  • 其它操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void splice (const_iterator position, list& x);   //将list x中的元素转移至position指定的位置，这同时改变了两个list的大小，且不涉及任何元素的构造和析构，这就是元素的位置转移。
void splice (const_iterator position, list& x, const_iterator i); //只转移list x中迭代器i指向的一个元素
void splice (const_iterator position, list& x,
             const_iterator first, const_iterator last);  //转移list x中两个迭代器指定的范围的元素

void remove (const value_type& val);  //删除list中等于val的所有元素
template <class Predicate>
void remove_if (Predicate pred);  //删除满足functor参数要求的元素，参数是一个函数指针或仿函数

void unique();  //删除所有相邻且重复的元素(只剩一个)，这对排好序的容器十分有用
void merge (list& x);  //将x中的元素合并至list中并排好序，lst.merge(lst2)，注意调用之前需要两个list都是已经排序好的。且调用之后，x变为empty的，即元素被转移了

void sort();  //排序
template <class Compare>
void sort (Compare comp);  //按functor排序

void reverse() noexcept;  //倒序

std::deque

概述

vector是单向开口的连续线性空间，deque则是一种双向开口的序列容器，它也具有动态大小，且可以在两端进行扩充或缩减。vector实际上也可以在头部进行插入和删除，但是效率非常差(需要将其他元素都挪位置)，而deque能够在两端进行常数时间的插入和删除。deque也提供Random Access Iterator。但是deque的迭代器并不是普通的指针，它的复杂度比vector迭代器高多了。
其声明为：

1
template < class T, class Alloc = allocator<T> > class deque;

为了实现双向插入和删除，deque内部结构较为复杂，其内部并不像vector一样是完全的连续空间。首先deque内部存在一个“buffer指针图”命名为map，当然并不是STL中的map，其实质是一段连续的内存空间，这段空间中保存了若干个指针，这些指针分别又指向一段固定长度的连续内存空间(buffer) 。

其迭代器保存了4个指针，分别是cur, first, last, node。其中cur指向实际数据，first指向实际数据所处的那一个buffer的第一个元素，last指向buffer的最后一个元素末尾，node保存了该buffer在指针图map中的位置。
deque

从头部添加元素时，是在头迭代器的前一个位置添加；从尾部添加元素时，是在尾迭代器的位置添加。当添加元素的位置buffer满了时，会在map中配置一个新节点，并申请一个新的buffer来存放。

当map头部节点或尾部节点也不够了怎么办？显然当map的头部备用节点或尾部备用节点不够了时，会重新申请一块新的连续内存作为新的map，并将原来的map拷贝过来，就像vector一样。

常用接口

和list接口基本一致。

  • 构造函数
1
2
3
4
5
6
7
8
9
10
11
12
13
//default (1) 
explicit deque (const allocator_type& alloc = allocator_type());
//fill (2)    
explicit deque (size_type n);
         deque (size_type n, const value_type& val,
                const allocator_type& alloc = allocator_type());
//range (3)   
template <class InputIterator>
deque (InputIterator first, InputIterator last,
        const allocator_type& alloc = allocator_type());
//initializer list (6)    
deque (initializer_list<value_type> il,
       const allocator_type& alloc = allocator_type());
  • 大小
1
2
size_type size() const noexcept;
bool empty() const noexcept;
  • 添加/删除元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void push_back (const value_type& val);
void pop_back();

void push_front (const value_type& val);  
void pop_front();
void clear() noexcept;

template <class... Args>
void emplace_front (Args&&... args);
template <class... Args>
void emplace_back (Args&&... args);
template <class... Args>
iterator emplace (const_iterator position, Args&&... args);

iterator erase (const_iterator position);
iterator erase (const_iterator first, const_iterator last);
  • 获取元素或迭代器
1
2
3
4
5
6
7
8
9
10
reference back();
reference front();
reference operator[] (size_type n);  //deque支持索引
reference at (size_type n);  //和operator[]效果一样，但是会检查n是否越界，越界会抛出out_of_range异常

//除以下之外，还有反向迭代器未列出
iterator begin() noexcept;
iterator end() noexcept;
const_iterator cbegin() const noexcept;
const_iterator cend() const noexcept;

std::stack

概述

stack是一种 先进后出(FILO) 的数据结构，它允许新增元素、移除元素、取得最顶端的元素，但是除了最顶端外，没有任何地方可以存取stack的其它元素，即stack不允许遍历行为。准确的来说，STL中的stack是一种容器适配器(container adaptors)，它只是其他容器的包装，这个其他容器必须提供以下操作：

  • empty
  • size
  • back
  • push_back
  • pop_back

因此stack的声明如下：

1
template <class T, class Container = deque<T> > class stack;

其中模板的第二个参数为容器类型，实际上，标准容器中的vector,deque和list都满足上述条件，可以作为该参数的选项。但是默认的选项是deque。需要说明的是：stack不提供迭代器。
stack和queue的底层实现都非常简单，实际上就是把模板中容器的上述方法进行了包装，基本上就是原封不动的调用。

常用接口

  • 构造函数(一般不改变默认容器，直接构造一个空的stack；这里没有列出拷贝和移动构造函数)
1
explicit stack (const container_type& ctnr);  //从一个已有的容器进行构造

实例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// constructing stacks
#include <iostream>       // std::cout
#include <stack>          // std::stack
#include <vector>         // std::vector
#include <deque>          // std::deque

int main ()
{
  std::deque<int> mydeque (3,100);          // deque with 3 elements
  std::vector<int> myvector (2,200);        // vector with 2 elements

  std::stack<int> first;                    // empty stack
  std::stack<int> second (mydeque);         // stack initialized to copy of deque

  std::stack<int,std::vector<int> > third;  // empty stack using vector
  std::stack<int,std::vector<int> > fourth (myvector);  

  return 0;
}
  • 其它接口
1
2
3
4
5
6
void push (const value_type& val);  //在栈顶添加一个元素
template <class... Args> void emplace (Args&&... args);  //同push，但是通过传入的参数原地构造一个对象放入栈顶
void pop();
bool empty() const;
size_type size() const;
reference top();  //获取栈顶的元素

std::queue

概述

queue是一种先进先出(FIFO)的数据结构，数据只能从一个开口进，从另一个开口出。和stack一样，queue也是一种容器适配器(container adaptors) ，它只是其它容器的包装，这个其它容器必须要可以从back推入元素并从front取出元素，即具备下列操作：

  • empty
  • size
  • front
  • back
  • push_back
  • pop_front

queue的声明如下(和stack一样)：

1
template <class T, class Container = deque<T> > class queue;

第二个参数为容器类型，标准容器中的deque和list都符合要求。默认使用deque作为底层容器。同样queue不提供迭代器。

常用接口

  • 构造函数
1
explicit queue (const container_type& ctnr);

实例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// constructing queues
#include <iostream>       // std::cout
#include <deque>          // std::deque
#include <list>           // std::list
#include <queue>          // std::queue

int main ()
{
  std::deque<int> mydeck (3,100);        // deque with 3 elements
  std::list<int> mylist (2,200);         // list with 2 elements

  std::queue<int> first;                 // empty queue
  std::queue<int> second (mydeck);       // queue initialized to copy of deque

  std::queue<int,std::list<int> > third; // empty queue with list as underlying container
  std::queue<int,std::list<int> > fourth (mylist);
  return 0;
}
  • 其他接口
1
2
3
4
5
6
7
8
9
void push (const value_type& val);  //从back方向放入一个值，底层调用了容器的push_back方法
template <class... Args> void emplace (Args&&... args);
void pop();  //将最先入队的元素出队，这个元素可以被front方法访问

bool empty() const;
size_type size() const;

reference& back();  //返回最新入队的元素的引用，底层调用容器的back
reference& front();  //返回最先入队的元素的引用，底层调用容器的front

总结

本篇介绍了STL容器中的std::vercor, std::list, std::deque以及两种容器适配器：std::stack, std::queue。对这些容器的内部数据结构以及常用的接口进行了简要介绍，限于篇幅，STL序列容器中的forward_list, priority_queue放置下一篇文章进行介绍。

参考资料

  1. 《STL源码剖析》侯捷
  2. http://www.cplusplus.com/reference/
  3. 《C++ Primer 5th》