STL标准库与泛型编程（侯捷）笔记3

STL标准库与泛型编程（侯捷）

本文是学习笔记，仅供个人学习使用。如有侵权，请联系删除。

参考链接

Youbute: 侯捷-STL标准库与泛型编程

B站: 侯捷 - STL

Github:STL源码剖析中源码 https://github.com/SilverMaple/STLSourceCodeNote/tree/master

Github:课程ppt和源码 https://github.com/ZachL1/Bilibili-plus

介绍vector, array, deque, queue, stack的底层实现

16 vector深度探索

Vector将元素复制到内部的dynamic array中。元素之间总是存在一定的顺序，所以vector是一种有序集合（ordered collection）。 Vector支持随机访问，因此只要知道位置，你可以在常量时间内访问任何一个元素。 Vector提供随机访问迭代器，所以适用于任何STL算法。

如果你在末端附加或删除元素，vector的效率相当好。但如果你在前端或中段安插或删除元素，效率就不怎么样了，因为作用点之后的每一个元素都必须移到另一位置，而每一次移动都得调用assignment操作符。

Vector是动态数组，它会进行扩充，但不是原地扩充，而是当数组空间用完时，它会在某个地方重新分配内存空间（原来的两倍大小），再把先前的内容搬过去。

vector底部有三个指针，start, finish, end_of_storage

在C++中，std::vector 是一个动态数组，它的底层通常包含三个指针成员：start、finish 和 end_of_storage。

1. start: 这是指向数组的第一个元素的指针，表示 vector 的起始位置。

2. finish: 这是指向数组最后一个元素的下一个位置的指针，表示 vector 当前存储的元素范围结束位置。注意，finish 指向的位置是当前存储元素的末尾的下一个位置，而不是最后一个元素的位置。

3. end_of_storage: 这是指向 vector 内存空间的末尾的下一个位置的指针。当 vector 的元素数量接近其容量时，end_of_storage 可能指向当前分配内存的末尾。如果要添加更多的元素导致超过当前分配的内存空间，vector 可能需要重新分配更大的内存块，然后 end_of_storage 会被更新为新的内存块的末尾。

这些指针的作用是帮助 vector 进行动态内存管理。start 和 finish 之间的部分是当前 vector 存储的元素，而 finish 和 end_of_storage 之间的部分是 vector 预分配但尚未使用的内存空间。当 vector 的元素数量增加时，它可能需要重新分配内存，然后更新 end_of_storage 指针，以确保有足够的空间来容纳更多的元素。

现在看看两倍空间增长是怎么做的

下面是push_back的实现，当前分配的空间用完的时候，会调用insert_aux函数

insert_aux关于空间两倍增长的部分如下图所示

const size_type len = old_size != 0 ? 2 * old_size : 1;

下面的try catch里面就是具体的从旧位置把元素拷贝到新位置的源代码，分别是：把原vector的内容拷贝到新vector，然后为新元素赋值，新的finish指针后移，如果有insert函数，还需要把insert后面的元素复制过来。

后面还会把原来旧的vector空间释放掉

vector’s iterator

list的迭代器设计为一个class，这里vector的迭代器就是一个指针T *, 然后借助前面介绍的iterator_traits的偏特化（范围的偏特化，从接收T变成接收指针T *）,会把associated types里面的 value_type直接指定为T，而不是基于类的迭代器的I::value_type。下图是GNU C++2.9版本的内容

下面是对GNU C++4.9版本的vector的介绍：多了几个类，但是izeof(vector<T>)还是12B，因为vector继承自_Vector_base, 它里面有一个_Vector_impl的成员，它里面的data是三个指针，在32位电脑里面一个指针是4B，因此在32位电脑上vector的大小是12B。

GNU C++4.9版本的vector的iterator呢？

下图所示的设计很复杂，经过层层推导，可以看到_Iterator _M_current变量的类型也是_Tp*即上面GNU C++2.9版本的T*类型。

