【C++笔记】C++标准模板库（STL）之序列容器

1   STL概述

---

STL（Standard Template Library），即标准模板库，是一个具有工业强度的，高效的C++程序库。它被容纳于C++标准程序库（C++ Standard Library）中，是ANSI/ISO C++标准中最新的也是极具革命性的一部分。该库包含了诸多在计算机科学领域里所常用的基本数据结构和基本算法。为广大C++程序员们提供了一个可扩展的应用框架，高度体现了软件的可复用性。

(1)    STL的一个重要特点是数据结构和算法的分离。
尽管这是个简单的概念，但这种分离确实使得STL变得非常通用。例如，由于STL的sort()函数是完全通用的，你可以用它来操作几乎任何数据集合，包括链表，容器和数组；

(2)     STL另一个重要特性是它不是面向对象的。
为了具有足够通用性，STL主要依赖于模板而不是封装，继承和虚函数（多态性）——OOP的三个要素。你在STL中找不到任何明显的类继承关系。这好像是一种倒退，但这正好是使得STL的组件具有广泛通用性的底层特征。另外，由于STL是基于模板，内联函数的使用使得生成的代码短小高效；

从逻辑层次来看，在STL中体现了泛型化程序设计的思想，引入了诸多新的名词，比如像需求（requirements），概念（concept），模型（model），容器（container），算法（algorithmn），迭代子（iterator）等。与OOP（object-oriented programming）中的多态（polymorphism）一样，泛型也是一种软件的复用技术。

---

2   STL内容

STL的六大组件
(1) 容器（Container），是一种数据结构，如 list，vector，和deques ，以模板类的方法提供。为了访问容器中的数据，可以使用由容器类输出的迭代器；

(2) 迭代器（Iterator），提供了访问容器中对象的方法。例如，可以使用一对迭代器指定list或vector中的一定范围的对象。迭代器就如同一个指针。事实上，C++的指针也是一种迭代器。但是，迭代器也可以是那些定义了operator*()以及其他类似于指针的操作符方法的类对象；

(3)算法（Algorithm），是用来操作容器中的数据的模板函数。例如，STL用sort()来对一个vector中的数据进行排序，用find()来搜索一个list中的对象，函数本身与他们操作的数据的结构和类型无关，因此他们可以在从简单数组到高度复杂容器的任何数据结构上使用；

(4)仿函数（Functor），如果一个类将 () 运算符重载为成员函数，这个类就称为函数对象类，这个类的对象就是函数对象（又称仿函数）；

(5)适配器（Adaptor），可以使一个类的接口（模板的参数）适配成用户指定的形式，从而让原本不能在一起工作的两个类工作在一起。值得一提的是，容器、迭代器和函数都有适配器；

(6)分配器（allocator），为容器类模板提供自定义的内存申请和释放功能，由于往往只有高级用户才有改变内存分配策略的需求，因此内存分配器对于一般用户来说，并不常用。

---

3    序列式容器

3.1 vector  基本函数实现

（1）构造函数

• vector():创建一个空vector；

• vector(int nSize):创建一个vector,元素个数为nSize；

• vector(int nSize,const t& t):创建一个vector，元素个数为nSize,且值均为t；

• vector(const vector&):复制构造函数；

• vector(begin,end):复制[begin,end)区间内另一个数组的元素到vector中

（2）添加元素函数

• void push_back(const T& x):向量尾部增加一个元素X；

• iterator insert(iterator it,const T& x):向量中迭代器指向元素前增加一个元素x；

• iterator insert(iterator it,int n,const T& x):向量中迭代器指向元素前增加n个相同的元素x

  iterator insert(iterator it,const_iterator first,const_iterator last):向量中迭代器指向元素前插入另一个相同类型向量的[first,last)间的数据

（3）删除元素函数

• iterator erase(iterator it):删除向量中迭代器指向元素；

• iterator erase(iterator first,iterator last):删除向量中[first,last)中元素；

• void pop_back():删除向量中最后一个元素；

• void clear():清空向量中所有元素

