C++ STL全面解析：六大核心组件之一----序列式容器（vector和List）（STL进阶学习）

目录

序列式容器

Vector

vector概述

vector的迭代器

vector的数据结构

vector的构造和内存管理

vector的元素操作

List

List概述

List的设计结构

List的迭代器

List的数据结构

List的内存构造

List的元素操作

---

 C++标准模板库（STL）是一组高效的数据结构和算法的集合，广泛应用于C++程序设计中。STL由六大核心组件组成，分别是：

1. 容器（Containers）：各种数据结构，如vector，list，deque等等。
2. 迭代器（Iterators）：扮演容器域算法之间的胶合剂，是所谓的”泛型指针“
3. 算法（Algorithms）：各种常用算法，例如sort，search，copy，erase等等。
4. 函数对象（Function Objects）：又名为仿函数，行为类似函数，可作为算法的某种策略。
5. 适配器（Adapters）：一种用来修饰容器或者仿函数或迭代器接口的东西，例如：stack和queue。
6. 分配器（Allocators）：负责空间配置域管理，从实现角度来看他是一个管理空间的模板类。

        STL六大组件的交互关系，容器通过分配器获取数据存储空间，算法则通过迭代器去存取容器的内容，（这也是为什么说迭代器是类似于一种胶合剂的角色），仿函数则可以协助算法完成不同的策略变化，适配器可以修饰或者套接仿函数。

       在 C++ 中，STL（Standard Template Library，标准模板库）提供了一系列容器来帮助程序员组织和管理数据。常用的数据结构有：aray(数组)、list(链表)、tee(树)stack(堆栈)、queue(队列)、hashtable(散列表)、set(集合)、map(映射表)…等等。当提到STL时，许多人的第一印象便是容器，这也证明了容器的可靠性以及受欢迎程度。

        STL 容器大致可以分为两类：序列式容器（Sequence Containers）和关联式容器（Associative Containers）。如其各自的名字一般，序列式就是按照顺序排列的容器。而关联式容器就是通过键值和键值对进行查找的。

常见的序列式容器包括：

• vector（向量）：动态数组，支持随机访问，内部连续存储。
• list（链表）：双向链表，不支持随机访问，插入和删除操作非常快。
• deque（双端队列）：支持两端快速插入和删除的容器，支持随机访问。
• forward_list（单向链表）：C++11 引入的新容器，单向链表，不支持随机访问。

常见的关联式容器包括：

• set（集合）：存储唯一的键值，不允许重复，通常按照键的字典序排序。
• multiset（多重集合）：类似 set，但允许键值重复。
• map（映射）：存储键值对，键唯一，通常按照键的字典序排序。
• multimap（多重映射）：类似 map，但允许键值重复。

序列式容器

Vector

vector概述

        vector的数据结构跟array是非常相似的，只不过他们有一点不同，那就是array在定义时会被限制住大小，是静态的容量。而vector则是动态的容量，可以根据插入数据的数量去自动扩容容量。我们不必再去担心初始化数组的时候去定义一个大块头，使用vector时这个顾虑将烟消云散。

        vector的实现技术关键在于对其大小的控制以及重新分配时数据迁移的效率，一旦vector的空间满载，如果客户端每新增一个元素，vector随之去增加一个元素这种效率肯定是很慢的。所以vector是采用的未雨绸缪机制。

vector的迭代器

                vector维护的是一个连续线性空间，所以无论是什么类型的元素，普通指针都可以作为vector的迭代器而满足所有的必要条件。因为vector迭代器的操作指针都可以完成，无非就是加减乘除，加加，减减等操作。所以vector迭代器的定义正是普通指针。

vector的数据结构

        vector的数据结构也是非常简单：线性连续空间。它以两个迭代器start和finish分别指向所分配空间的目前已使用范围的头和尾，其中end_of_storage则是用来指向分配空间的尾。

        为了提高数据迁移时的效率，vector引入未雨绸缪的机制。这个机制就是vector实际配置的大小要比客户端需求的大小更大，以备将来的扩充，降低分配空间的次数。这个不难理解。

        通过start，finish，end_of_storage三个迭代器，便可轻易的提供首位标示，大小，容量，空容器判断等。

下方是vector的整体示意图：

vector的构造和内存管理

        我们围绕这个小测试程序说起。