而且，GNU C++4.9版本的vector的iterator不再是G++2.9版本的指针T*，而是vector<T>::iterator，如下图箭头所指。

17 array、forward list深度探索

容器array

TR1：C++ TR1（Technical Report 1，技术报告 1）是一个介于 C++03 标准和 C++11 标准之间的阶段性技术报告，旨在为 C++ 标准库引入新功能和库组件提供一种机制。TR1 提供了一些 C++ 标准库的扩展，以及一些新的库组件，作为对 C++03 标准库的增强。

TR1 中的一些建议和组件后来被纳入 C++11 标准，成为了正式的 C++ 标准库的一部分。C++11 标准以及之后的版本中包括了 TR1 中的一些组件，例如 <memory>, <functional>, <random>, <tuple> 等。

这里介绍TR1版本的array实现

array的用法，需要指定array的大小

array<int, 10> myArray;
auto ite = myArray.begin();
ite += 3;
cout << *ite;

array的实现中没有构造函数和析构函数，GNU C++（g++） 2.9版本中直接拿原生指针当作迭代器， g++2.9版本的vector也是这种实现。

GNU C++ 4.9版本的array

容器forward_list

单向链表，下面的slide配合list学习。

std::forward_list 是 C++ 标准模板库（STL）中的一种单向链表容器。与 std::list 不同，std::forward_list 是一个单向链表，每个元素只保存指向下一个元素的指针，而不保存指向前一个元素的指针。

以下是一些 std::forward_list 的主要特点和操作：

特点：

1. 单向链表： std::forward_list 是一个单向链表，每个元素只有指向下一个元素的指针。
2. 没有 size() 函数： 由于是单向链表，std::forward_list 没有提供直接获取元素个数的 size() 函数。获取元素个数需要遍历整个链表。
3. 高效插入和删除： 在链表中间插入或删除元素的操作比在其他序列容器中更加高效。
4. 不支持随机访问： 由于是单向链表，std::forward_list 不支持通过索引直接访问元素。

18 deque、queue和 stack深度探索（上）

容器deque

std::deque（双端队列，deque 意为 double-ended queue）是 C++ 标准模板库（STL）中的一个容器，它提供了动态数组的功能，允许在两端进行高效的插入和删除操作。以下是关于 std::deque 的一些主要特点和概念：

1. 双端操作： std::deque 允许在队列的两端（前端和后端）进行高效的插入和删除操作，而不仅仅是在尾部。

2. 动态数组： std::deque 的内部结构通常是由多个固定大小的块组成的，每个块中存储一定数量的元素。这种结构允许在两端执行常数时间的插入和删除操作，而不需要像动态数组那样移动大量元素。

3. 迭代器： std::deque 提供随机访问迭代器，可以在常数时间内对其元素进行随机访问。这使得 std::deque 在许多算法和操作中能够高效地使用。

4. 不要求连续存储： 与 std::vector 不同，std::deque 不要求元素在内存中是连续存储的。这使得在 std::deque 头部和尾部执行插入和删除操作更加高效。

5. 大小可变： std::deque 的大小可以动态调整，因此它可以根据需要动态分配和释放内存。

总体而言，std::deque 是一个强大的容器，适用于需要在两端进行高效插入和删除操作的情况。它提供了动态数组的灵活性，同时避免了由于频繁在中间插入或删除元素而引起的性能问题。

deque的内部：

首先有一个map（暂且称为控制中心），里面存储指针，指针指向各个缓冲区buffer（或者叫做node），缓冲区是数组，具体存储数据。缓冲区是连续的，但是不同的缓冲区之间不是连续的，所以称为分段连续。如下图所示，下图中有5个 buffer。

对于下图中的迭代器中的cur,first,last,node四个元素，first和last分别是一个buffer的起始和结束，node是控制中心中哪个buffer的指针，cur指向的是具体的元素值。