（4）遍历元素函数

• at(int pos):返回pos位置元素的引用

• front():返回首元素的引用；

• back():返回尾元素的引用

• iterator begin():返回向量头指针，指向第一个元素

• iterator end():返回向量尾指针，指向向量最后一个元素的下一个位置

• reverse_iterator rbegin():反向迭代器，指向最后一个元素

• reverse_iterator rend():反向迭代器，指向第一个元素之前的位置

（5）判断函数

• bool empty() const:判断向量是否为空，若为空，则向量中无元素

（6）容器大小函数

• int size() const:返回向量中元素的个数；

• int capacity() const:返回当前向量中所能容纳的最大元素值；

• int max_size() const:返回最大可允许的vector元素数量值；

（7）其他函数

• oid swap(vector&):交换两个同类型向量的数据

• void assign(int n,const T& x):设置向量中第n个元素的值为x

• void assign(const_iterator first,const_iterator last):向量中[first,last)中元素设置成当前向量元素

需要补充说明以下begin和end

现在使用代码逐一操作一下：

1 #include
2 #include
3 using namespace std;
4
5 int main()
6 {
7     vector<int>v1;  // 创建一个空的vector;
8    vector<int>v2(5);  //创建元素个数为5的vector;
9    vector<int>v3(7, 3);  //创建元素个数为7，且值均为3的vector
10    vector<int>v4(v3);  // 复制构造函数
11    vector<int>v5(v3.begin(), v3.begin() + 3);  //复制v3区间内的元素到v5中
12
13    // 方式1
14    cout << "1. v1的元素个数：" << v1.size() << endl;
15    cout << "2. v2的输出结果：";
16    for (int i = 0; i < v2.size(); i++)
17    {
18        cout << v2[i] << "  ";
19    }
20    cout << endl;
21
22    // 方式2：现在换一种写法，输出一下
23    cout << "3. v3的输出结果：";
24    vector<int>::iterator iter;
25    for (iter = v3.begin(); iter != v3.end(); iter++)
26    {
27        cout << *iter << "  ";
28    }
29    cout << endl;
30
31    // 现在输出一下v4
32    cout << "4. v4的输出结果：";
33    for (int i = 0; i < v4.size(); i++)
34    {
35        cout << v4.at(i) << "  ";
36    }
37    cout << endl;
38
39    // 现在输出一下v5
40    cout << "5. v5的输出结果：";
41    for (int i = 0; i < v5.size(); i++)
42    {
43        cout << v5.at(i) << "  ";
44    }
45    cout << endl;
46 }

输出结果为：

1. v1的元素个数：0
2. v2的输出结果：0  0  0  0  0
3. v3的输出结果：3  3  3  3  3  3  3
4. v4的输出结果：3  3  3  3  3  3  3
5. v5的输出结果：3  3  3

下面我们将继续实验其他函数，但是这里仅放出主要代码，在实际操作中需要放入上方的代码内，即主函数内。

为缩减代码量，这里预先定义一个输出vector的函数，定义如下：

void out_vec(const vector<int>vec)
{
    for (int i = 0; i < vec.size(); i++)
        cout << vec[i] << "  ";
    cout << endl;
}

主要的测试代码如下所示：

1  int main()
2  {
3    ///注意此处省略了上边的vector的创建，测试时需要加上///
4
5    //第二部分：添加元素函数
6    v4.push_back(5);
7    v4.push_back(10);
8    cout << "1. push_back后的v4: ";
9    out_vec(v4);  // 输出看一下
10
11    vector<int>::iterator iter_posi = v4.begin() + 5;
12    v4.insert(iter_posi, 100);
13    cout << "2. v4.insert(iter_posi, 100)之后的结果：";
14    out_vec(v4);  // 输出看一下
15
16    vector<int>::iterator iter_posi2 = v4.begin() + 7;
17    v4.insert(iter_posi2, 3, 200);
18    cout << "3. v4.insert(iter_posi2, 3, 200)之后的结果：";
19    out_vec(v4);  // 输出看一下
20
21    // 现在新创建一个vector
22    vector<int>temp_vec;
23    temp_vec.push_back(20);
24    temp_vec.push_back(22);
25    temp_vec.push_back(24);
26    temp_vec.push_back(26);
27    //向temp_vec中插入部分v4元素
28    vector<int>::iterator iter_posi3 = temp_vec.begin() + 2;
29    temp_vec.insert(iter_posi3, v4.begin(), v4.begin() + 4);
30    cout << "4. temp_vec输出：";
31    out_vec(temp_vec);
32  }