// filename : vector-test.cpp
#include <vector>
#include <iostream>
#include <algorithm>using namespace std;int main() {int i;vector<int> iv(2, 9);cout << "size=" << iv.size() << endl;            // size=2cout << "capacity=" << iv.capacity() << endl;    // capacity=2iv.push_back(1);cout << "size=" << iv.size() << endl;            // size=3cout << "capacity=" << iv.capacity() << endl;    // capacity=4iv.push_back(2);cout << "size=" << iv.size() << endl;            // size=4cout << "capacity=" << iv.capacity() << endl;    // capacity=4iv.push_back(3);    cout << "size=" << iv.size() << endl;            // size=5cout << "capacity=" << iv.capacity() << endl;    // capacity=8iv.push_back(4);cout << "size=" << iv.size() << endl;            // size=6cout << "capacity=" << iv.capacity() << endl;    // capacity=8for (i = 0; i < iv.size(); ++i)cout << iv[i] << ' ';                        // 9 9 1 2 3 4cout << endl;iv.push_back(5);cout << "size=" << iv.size() << endl;            // size=7cout << "capacity=" << iv.capacity() << endl;    // capacity=8for (i = 0; i < iv.size(); ++i)cout << iv[i] << ' ';                        // 9 9 1 2 3 4 5cout << endl;iv.pop_back();iv.pop_back();cout << "size=" << iv.size() << endl;            // size=5cout << "capacity=" << iv.capacity() << endl;    // capacity=8cout << endl;iv.pop_back();cout << "size=" << iv.size() << endl;            // size=4cout << "capacity=" << iv.capacity() << endl;    // capacity=8vector<int>::iterator ite = find(iv.begin(), iv.end(), 1);if (ite != iv.end())iv.erase(ite);cout << "size=" << iv.size() << endl;            // size=3cout << "capacity=" << iv.capacity() << endl;    // capacity=8for (i = 0; i < iv.size(); ++i)cout << iv[i] << ' ';                        // 9 9 2cout << endl;ite = find(iv.begin(), iv.end(), 2);if (ite != iv.end())iv.insert(ite, 3, 7);cout << "size=" << iv.size() << endl;            // size=6cout << "capacity=" << iv.capacity() << endl;    // capacity=8for (int i = 0; i < iv.size(); ++i)cout << iv[i] << ' ';                        // 9 9 7 7 7 2cout << endl;iv.clear();cout << "size=" << iv.size() << endl;            // size=0cout << "capacity=" << iv.capacity() << endl;    // capacity=8return 0;
}

        从这段小的测试例子来看我们不难发现vector的分配空间的机制正如我们所了解的一样，它在扩容时会进行更大量级的扩容，又是双倍扩容。vector缺省使用alloc作为空间配置器，并据此定义了一个data_allocator，为的是方便以元素大小为配置单位。

        当我们使用push_back将新元素插入尾部时，该函数首先会去检测是否还有备用空间，如果有就不扩容，在备用空间上进行构造，并调整finish，如果没有就回去调用insert_aux扩容空间，重新配置，移动数据，释放空间。