所有的容器都维护了两个begin() 和 end(), 就是下图中的迭代器start和finish，它里面也有上述四个元素。

下面看一下class deque的内容，它里面的数据有：

iterator start; // 16B， 
iterator finish; // 16B
map_pointer map;  // 4B，上面所说的控制中心
size_type map_size;  // 4B， 控制中心这个vector的大小

上面的16 + 16 + 4 + 4 = 40B，这就是一个class deque创建出来的对象本身大小有40B（32位机器上），至于deque里面存储的数据占用的空间大小，是动态分配获得的，和对象本身大小无关。

再看下图的右上角，其中一个模板参数位 BufSiz, 这是GNU C++2.9版本，可以用来指定缓冲区的大小。

下图是iterator的成员（方框框起来的部分），可以看到map_pointer是 T**,它本身是一个指针，所以cur, first, last, node共计4 * 4B = 16B(在32位电脑上指针是4B大小)，这个就是上面iterator的大小。

下图中有

typedef  random_access_iterator_tag iterator_category;

指定迭代器的类型是随机存取的类型，这就是deque对外表现：提供随机访问迭代器，可以在常数时间内对其元素进行随机访问。其实通过上面的学习，我们知道deque底层不是连续的，它是分段连续的。

下面看deque的insert函数

insert可以在指定位置插入元素，这一页ppt展示的是插入的位置在deque的头或尾，直接调用push_front和push_back，对于中间的插入放到下一页ppt中的insert_aux函数讲。

下面是insert_aux函数的具体讲解

由于deque是连续的，并且是可以双向扩充的，当插入一个元素（对应安插点）时，就要看一下，哪端元素少，要决定元素的移动是向前还是向后，然后再插入新值，这样速度更快。

19 deque、queue和 stack深度探索（下）

先看一下deque的函数：

reference front()
{return *start;
}reference back()
{iterator tmp = finish; // 迭代器tmp赋值为finish，finish指向最后一个元素的下一个位置--tmp;// 迭代器--，往前移动一格return *tmp; // 此时返回的是最后一个元素
}size_type size() const
{return finish - start; // -操作符重载// 
}

这里是从源代码中的operator-的重载，摘录如下：

// _Deque_iterator里面的四个值
_Tp* _M_cur;
_Tp* _M_first;
_Tp* _M_last;
_Map_pointer _M_node;difference_type operator-(const _Self& __x) const {return difference_type(_S_buffer_size()) * (_M_node - __x._M_node - 1) +(_M_cur - _M_first) + (__x._M_last - __x._M_cur);
}
// 每个buffer容纳的元素个数，buffer_size
inline size_t __deque_buf_size(size_t __size) {return __size < 512 ? size_t(512 / __size) : size_t(1);
}static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp)); }

下面看deque如何模拟连续空间，主要是deque iterators的功劳

下面的_M_node - __x._M_node - 1中的_M_node指的是上图中的迭代器中的node节点，_M_node - __x._M_node - 1指的是控制中心两个node相减，得到是首尾buffer之间buffer的个数。(__x._M_last - __x._M_cur)指的是起始buffer的元素个数，就是下图中的97，98，99所在buffer的计算，这个buffer中右侧是元素，左侧是空白（目前还没有存数据）。(_M_cur - _M_first)指的是末尾buffer的元素个数，这个buffer左侧是数据，右侧是空白。

// 两个迭代器之间的距离：指的是多少个元素在两个迭代器之间
difference_type operator-(const _Self& __x) const {return difference_type(_S_buffer_size()) * (_M_node - __x._M_node - 1) +(_M_cur - _M_first) + (__x._M_last - __x._M_cur);
}

下面看++和–操作符重载：移动一个位置