输出结果为：

1. push_back后的v4: 3  3  3  3  3  3  3  5  10
2. v4.insert(iter_posi, 100)之后的结果：3  3  3  3  3  100  3  3  5  10
3. v4.insert(iter_posi2, 3, 200)之后的结果：3  3  3  3  3  100  3  200  200  200  3  5  10
4. temp_vec输出：20  22  3  3  3  3  24  26

现在测试其他函数：

1 int main()
2 {
3    //测试empty()函数
4    cout <<"1. v1的测试" << boolalpha << v1.empty() << endl;
5    //测试assign()和swap()函数
6    vector<int>temp_vec;
7    temp_vec.push_back(20);
8    temp_vec.push_back(22);
9    temp_vec.push_back(24);
10    temp_vec.push_back(26);
11    cout << "2. 当前的temp_vec: ";
12    out_vec(temp_vec);
13    cout << "3. 当前的v3: ";
14    out_vec(v3);
15    //测试swap()
16    swap(temp_vec, v3);
17    cout << "4. 交换后的temp_vec: ";
18    out_vec(temp_vec);
19    cout << "5. 交换后的v3: ";
20    out_vec(v3);
21
22    v1.assign(10, 5);
23    cout << "\n6. assign(10, 5)之后的v1：";
24    out_vec(v1);
25 }

输出结果为：

1. v1的测试 true
2. 当前的 temp_vec: 20  22  24  26
3. 当前的 v3: 3  3  3  3  3  3  3
4. 交换后的 temp_vec: 3  3  3  3  3  3  3
5. 交换后的 v3: 20  22  24  26
6. assign(10, 5)之后的v1：5  5  5  5  5  5  5  5  5  5

其他未测试函数使用方法类似，可自行测试。

4. deque

deque是double-ended queue的缩写，意为双端队列，它是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出，相比list增加[]运算符重载。

它和vector有一些相似的地方，主要包括两点：
（1）deque 容器也擅长在序列尾部添加或删除元素（时间复杂度为O(1)），而不擅长在序列中间添加或删除元素。
（2）deque也可以根据自身需求改变大小；

但是，它和vector不同的地方在于，deque还十分擅长在头部位置添加或删除元素，所耗费的时间复杂度也为常数阶O(1)。并且更重要的一点是，deque 容器中存储元素并不能保证所有元素都存储到连续的内存空间中，严格的讲，其没有capacity的概念，是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来，也就是说它不用像vector那样去预留一部分空间，即reserve功能。

尽管vector和deque都提供对元素的随机访问和序列中部执行线性时间的删除和插入操作，但是vector完成这些操作的时间更短一些。

deque基本具备vector的所有功能（所以下面表格的函数vector也可以使用）。
在使用deque的时候要引入头文件；

1  #include

deque的构造函数与vector一致，这里就不再赘述，它的一些常见函数如下所示。

