序列式容器

序列式容器包括：静态数组array、动态数组vector、双端队列deque、单链表forward_list、双链表list。这五个容器中，我们需要讲解三个vector、deque、list的使用，包括：初始化、遍历、尾部插入与删除、头部插入与删除、任意位置进行插入与删除、元素的清空、获取元素的个数与容量的大小、元素的交换、获取头部与尾部元素等。

vector向量容器

底层数据结构是动态数组，每次扩容以原来容量的2倍进行扩容。（具体是不是2倍有待考究，各种资料说法不一，可以参考本章节扩展中的方法进行测试）

，我们可以把若干对象放在里面。vector的数据安排以及操作方式，与array非常相似，两者的唯一差别在于空间的运用的灵活性。Array是静态空间，一旦配置了就不能改变，要换大一点或者小一点的空间，可以，一切琐碎得由自己来，首先配置一块新的空间，然后将旧空间的数据搬往新空间，再释放原来的空间。vector是动态空间，随着元素的加入，它的内部机制会自动扩充空间以容纳新元素。因此vector的运用对于内存的合理利用与运用的灵活性有很大的帮助，我们再也不必害怕空间不足而一开始就要求一个大块头的array了。

vector的实现技术，关键在于其对大小的控制以及重新配置时的数据移动效率，一旦vector旧空间满了，如果客户每新增一个元素，vector内部只是扩充一个元素的空间，实为不智，因为所谓的扩充空间(不论多大)，一如刚所说，是”配置新空间-数据移动-释放旧空间”的大工程，时间成本很高，应该加入某种未雨绸缪的考虑，稍后我们便可以看到vector的空间配置策略。

vector所采用的数据结构非常简单，线性连续空间，它以两个迭代器_Myfirst和_Mylast分别指向配置得来的连续空间中目前已被使用的范围，并以迭代器_Myend指向整块连续内存空间的尾端。

为了降低空间配置时的速度成本，vector实际配置的大小可能比客户端需求大一些，以备将来可能的扩充，这边是容量的概念。换句话说，一个vector的容量永远大于或等于其大小，一旦容量等于大小，便是满载，下次再有新增元素，整个vector容器就得另觅居所。

注意

所谓动态增加大小，并不是在原空间之后续接新空间(因为无法保证原空间之后尚有可配置的空间)，而是一块更大的内存空间，然后将原数据拷贝新空间，并释放原空间。因此，对vector的任何操作，一旦引起空间的重新配置，指向原vector的所有迭代器就都失效了。这是程序员容易犯的一个错误，务必小心。

deque双端队列容器

deque——双端队列容器
底层数据结构是二维动态数组，其第一个维度一开始是固定值2，第二个维度容量的大小与存储的类型相关，是以4096除以被存储类型的大小得到的（例如deque中存储的是int类型的数据，第二维度的容量就是4096/4=1024）；扩容的时间第二维度的容量是不会变化的，第一个维度以2倍进行扩容；每次扩容后，原来第二维度的数组，从新的第一维度数组的oldsize/2下标处开始存放，这样存放上下都留有相同数量的空行，方便支持deque的双端操作（头部操作和尾部操作）。

vector容器是单向开口的连续内存空间，deque则是一种双向开口的连续线性空间。所谓的双向开口，意思是可以在头尾两端分别做元素的插入和删除操作，当然，vector容器也可以在头尾两端插入元素，但是在其头部操作效率奇差，无法被接受。

deque容器和vector容器最大的差异，一在于deque允许使用常数项时间对头端进行元素的插入和删除操作。二在于deque没有容量的概念，因为它是动态的以分段连续空间组合而成，随时可以增加一段新的空间并链接起来，换句话说，像vector那样，”旧空间不足而重新配置一块更大空间，然后复制元素，再释放旧空间”这样的事情在deque身上是不会发生的。也因此，deque没有必须要提供所谓的空间保留(reserve)功能.