_Self& operator++() {++_M_cur;if (_M_cur == _M_last) { // 到达一个buffer的边界// _M_node是控制中心的节点_M_set_node(_M_node + 1); // 跳转到下一个buffer_M_cur = _M_first;}return *this; 
}
_Self operator++(int)  {_Self __tmp = *this;++*this;return __tmp;
}_Self& operator--() {if (_M_cur == _M_first) {_M_set_node(_M_node - 1);_M_cur = _M_last;}--_M_cur;return *this;
}
_Self operator--(int) {_Self __tmp = *this;--*this;return __tmp;
}// 从一个buffer跳转到另一个buffer
void _M_set_node(_Map_pointer __new_node) {_M_node = __new_node;_M_first = *__new_node; // 指向新buffer的start_M_last = _M_first + difference_type(_S_buffer_size()); //指向新buffer的last
}

deque号称是连续空间，迭代器可以跳过多个位置，所以迭代器提供+=的重载

当跳过多个位置跨越了当前buffer的边界，就会到另一个buffer，

_Self& operator+=(difference_type __n)
{difference_type __offset = __n + (_M_cur - _M_first);// 目标位置在同一个缓冲区bufferif (__offset >= 0 && __offset < difference_type(_S_buffer_size()))_M_cur += __n;else { // 目标位置不在同一个缓冲区bufferdifference_type __node_offset =__offset > 0 ? __offset / difference_type(_S_buffer_size()): -difference_type((-__offset - 1) / _S_buffer_size()) - 1;// 切换到正确的buffer_M_set_node(_M_node + __node_offset);// 切换至正确的元素_M_cur = _M_first + (__offset - __node_offset * difference_type(_S_buffer_size()));}return *this;
}_Self operator+(difference_type __n) const
{_Self __tmp = *this;return __tmp += __n;
}

-=的重载调用上文的+=

  _Self& operator-=(difference_type __n) { return *this += -__n; }_Self operator-(difference_type __n) const {_Self __tmp = *this;return __tmp -= __n;}
// 连续空间需要提供下标操作符[]reference operator[](difference_type __n) const { return *(*this + __n); }

另外这里补充一下this 和 *this的区别：

bool operator==(const _Self& __x) const { return _M_cur == __x._M_cur; }  
bool operator!=(const _Self& __x) const { return !(*this == __x); }

问题：这里的this是什么类型，*this是什么类型？

回答：

在C++中，this 是一个指向当前对象的指针。在成员函数中，this 指针被隐式地传递给成员函数，指向调用该成员函数的对象。因此，this 的类型是指向当前类类型的指针。

在上述代码中，*this 表示当前对象的解引用。由于 this 是指针，*this 就是该指针所指向的对象。因此，*this 的类型是当前类的对象类型。

具体来说，上述代码是一个用于比较不等于的运算符重载函数。*this 是当前对象，__x 是另一个对象。通过 *this == __x 这一比较操作，判断当前对象是否等于另一个对象。!(*this == __x) 表示当前对象不等于另一个对象，因此返回 true。这个重载函数的目的是实现 != 运算符，如果你已经在类中实现了 == 运算符，这个函数就是通过对 == 的结果取反来实现 !=。

g++4.9版本的deque

deque的类图如下图所示，也是deque继承自一个deque base，deque base有一个deque impl实现，这个deque impl有一个迭代器deque iterator。

新版本不允许用户指定缓冲区的大小，使用默认值512.

deque里面有四个成员变量

_M_map // 指向控制中心(这是一个vector)map，控制中心控制一块一块的缓冲区
_M_map_size // 控制中心的大小
// 两个迭代器
_M_start // 指向deque所有元素的头
_M_finish // 指向deque所有元素的尾

这里补充控制中心这个vector扩充的规则：

当vector空间满的时候，会自动两倍扩充空间，并且把旧的元素拷贝进新的两倍空间中，这里实现的时候，拷贝到新vector的中间部分，从而实现vector中间部分不仅可以向后扩张（记录新的缓冲区），而且还可以向前扩张（记录新的缓冲区），如下图右侧，中间控制中心（灰色）。

容器queue

std::queue 是 C++ 标准模板库（STL）中的一个容器适配器，用于实现先进先出（FIFO）的队列数据结构。它是建立在其他 STL 容器之上的一个封装，通常使用 std::deque 作为默认底层容器。

以下是 std::queue 的一些主要特点和操作：

1. 先进先出（FIFO）： std::queue 实现了队列的基本特性，确保最先进入队列的元素最先被移出。

2. 容器适配器： std::queue 是一个容器适配器，意味着它不直接提供存储元素的能力，而是通过封装底层容器（默认是 std::deque）来实现队列的行为。

3. 底层容器： 默认情况下，std::queue 使用 std::deque 作为底层容器，但你也可以通过模板参数来指定其他底层容器，比如 std::list 或 std::vector。

4. 入队和出队操作： std::queue 提供了 push 方法用于将元素入队，pop 方法用于将队首元素出队。

   std::queue<int> myQueue;
   myQueue.push(1);
   myQueue.push(2);
   myQueue.pop();
   

5. 队首和队尾访问： front 方法返回队首元素的引用，back 方法返回队尾元素的引用。

   std::queue<int> myQueue;
   int frontElement = myQueue.front();  // 访问队首元素
   int backElement = myQueue.back();    // 访问队尾元素
   

6. 大小和空判断： size 方法返回队列中的元素数量，empty 方法检查队列是否为空。

   std::queue<int> myQueue;
   bool isEmpty = myQueue.empty();  // 检查队列是否为空
   

std::queue 提供了一种方便的方式来操作队列，尤其是在需要实现先进先出的场景下。它隐藏了底层容器的实现细节，使得队列的使用更加简单。

queue的源代码如下图，它调用deque中的各种方法实现自己的功能

容器stack

std::stack 是 C++ 标准模板库（STL）中的一个容器适配器，用于实现后进先出（LIFO）的栈数据结构。它是建立在其他 STL 容器之上的一个封装，通常使用 std::deque 作为默认底层容器。

以下是 std::stack 的一些主要特点和操作：

1. 后进先出（LIFO）： std::stack 实现了栈的基本特性，确保最后入栈的元素最先被弹出。

2. 容器适配器： std::stack 是一个容器适配器，意味着它不直接提供存储元素的能力，而是通过封装底层容器（默认是 std::deque）来实现栈的行为。

3. 底层容器： 默认情况下，std::stack 使用 std::deque 作为底层容器，但你也可以通过模板参数来指定其他底层容器，比如 std::list 或 std::vector。

4. 入栈和出栈操作： push 方法用于将元素入栈，pop 方法用于将栈顶元素出栈。

   std::stack<int> myStack;
   myStack.push(1);
   myStack.push(2);
   myStack.pop();
   

5. 栈顶访问： top 方法返回栈顶元素的引用。

   std::stack<int> myStack;
   int topElement = myStack.top();  // 访问栈顶元素
   

6. 大小和空判断： size 方法返回栈中的元素数量，empty 方法检查栈是否为空。

   std::stack<int> myStack;
   bool isEmpty = myStack.empty();  // 检查栈是否为空
   

std::stack 提供了一种方便的方式来操作栈，尤其是在需要实现后进先出的场景下。它隐藏了底层容器的实现细节，使得栈的使用更加简单。

下面是stack的源代码，它也是调用deque的各个函数实现自己的功能

queue和stack，关于其iterator和底层结构

stack和queue都不允许遍历，不提供iterator

stack和queue都可以选择list或者deque作为底层结构，如下图所示，便是使用list作为底层结构

stack<string, list<string>> c;
queue<string, list<string>> c1;

stack可以选择vector作为底层结构

queue不能选择vector作为底层结构

stack和queue都不能选择set或map做底层结构

后记

截至2024年1月7日，学习完list, vector, deque, queue, stack的底层实现，接下来要学习基于红黑树的容器。