1 //我们还是先定义一个deque的输出函数
2 #include
3 #include
4 using namespace std;
5
6 void out_deq(const dequedeq)
7 {
8    for (int i = 0; i < deq.size(); i++)
9        cout << deq[i] << " ";
10    cout << endl;
11 }
12
13//然后我们在测试相关函数
14 int main()
15 {
16    deque<int>deq1(4, 12);
17    cout << "1. deq1(4, 12)输出：";
18    out_deq(deq1);
19    cout << endl;
20    deq1.resize(6);
21    cout << "2. deq1.resize(6)输出：";
22    out_deq(deq1);
23
24    cout << "3. 测试front()：";
25    cout << deq1.front() << endl;
26    cout << "    deq1的size为：" << deq1.size() << endl;
27
28    cout << "4. 测试shrink _to_fit()：";
29    deq1.shrink_to_fit();  //特别说明这个函数并不改变deque的size；只是将内存占用缩减到size
30    out_deq(deq1);
31    cout << "    deq1的size为：" << deq1.size() << endl;
32
33    cout << "5. 测试emplace(): "; //在指定位置生成一个元素
34    //指定一个位置
35    deque<int>::iterator iterposi5 = deq1.begin() + 2;
36    deq1.emplace(iterposi5);
37    out_deq(deq1);
38 }

输出结果为：

1. deq1(4, 12)输出：12 12 12 12
2.  deq1.resize(6)输出：12 12 12 12 0 0
3. 测试front()：12
    deq1的size为：6
4. 测试shrink _to_fit()：12 12 12 12 0 0
    deq1的size为：6
5. 测试emplace(): 12 12 0 12 12 0 0

5. list

非连续存储结构，具有双链表结构，每个元素维护一对前向和后向指针，因此支持前向/后向遍历。支持高效的随机插入/删除操作，但随机访问效率低下，且由于需要额外维护指针 ，开销也比较大。每一个结点都包括一个信息快Info、一个前驱指针Pre、一个后驱指针Post。可以不分配必须的内存大小方便的进行添加和删除操作。使用的是非连续的内存空间进行存储。
在使用list的时候，要引入头文件

list的构造函数和vector也相同，此处不做赘述；相关的函数如下。

现在通过代码，对一些之前未曾测试过的函数进行测试。

1 #include
2 #include
3 using namespace std;
4
5 int main()
6 {
7    list<int>lst1 = { 1,2,7,3,4 };
8    list<int>::iterator iter_tmp;
9    cout << "1. lst1的元素：";
10    for (iter_tmp = lst1.begin(); iter_tmp != lst1.end(); iter_tmp++)
11        cout << *iter_tmp << "  ";
12    cout << endl;
13
14    //先测试splice()
15    list<int>lst2 = { 11, 21,23,45 };
16    cout << "2. lst2的元素：";
17    for (list<int>::iterator iter = lst2.begin(); iter != lst2.end(); iter++)
18        cout << *iter << " ";
19    cout << endl;
20    lst2.splice(lst2.begin(), lst1);  // 表示在lst2.begin()的位置合并lst1
21    cout << "3.  在lst2.begin()的位置合并lst1后？：";
22    for (list<int>::iterator iter = lst2.begin(); iter != lst2.end(); iter++)
23        cout << *iter << " ";
24    cout << endl;
25    //我们看一下lst1的情况
26    cout << "4. lst1的情况: ";
27    for (list<int>::iterator iter = lst1.begin(); iter != lst1.end(); iter++)
28        cout << *iter << " ";
29    cout << endl;
30
31    //再测试unique函数
32    lst2.push_back(45);
33    cout << "5. lst2当前的元素：";
34    for (iter_tmp = lst2.begin(); iter_tmp != lst2.end(); iter_tmp++)
35        cout << *iter_tmp << "  ";
36    cout << endl;
37    lst2.unique();
38    cout << "6. lst2使用unique之后的情况：";
39    for (iter_tmp = lst2.begin(); iter_tmp != lst2.end(); iter_tmp++)
40        cout << *iter_tmp << "  ";
41 }

输出结果为：

1.  lst1的元素：1  2  7  3  4
2.  lst2的元素：11 21 23 45
3.  在lst2.begin()的位置合并  lst1  后：1 2 7 3 4 11 21 23 45
4.  lst1的情况:
5.  lst2当前的元素：1  2  7  3  4  11  21  23  45  45
6.  lst2使用unique之后的情况：1  2  7  3  4  11  21  23  45

上述代码主要测试了splice和unique函数，可以发现，上面将lst1合并入lst2后，lst1为空了。