虽然deque容器也提供了Random Access Iterator,但是它的迭代器并不是普通的指针，其复杂度和vector不是一个量级，这当然影响各个运算的层面。因此，除非有必要，我们应该尽可能的使用vector，而不是deque。对deque进行的排序操作，为了最高效率，可将deque先完整的复制到一个vector中，对vector容器进行排序，再复制回deque。

list链表容器

list——链表容器
底层数据结构是双向循环的链表。

链表是一种物理存储单元上非连续、非顺序的存储结构)，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

相较于vector的连续线性空间，list就显得负责许多，它的好处是每次插入或者删除一个元素，就是配置或者释放一个元素的空间。因此，list对于空间的运用有绝对的精准，一点也不浪费。而且，对于任何位置的元素插入或元素的移除，list永远是常数时间。

注意

list和vector是两个最常被使用的容器。

list容器是一个双向链表。

采用动态存储分配，不会造成内存浪费和溢出
链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素
链表灵活，但是空间和时间额外耗费较大

类模板声明

cpp

#include <vector>
template<class T, class Allocator = std::allocator<T>> class vector;

#include <deque>
template<class T, class Allocator = std::allocator<T>> class deque;

#include <list>
template<class T, class Allocator = std::allocator<T>> class list;

初始化容器对象

对于序列式容器而言，初始化的方式一般会有五种。

初始化为空容器

cpp

vector<int> v;
deque<int> d;
list<int> l;

初始化为多个相同的值

cpp

vector<int> v(10, 1);
deque<int> d(10, 1);
list<int> l(10, 1);

使用迭代器范围

代码演示以vector为例，其他容器类似。vector可以直接替换为deque与list。

cpp