template <class T, class Alloc>
void vector<T, Alloc>::insert_aux(iterator position, const T& x) {if (finish != end_of_storage) {  // 还有备用空间// 在备用空间起始处构造一个元素，并以vector最后一个元素值为其初值construct(&*finish, *finish-1);++finish;// 复制待插入的元素值T x_copy = x;// 将 [position, finish-1) 区间的元素向后移动一位copy_backward(position, finish-1, finish);*position = x_copy;} else {  // 已无备用空间const size_type old_size = size();  // 记录旧的大小const size_type len = (old_size != 0 ? 2 * old_size : 1);  // 新大小：如果原大小为0，则配置1；否则配置原大小的两倍// 分配新的内存空间iterator new_start = data_allocator::allocate(len);iterator new_finish = new_start;try {// 将原 vector 的内容拷贝到新 vectornew_finish = uninitialized_copy(start, position, new_start);// 为新元素设定初值 xconstruct(&*new_finish, x);++new_finish;// 将原 vector 的备用空间中的内容也忠实复制过来new_finish = uninitialized_copy(position, finish, new_finish);} catch (...) {// 如果出现异常，销毁新分配的内存并释放destroy(new_start, new_finish);data_allocator::deallocate(new_start, len);throw;}// 析构并释放原 vectordestroy(begin(), end());deallocate();// 调整迭代器，指向新 vectorstart = new_start;finish = new_finish;end_of_storage = new_start + len;}
}

        这里还需提一嘴，所谓的动态增加大小并非是像链表一般直接在后方增加新的扩容空间，因为vector的本质还是数组，所以它增加大小的方式和数组是相同的，大家不要误解。因此，一旦引起空间重新配置，那么原来vector的迭代器都将失效，切记。

vector的元素操作

        这里我不再多说，大家可以参考我之前学习vector操作时的一篇文章。

C++基础知识（八：STL标准库（Vectors和list））_c++ stl标准库-CSDN博客https://blog.csdn.net/LKHzzzzz/article/details/136316825

List

List概述

        相对于vector，list则显得更为复杂一下。但是list本身的优势也是vector没有的。例如插入一个元素就会配置一个元素空间，这就做到了对空间运用的绝对精准，同时这也是许多大型项目中经常用到的一种数据结构，例有Linux内核，其中对list的运用更是出神入化，不得不感叹大神的智慧。但是vector和list各有各的优势，还需要取决于在什么场景下用那个数据结构。

List的设计结构

        list的本身和list的节点是不同的结构，需要分开进行设计，以下是一个双向链表的节点机构。

List的迭代器

        List的迭代器不能再像vector一般用一个普通指针作为迭代器，因为list的节点不是连续存在的，所以list迭代器必须要有能力指向list的节点，并可以进行++，--，等操作。这里我们可以看出来list是一个双向列表，那么我们的迭代器也就必须具备前移和后退的能力。

        注：list的迭代器在析构这个list之前都是有效的！与vector并不相同！

以下是list的迭代器结构

template <typename T, typename Ref, typename Ptr>
struct list_iterator {typedef list_iterator<T, T&, T*> Self; // 自定义类型别名typedef bidirectional_iterator_tag iterator_category; // 迭代器类别typedef T value_type; // 值类型typedef Ptr pointer; // 指针类型typedef Ref reference; // 引用类型typedef std::list<T>::node* link_type; // 节点类型typedef std::size_t size_type; // 大小类型typedef std::ptrdiff_t difference_type; // 差值类型private:link_type node; // 迭代器内部的指针，指向 list 的节点public:// 构造函数list_iterator(link_type x) : node(x) {}list_iterator() : node(nullptr) {} // 默认构造函数list_iterator(const Self& x) : node(x.node) {} // 拷贝构造函数// 比较运算符bool operator==(const Self& x) const { return node == x.node; }bool operator!=(const Self& x) const { return node != x.node; }// 解引用运算符reference operator*() const { return (*node).data; }// 成员访问运算符pointer operator->() const { return &(*this->operator*()); }// 前缀递增运算符Self& operator++() {node = link_type((*node).next);return *this;}// 后缀递增运算符Self operator++(int) {Self tmp = *this;++(*this);return tmp;}// 前缀递减运算符Self& operator--() {node = link_type((*node).prev);return *this;}// 后缀递减运算符Self operator--(int) {Self tmp = *this;--(*this);return tmp;}
};

List的数据结构

        List不仅仅是一个双向链表，而且还是一个环状双向链表。所以它只需要一个指针便可以完整表现整个链表。

List的内存构造

让我们先从一段小的测试例子看起

#include <list>
#include <iostream>
#include <algorithm>using namespace std;int main() {int i;list<int> ilist;cout << "size=" << ilist.size() << endl; // size=0ilist.push_back(0);ilist.push_back(1);ilist.push_back(2);ilist.push_back(3);ilist.push_back(4);cout << "size=" << ilist.size() << endl; // size=5list<int>::iterator ite;for (ite = ilist.begin(); ite != ilist.end(); ++ite) {cout << *ite << " ";}cout << endl; // 输出 0 1 2 3 4cout << endl;ite = find(ilist.begin(), ilist.end(), 3);if (ite != ilist.end()) {ilist.insert(ite, 99);}cout << "size=" << ilist.size() << endl; // size=6cout << *ite << endl; // 输出 99for (ite = ilist.begin(); ite != ilist.end(); ++ite) {cout << *ite << " ";}cout << endl; // 输出 0 1 2 99 3 4cout << endl;ite = find(ilist.begin(), ilist.end(), 1);if (ite != ilist.end()) {cout << *(ilist.erase(ite)) << endl; // 输出 2}for (ite = ilist.begin(); ite != ilist.end(); ++ite) {cout << *ite << " ";}cout << endl; // 输出 0 2 99 3 4cout << endl;return 0;
}

        当我们以push_back（）插入元素的时候他的底层调用的其实是Insert函数，

void push_back(const T& x){insert(end()，x);

        insert（）是一个重载函数，有多种形式，但是在list中用的就是最简单一步操作，也就是单纯的去插入一个元素：首先构造一个元素空间，然后在尾部进行一系列的操作，把新元素插入进去。

list_node<T> *insert(list_node<T> *position, const T &x)
{list_node<T> *tmp = create_node(x); // 产生一个节点，内容为 x// 调整双向指针，使 tmp 插入进去tmp->next = position;tmp->prev = position->prev;// 更新前后节点的指针(static_cast<list_node<T> *>(position->prev))->next = tmp;position->prev = tmp;return tmp;
}

        插入之后的list状态也就如下图一般。由于list不像vector一般会在扩容时重新分配空间，然后转移过去，然后析构，因此list的迭代器是一直有效的。

List的元素操作

        这里大家可以去看一下我之前写的一篇基本操作文章关于List的，这里就不多说了。

C++基础知识（八：STL标准库（Vectors和list））_c++ stl标准库-CSDN博客https://blog.csdn.net/LKHzzzzz/article/details/136316825