int arr[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
vector<int> number(arr, arr + 10);//左闭右开区间

使用大括号

代码演示以vector为例，其他容器类似。vector可以直接替换为deque与list。

cpp

vector<int> v{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

拷贝构造或者移动构造

代码演示以vector为例，其他容器类似。vector可以直接替换为deque与list。

cpp

vector<int> v1 = {1, 2, 4, 6};
vector<int> v2(v1);
vector<int> v3(std::move(v1));

遍历容器对象

就是访问容器中的每个元素，一般可以采用下标或者迭代器的方式进行遍历。

下标方式

使用下标进行遍历(要求容器必须是支持下标访问的，list不支持下标，所以就不适用)

cpp

for(size_t idx = 0; idx != number.size(); ++idx) {
    cout << number[idx] << " ";
}
cout << endl;

迭代器方式

使用未初始化的迭代器进行遍历

cpp

vector<int>::iterator it;
for(it = numbers.begin(); it != numbers.end(); ++it) {
    cout << *it << " ";
}
cout << endl;

使用初始化的迭代器进行遍历

cpp

vector<int>::iterator it = numbers.begin();
for(; it!= numbers.end(); ++it) {
    cout << *it << " ";
}
cout << endl;

使用for和auto遍历

cpp

for(auto it = numbers.begin(); it!= numbers.end(); ++it) {
    cout << *it << " ";
}
cout << endl;

使用for和auto遍历，并且使用auto进行类型推导

cpp

for(auto it : numbers) {
    cout << it << " ";
}
cout << endl;

尾部插入与删除

尾部插入与删除，一般使用push_back与pop_back。尾部插入时是拷贝一份副本到尾部。这两个函数比较简单，vector、deque、list三个容器都适用。

cpp

void push_back(const T& value);
void push_back(T&& value);

void pop_back();

头部插入与删除

头部插入与删除，一般使用push_front与pop_front。头部插入时是拷贝一份副本到头部。对于deque与list而言，是支持这两个操作的，但是对于vector没有提供这两个操作。

cpp

void push_front(const T& value);
void push_front(T&& value);

void pop_front();

思考题：为何vector不支持在头部进行插入元素与删除元素呢？

可以从容器的底层结构上考虑。

任意位置进行插入元素

任意位置进行插入一般使用inser，vector、deque、list三个容器都适用。函数接口如下

cpp

// 1、在容器的某个位置前面插入一个元素
iterator insert( iterator pos, const T& value );
iterator insert( const_iterator pos, const T& value );
number.insert(it, 22);

// 2、在容器的某个位置前面插入count个相同元素
void insert(iterator pos, size_type count, const T& value)
iterator insert(const_iterator pos, size_type count, const T& value)
number.insert(it1, 4, 44);

// 3、在容器的某个位置前面插入迭代器范围的元素
template<class InputIt>
void insert(iterator pos, InputIt first, InputIt last); 
template<class InputIt>
iterator insert(const_iterator pos, InputIt first, InputIt last)
vector<int> vec{51, 52, 53, 54, 55, 56, 57, 58, 59};
number.insert(it, vec.begin(), vec.end());

// 4、在容器的某个位置前面插入大括号范围的元素
iterator insert(const_iterator pos, std::initializer_list<T> ilist)
number.insert(it, std::initialiser_list<int>{1, 2, 3});

三种序列式容器的插入示例如下

cpp

// 此处list可以换成vector或者deque
list<int> number = {1, 4, 6, 8, 9};
++it;
auto it = number.begin();

// 1、在容器的某个位置前面插入一个元素
number.insert(it, 22);

// 2、在容器的某个位置前面插入count个相同元素
number.insert(it, 3, 100);

// 3、在容器的某个位置前面插入迭代器范围的元素
vector<int> vec{51, 52, 53, 54, 55, 56, 57, 58, 59};
number.insert(it, vec.begin(), vec.end());

// 4、在容器的某个位置前面插入大括号范围的元素
number.insert(it, {1, 2, 3});

思考题：上述代码中，三种容器在insert之后，迭代器it解引用之后的结果有什么区别？

insert在任意位置进行插入，list使用起来很好，没有任何问题，但是deque与vector使用起来可能会出现问题，因为vector是物理上连续的，所以在中间插入元素会导致插入元素后面的所有元素向后移动，deque也有类似情况，可能因为插入而引起底层容量不够而扩容，从而使得迭代器失效(申请了新的空间，但是迭代器还指向老的空间)，即使没有扩容，插入之后的迭代器也失效了(不再指向之前的元素了)。

任意位置进行删除元素

任意位置进行删除一般使用erase，vector、deque、list三个容器都适用。函数接口如下

cpp

// 删除指定迭代器位置的元素
iterator erase(iterator position);

// 删除一个迭代器范围的元素
iterator erase(iterator first, iterator last);

对于vector而言，会导致删除迭代器之后的所有元素前移，从而导致删除元素之后的所有迭代器失效（迭代器的位置没有改变，但是因为元素的移动，导致迭代器指向的不是删除之前的元素，所以失效）；deque比vector复杂，要看pos前后的元素个数来决定，deque的erase函数可以看STL源码，需要看删除位置与size()的一半的大小，然后看是挪动前一半还是后一半，尽量减少挪动的次数；list会删除指向的元素，从而导致指向删除元素的迭代器失效。

这里以vector的erase为例，看看其删除元素的操作与删除后的效果。

cpp

//题意：删除vector中所有值为4的元素。
vector<int> vec = {1, 3, 5, 4, 4, 4, 4, 7, 8，4, 9};
for (vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {
    if(4 == *it) {
        vec.erase(it);
    }
}
// 发现删除后有些4没有删除掉，可以推测出是什么原因吗？是那些4没有删除呢？

// 正确解法：
for (auto it = vec.begin(); it != vec.end();) {
    if (4 == *it) {
        vec.erase(it);
    } else {
        ++it;
    }
}

思考题：将上述的vector换成是list，看看如何删除所有值为4的元素？

其他操作

cpp

// 清除容器中的所有元素(三个序列式容器都有)
void clear();

// 获取元素个数(三个序列式容器都有)
size_type size() const;

// 获取容量大小（只有vector有）
size_type capacity() const;

// 回收多余的空间，使得元素的个数与容量大小对应，不存在没有使用的空间（vector与deque有这个函数）
void shrink_to_fit();

// 交换两个相同容器中的元素(三个序列式容器都有)
void swap( vector& other);
vector<int> number1 = {1, 2, 3};
vector<int> number2 = {10, 20, 30};
number1.swap(number2);// 之后number1中的内容与number2中的内容做了交换

// 更改容器中元素个数(三个序列式容器都有)
// 以vector为例，执行resize时候，如果count < size(),就将多余的元素删除；如果count > size(),就在
// 之前的元素后面执行insert添加元素（没有指定就添加默认值）,元素的个数在改变的同时，容量也在发生改变 //（上一次的两倍或者本次元素个数）
void resize( size_type count, T value = T() );
void resize( size_type count);
void resize( size_type count, const value_type& value);

// 获取第一个元素(三个序列式容器都有)
reference front();
const_reference front() const;

// 获取最后一个元素(三个序列式容器都有)
reference back();
const_reference back() const;

// C++11增加的可变参数模板的几个函数
// 在容器的尾部就地构造一个元素
template< class... Args >
void emplace_back( Args&&... args);
vector<Point> vec;
vec.emplace_back(1, 2);// 就地将(1, 2)构建为一个对象存放在vector的尾部

list的特殊操作

排序函数sort

cpp

void sort();// 默认以升序进行排序，其实也就是，使用operator<进行排序

template< class Compare >
void sort(Compare comp);// 其实也就是传入一个具有比较的类型，即函数对象

template <typename T1, typename T2>
struct Compare {
    bool operator()(const T1 &a, const T2 &b) const {
        return a < b;
    }
};

移除重复元素unique

cpp

void unique();
size_type unique();

注意

使用unique的时候，要保证元素list是已经排好顺序的，否则使用unique是没有用的。

反转函数reverse

cpp

void reverse();
void reverse() noexcept;

将链表中的元素逆置。

合并函数merge

cpp

//合并两个链表（other既可以是左值也可以是右值）
void merge( list& other );
void merge( list&& other );

template <class Compare>
void merge( list& other, Compare comp );
template <class Compare>
void merge( list&& other, Compare comp );

合并的链表必须是有序的，如果没有顺序，合并没有效果。两个链表合并之后，并且另一个链表就为空了。

从一个链表转移元素到另一个链表splice

cpp

// 移动other链表到另一个链表的某个指定位置前面
void splice(const_iterator pos, list& other);
void splice(const_iterator pos, list&& other);

// 移动other链表中的某个元素到另一个链表的某个指定位置前面
void splice(const_iterator pos, list& other, const_iterator it);
void splice(const_iterator pos, list&& other, const_iterator it);

// 移动other链表的一对迭代器范围元素到另一个链表的某个指定位置前面
void splice(const_iterator pos, list& other, const_iterator first, const_iterator last);
void splice(const_iterator pos, list&& other,const_iterator first, const_iterator last);

整个list的特殊成员函数的使用

cpp

void test() {
    list<int> number{8, 3, 4, 3, 6, 7, 6, 9, 1, 8, 9};
    number.unique();
    number.sort();   // 默认情况是以小于符号进行排序
    number.unique(); // unique在去除重复元素的时候，链表必须为有序
    list<int> number2{11, 22, 33};
    number.merge(number2);
    number.reverse();
    list<int> number3{41, 42, 43, 44, 45, 46, 47};
    auto it = number.begin();
    ++it;
    ++it;
    auto it2 = numbers.begin();
    ++it2;
    ++it2;
    number.splice(it, numbers3, it2);
    auto it3 = number.end();
    it = number.begin();
    --it3;
    number.splice(it, numbers, it3);
}

思考题：调用splice函数时候，调用splice的对象能不能与参数中的other是同一个链表？

vector的原理

vector头部是固定的，不能进行插入与删除，只提供了在尾部进行插入与删除的操作，所以如果真的要在头部插入或者删除，那么其他的元素会发生移动，这样操作就比较复杂。

思考一个问题，vector的底层可以采用什么方式进行实现呢？

探讨vector的底层实现，三个指针：

``_M_start`：指向第一个元素的位置

_M_finish：指向最后一个元素的下一个位置

_M_end_of_storage：指向当前分配空间的最后一个位置的下一个位置

那么这三个指针是怎么来的呢，我们可以从其源码中获取答案（这里需要阅读vector的源码）

搞清楚vector的继承图、原理、源码以后，可以再思考一个问题

如何获取vector中的第一个元素的首地址呢，可以直接给对象取地址吗？

通过这个图就应该可以得到答案了。

cpp

&number;// error,只是获取对象栈上的地址,也就是_M_start的地址
&number[0];
&*number.begin();// ok
int *pdata = number.data();// ok
cout << "pdata = " << pdata << endl;// 使用printf，思考一下printf与cout打印地址的区别

deque的原理

思考一个问题，deque的底层采用什么方式进行实现呢？

探索deque的底层实现：

deque是由多个片段组成的，片段内部是连续的，但是片段之间不连续的，分散的，多个片段被一个称为中控器的结构控制，所以说deque是在物理上是不连续的，但是逻辑上是连续的。

我们依旧可以从其源码中获取答案（这里需要阅读deque的源码）

从继承图中可以看到，中控器其实是一个二级指针，由_M_map 表示，还有一个表示中控器数组大小的_M_map_size ，deque的迭代器也不是一个简单类型的指针，其迭代器是一个类类型，deque有两个迭代器指针，一个指向第一个小片段，一个指向最后一个小片段。其结构图如下：

list的原理

list是双向链表，其实现如下：

双向链表这个大家都比较熟悉，所以这里就不再赘述了。

vector的迭代器失效

以vector为例，如果使用insert插入元素，而每次插入元素的个数不确定，可能剩余空间不足以存放插入元素的个数，那么insert在插入的时候

cpp

void test() {
    vector<int> number = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    display(number);
    cout << "number.size() = " << numbers.size() << endl;         // 9
    cout << "number.capacity() = " << numbers.capacity() << endl; // 9
    cout << endl
         << "在容器尾部进行插入: " << endl;
    number.push_back(10);
    number.push_back(11);
    display(number);
    cout << "number.size() = " << number.size() << endl;         // 11
    cout << "number.capacity() = " << number.capacity() << endl; // 18
    cout << endl
         << "在容器vector中间进行插入: " << endl;
    auto it = number.begin();
    ++it;
    ++it;
    number.insert(it, 22);
    display(number);
    cout << "*it = " << *it << endl;
    cout << "number.size() = " << number.size() << endl;         // 12
    cout << "number.capacity() = " << number.capacity() << endl; // 18
    numbers.insert(it, 7, 100);                                  // 因为插入个数不确定，有可能底层已经发生了扩容
    display(numbers);
    cout << "*it = " << *it << endl;
    cout << "numbers.size() = " << numbers.size() << endl;         // 19
    cout << "numbers.capacity() = " << numbers.capacity() << endl; // 24
    // 正确办法是重置迭代器的位置
    vector<int> vec{51, 52, 53, 56, 57, 59};
    numbers.insert(it, vec.begin(), vec.end()); // 继续使用该迭代器就会出现问题（内存错误）
    display(numbers);
    cout << "*it = " << *it << endl;
    cout << "numbers.size() = " << numbers.size() << endl;
    cout << "numbers.capacity() = " << numbers.capacity() << endl;
    // 解决方案：每次在插入元素的时候，可以将迭代器的位置进行重置更新，避免因为底层扩容，迭代器还指向老
    // 的空间而出现问题
    vector<int> vec{51, 52, 53, 56, 57, 59};
    it = number.begin(); // 重新置位
    ++it;
    ++it;
    numbers.insert(it, vec.begin(), vec.end()); // 继续使用该迭代器就会出现问题（内存错误）
    display(numbers);
    cout << "*it = " << *it << endl;
    cout << "numbers.size() = " << numbers.size() << endl;
    cout << "numbers.capacity() = " << numbers.capacity() << endl;
}

思考题：insert插入数据导致容量不够，底层是不是也采用类似vector的push_back一样的两倍扩容呢？

因为vector的push_back操作每次只会插入一个，所以可以按照统一的形式2 * capacity()，但是insert的时候，插入的元素个数不定的，所以就不能一概而论。这里可以分别讨论一下，我们设置capacity() =n, size() = m, insert插入的元素个数为t个

如果t < n - m，这个时候就没有扩容，所以直接插入
如果n - m < t < m，就按照m的2倍去进行扩容，新的空间就是2 * m
如果n - m< t < n 且t > m，就按照 t + m去进行扩容
如果t > n时，依旧按照t + m去进行扩容

这就是vector进行insert扩容的原理（这个原理可以了解一下，主要是为了告诉大家，不是两倍扩容）。

参考资料

cppreference-容器库

扩展

测试vector的扩容

vector的insert和push_back操作都可能会导致扩容，其中push_back操作每次只增加一个元素，扩容的规则是固定的，我们只探讨它的扩容规则，至于insert的扩容规则在vector的迭代器失效部分有叙述。

在linux系统下使用g++编译后运行得到的结果是按2倍进行扩容的

示例代码

cpp

#include <iostream>
#include <vector>
using namespace std;

int main(int argc, char *argv[]) {
vector<int> v;
int size = -1;
int count = 0;
cout << "count=" << count << " size=" << size << endl;
for (int i = 0; i < 1000; ++i) {
  v.push_back(i);
  if (v.capacity() == size) {
      continue;
  } else {
      size = v.capacity();
      ++count;
      cout << count << ":" << size << endl;
  }
}
cout << "count=" << count << " size=" << size << endl;

return 0;
}

编译输出：

shell

$ g++ 001.cpp 
$ ./a.out 
count=0 size=-1
1:1
2:2
3:4
4:8
5:16
6:32
7:64
8:128
9:256
10:512
11:1024
count=11 size=1024
$ g++ -v
...
gcc version 11.4.0 (Ubuntu 11.4.0-1ubuntu1~22.04)

log4cpp

C++11智能指针

C++11线程库

C++11其他新特性

C++20协程

workflow

序列式容器

vector向量容器

deque双端队列容器

list链表容器

类模板声明

初始化容器对象

初始化为空容器

初始化为多个相同的值

使用迭代器范围

使用大括号

拷贝构造或者移动构造

遍历容器对象

下标方式

迭代器方式

使用for和auto遍历

尾部插入与删除

头部插入与删除

任意位置进行插入元素

任意位置进行删除元素

其他操作

list的特殊操作

排序函数sort

移除重复元素unique

反转函数reverse

合并函数merge

从一个链表转移元素到另一个链表splice

vector的原理

deque的原理

list的原理

vector的迭代器失效

参考资料

扩展

测试vector的扩容

序列式容器 ​

vector向量容器 ​

deque双端队列容器 ​

list链表容器 ​

类模板声明 ​

初始化容器对象 ​

初始化为空容器 ​

初始化为多个相同的值 ​

使用迭代器范围 ​

使用大括号 ​

拷贝构造或者移动构造 ​

遍历容器对象 ​

下标方式 ​

迭代器方式 ​

使用for和auto遍历 ​

尾部插入与删除 ​

头部插入与删除 ​

任意位置进行插入元素 ​

任意位置进行删除元素 ​

其他操作 ​

list的特殊操作 ​

排序函数sort ​

移除重复元素unique ​

反转函数reverse ​

合并函数merge ​

从一个链表转移元素到另一个链表splice ​

vector的原理 ​

deque的原理 ​

list的原理 ​

vector的迭代器失效 ​

参考资料 ​

扩展 ​

测试vector的扩容 ​

序列式容器

vector向量容器

deque双端队列容器

list链表容器

类模板声明

初始化容器对象

初始化为空容器

初始化为多个相同的值

使用迭代器范围

使用大括号

拷贝构造或者移动构造

遍历容器对象

下标方式

迭代器方式

使用for和auto遍历

尾部插入与删除

头部插入与删除

任意位置进行插入元素

任意位置进行删除元素

其他操作

list的特殊操作

排序函数sort

移除重复元素unique

反转函数reverse

合并函数merge

从一个链表转移元素到另一个链表splice

vector的原理

deque的原理

list的原理

vector的迭代器失效

参考资料

扩展

测试vector的扩容