11.STL

STL阶段

禁止复制

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

文本查询扩展作业解析

get_file函数的作用就是进行预处理操作，将文件中的每一行的内容放在shared_ptr<vector<string>> file里面进行存储；然后对每一个单词进行处理，将单词与行号放在map<string, shared_ptr<set<size_t>>> wm

查询某个单词sought的时候，会构建Query对象，在Query的构造函数中，会构建一个WordQuery对象，并且使用基类的指针shared_ptr<Query_base> q指向new出来的WordQuery对象。然后再调用Query的eval方法与rep方法的时候，都会走多态。在走WordQuery的eval方法的时候会走TextQuery的query方法，在TextQuery的query函数中将待查询的单词、行号、每一行的内容放在QueryResult中，交给QueryResul的数据成员，最后调用print函数将结果打出来。

查询两个单词同时出现的情况

Query andq = Query(sought1) & Query(sought2);
查询sought1的时候会构建Query对象，在Query的构造函数中，会构建一个WordQuery对象，并且使用基类的指针shared_ptr<Query_base> q指向new出来的WordQuery对象。
查询sought2的时候会构建Query对象，在Query的构造函数中，会构建一个WordQuery对象，并且使用基类的指针shared_ptr<Query_base> q指向new出来的WordQuery对象。
andq也是一个Query对象，在Query的构造函数中，会构建一个AndQuery对象，并且使用基类的指针shared_ptr<Query_base> q指向new出来的AndQuery对象//const Query &lhs = Query(sought1);
//const Query &rhs = Query(sought2);
inline Query operator&(const Query &lhs, const Query &rhs)
{std::shared_ptr<Query_base>  tmp(new AndQuery(lhs, rhs));return tmp;//return std::shared_ptr<Query_base>(new AndQuery(lhs, rhs));//隐式转换//shared_ptr<Query_base>  t(new AndQuery(lhs, rhs));//return t;  Query(t)
}
Query(std::shared_ptr<Query_base> t)
Point pt = 10;//10--->Point(10, 0)Query(std::shared_ptr<Query_base> query)
: q(query)
{}QueryResult
AndQuery::eval(const TextQuery& text) const
{ QueryResult left = lhs.eval(text), right = rhs.eval(text);shared_ptr<set<line_no> > ret_lines(new set<line_no>);  //取交集set_intersection(left.begin(), left.end(), right.begin(), right.end(),inserter(*ret_lines, ret_lines->begin()));return QueryResult(rep(), ret_lines, left.get_file());
}

~hello

1 2 3 4 ...10
1 3 5 10
2 4 6 7 8 90 1 2 3 4 5 6 7 8 9
0 2 4 9
1 3 5 6 7 8
QueryResult
NotQuery::eval(const TextQuery& text) const
{QueryResult result = query.eval(text);shared_ptr<set<line_no> > ret_lines(new set<line_no>);QueryResult::line_it beg = result.begin(), end = result.end();vector<string>::size_type sz = result.get_file()->size();for (size_t n = 0; n != sz; ++n) {if (beg == end || *beg != n) ret_lines->insert(n); else if (beg != end) ++beg; }return QueryResult(rep(), ret_lines, result.get_file());
}n
0 1 2 3 4 5 6 7 8 9end
0 2 4 9begret:1 3 5  6 7 8

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

标准模板库概述

STL的六大组件

1、容器：用来存放数据的，数据结构。

序列式容器 vector、deque、list
关联式容器 set、map、multiset、multimap
无序关联式容器 unordered_set、unordered_multiset、unordered_map、unordered_multimap

2、迭代器：看成是一种指针，广义指针（具备指针的功能）。可以访问容器中的元素。

3、算法：操作容器中的元素。

4、适配器：起到适配的作用。

容器适配器 stack、queue、priority_queue
迭代器适配器
函数适配器

5、函数对象（仿函数）：定制化操作。

6、空间配置器：进行空间的申请与释放操作的。使用 + 原理 + 源码

序列式容器

deque：双端数组。多个片段组成，片段内连续，片段间不连续。

list：双向链表。

迭代器的形式

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

初始化（掌握）

三种序列式容器，初始化的方法基本一样：

无参
count个value
迭代器
大括号

// 1.1、创建一个空对象
vector<int> number;// 1.2、创建count个value
vector<int> number2(10, 3);
vector<int> number3(10);// 1.3、迭代器范围
int arr[10] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
vector<int> number4(arr, arr + 10);//[,)左闭右开//1.4、使用大括号
vector<int> number5 = {1, 2, 3, 5, 6, 8, 7, 4};

遍历（掌握）

注意：list没有下标访问。

三种序列式容器，遍历的方法基本一样。对于vector与deque而言，可以使用：

下标
迭代器
for与auto

但是对于list而言，不能使用下标，但是另外两个遍历方式是可以的。

// 2.1、下标
for(size_t idx = 0; idx != number5.size(); ++idx){cout << number5[idx] << "  ";
}// 2.2、迭代器
// 2.2.1
vector<int>::iterator it;
for(it = number5.begin(); it != number5.end(); ++it){cout << *it << "  ";
}
// 2.2.2
vector<int>::iterator it2 = number5.begin();
for(; it2 != number5.end(); ++it2){cout << *it2 << "  ";
}// 2.3、for与auto
for(auto &elem : number5){cout << elem << "  ";
}

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

在尾部进行插入与删除

总结：三种序列式容器在尾部进行插入与删除是完全一样的。

push_back()
pop_back()

number.push_back(200); 	//没有返回值
number.pop_back(); 		//没有返回值

在头部进行插入与删除

注意：vector没有头插。

Q: 为何vector不能在头部进行插入与删除?

A: vector是**一端开口**的，如果提供在头部进行插入与删除的操作，那么动第一个元素，会导致后面的N个元素都需要移动，时间复杂度是O(N)

number.push_front(222);	//没有返回值
number.pop_front();		//没有返回值

vector源码阅读（了解）

类之间的继承图

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

源码

class  vector
{
public:typedef _Tp value_type;typedef value_type* pointer;typedef const value_type* const_pointer;typedef value_type* iterator;typedef const value_type* const_iterator;typedef value_type& reference;typedef const value_type& const_reference;typedef size_t size_type;typedef ptrdiff_t difference_type;};const map<int, string>  number = {{1, "hello"}};
number[1];

注意：对于vector而言，下标与at都可以随机访问，但是at比下标更加安全一些，at有范围检查。

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

deque源码阅读（了解）

类的继承图

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

容器的insert操作

总结：三种序列式容器都有四种插入的方法

找一个位置插入一个元素
找一个位置插入count个元素
找一个位置插入迭代器范围的元素
插入到括号

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

number.insert(it, 11); // 1 在迭代器位置插入元素11
number.insert(it, 5, 22); // 2 迭代器位置插入5个22
number.insert(it, vec.begin(), vec.end()); // 3
number.insert(it, {666, 999, 777, 555}); // 4

vector的迭代器失效（重要，坑）

对于vector的insert操作而言，不知道每次插入元素的个数是多少，当在进行插入的过程中，元素个数过多之后会进行**扩容，而迭代器还是指向的老的空间，然后再使用该迭代器的时候会发生问题，因为迭代器已经失效**了。

解决方案：每次在使用迭代器之前，**将迭代器重新置位**即可。

vector的erase操作（重要）

删除满足条件的元素的时候，后面的元素会前移，此时再执行++it，会漏掉某些元素，所以**不应该在删除的时候移动it**。

满足条件就删除，但是不移动迭代器的位置；没有删除元素的时候，才移动迭代器的位置。

for(auto it = number.begin(); it != number.end(); ){if(4 == *it){ // 删除vector中所有的元素4number.erase(it);}else{++it;}
}

容器的清空

vector有：

clear：清空元素，使 size = 0
size：存了多少个元素
capacity：容器的容量
shrink_to_fit：回收多余的空间，使 capacity = size

deque有：

clear：清空元素，使 size = 0，但它仍保有分配的内存
size：存了多少个元素
shrink_to_fit：回收多余的空间

list有：

clear：清空元素，使 size = 0
size：存了多少个元素

其他操作（三个容器都有）

swap函数：进行两个容器之间内容的交换。
resize函数：可以改变容器中元素的个数。
front函数：可以获取第一个元素。
back函数：可以获取最后一个元素。
emplace_back函数：这个函数的作用是在容器的末尾就地构造一个元素，而不是先构造一个临时对象然后将其移动或复制到容器中。emplace_back 函数通常比 push_back 函数更高效，因为它避免了额外的构造和析构操作。当你有一个需要插入的右值引用（如临时对象）时，push_back 可能会执行一次移动构造，而 emplace_back 直接在容器管理的内存空间中构造对象。

list的特殊操作

reverse函数：链表逆置
sort函数：链表排序。参数可以使用 std::less<int>() std::greater<int>() 或 CompareList() （自定义一个类重载函数调用运算符）
unique函数：去除**连续的**重复元素，一般配合sort使用
merge函数：两个链表合并（注意使用链表之前需要使用sort进行排序）

splice函数：从一个 list 转移元素给另一个

移动所有元素

number.splice(it, number2); //it为number的迭代器，操作完成后，number2变为空

移动一个元素

number.splice(it, number2, it2); //将number2中的it2指向元素，移动到number的it的前面

移动迭代器范围的元素

number.splice(it, number2, it2, it3); //将number2中的it2指向元素移动到number的it的前面

关联式容器

set的使用

基本特性

存放的是key类型，key值是**唯一**的，不能重复
默认会按照key值进行**升序**排列（从小到大）
底层使用的是**红黑树**

查找操作

size_t cnt = number.count(8); 	//存在返回1，不存在返回0
auto it = number.find(7); 		//以迭代器的形式返回在容器中的位置。不存在迭代器就指向number.end()

set容器的insert操作

使用方法：

找一个位置插入一个元素
找一个位置插入迭代器范围的元素
插入到括号

pair<set<int>::iterator, bool> ret = number.insert(7); //插入一个元素
number.insert(vec.begin(), vec.end()); //插入迭代器范围的元素
number.insert({6, 11, 7, 3, 21}); //插入大括号范围的元素

erase操作

number.erase(it); //删除迭代器指向的元素

set不支持修改，防止破坏红黑树的稳定性

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

不支持下标操作

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

set针对于自定义类型如何进行排序（重要）

方法一：模板的特化（全特化） std::less根据特定模板Point进行的特化
方法二：运算符重载，使用的是默认的std::less，但是两个Point不能比较大小，重载运算符来比较
方法三：模板参数Compare使用自己的函数对象

#include <math.h>
#include <iostream>
#include <set>
#include <vector>
#include <utility>using std::cout;
using std::endl;
using std::set;
using std::vector;
using std::pair;template <typename Container>
void display(const Container &con)
{for(auto &elem : con){cout << elem << "  ";}cout << endl;
}class Point
{
public:Point(int ix = 0, int iy = 0): _ix(ix), _iy(iy){}float getDistance() const { return hypot(_ix, _iy); }int getX() const { return _ix; }int getY() const { return _iy; }~Point(){}friend std::ostream &operator<<(std::ostream &os, const Point &rhs);friend bool operator<(const Point &lhs, const Point &rhs);friend struct ComparePoint;
private:int _ix;int _iy;
};std::ostream &operator<<(std::ostream &os, const Point &rhs)
{os << "(" << rhs._ix<< ", " << rhs._iy<< ")";return os;
}// ========================= 运算符重载 =======================
// 方法二：运算符重载，使用的是默认的std::less，但是两个Point不能比较大小，重载运算符来比较
bool operator<(const Point &lhs, const Point &rhs)
{cout << "bool operator<" << endl;if(lhs.getDistance() < rhs.getDistance()) {return true;}else if(lhs.getDistance() == rhs.getDistance()) {if(lhs._ix < rhs._ix) {return true;}else if(lhs._ix == rhs._ix) {if(lhs._iy < rhs._iy) {return true;} else {return false;}} else {return false;}} else {return false;}
}// ======================= 函数对象 ==========================
// 方法三：模板参数Compare使用自己的函数对象
struct ComparePoint
{bool operator()(const Point &lhs, const Point &rhs) const {cout << "struct ComparePoint" << endl;if(lhs.getDistance() < rhs.getDistance()) {return true;}else if(lhs.getDistance() == rhs.getDistance()) {if(lhs._ix < rhs._ix) {return true;}else if(lhs._ix == rhs._ix) {if(lhs._iy < rhs._iy) {return true;} else {return false;}} else {return false;}} else {return false;}}
};//模板的特化
//命名空间的扩展
namespace std
{
// ========================= 模板的特化（全特化） ========================
// 方法一：模板的特化 std::less根据特定模板Point进行的特化
template <>
struct less<Point>
{bool operator()(const Point &lhs, const Point &rhs) const {cout << "template <>" << endl;if(lhs.getDistance() < rhs.getDistance()) {return true;}else if(lhs.getDistance() == rhs.getDistance()) {if(lhs.getX() < rhs.getX()) {return true;}else if(lhs.getX() == rhs.getX()) {if(lhs.getY() < rhs.getY()) {return true;} else {return false;}} else {return false;}} else {return false;}}
};}
void test()
{set<Point> number = {/* set<Point, ComparePoint> number = { */Point(1, 2),Point(-1, 2),Point(1, 2),Point(3, 2),Point(1, -2),Point(4, -2),};display(number);
}int main(int argc, char *argv[])
{test();return 0;
}

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

multiset的使用

基本特性

存放的是key类型，**key值是不唯一**的，可以重复
默认会按照key值进行升序排列（从小到大）
底层使用的是红黑树

查找

count
find

bound函数

auto it = number.lower_bound(3); //返回第一个大于等于给定key值的迭代器auto it2 = number.upper_bound(3); //返回第一个大于给定key值的迭代器pair<multiset<int>::iterator, multiset<int>::iterator> ret = number.equal_range(3);
//返回的是一个范围，第一个迭代器指向的是大于等于给定key的迭代器，第二个迭代器是大于给定key的迭代器

插入操作

基本与set中的插入操作是一样，但是对于multiset而言，元素可以重复，所以插入肯定是可以成功的，返回类型不会像set一样，有pair类型。

erase操作

erase操作与set是一样的。也不支持修改、也不支持下标。

针对于自定义类型

自定义类型的三种写法：

模板的特化
函数对象的形式
运算符重载

与set针对于自定义类型是完全一样的。

总结：

元素都是有序的，默认都使用从小到大进行排序
底层使用的都是红黑树数据结构
set中的元素是唯一的，但是multiset中元素是可以重复的

map的使用

基本特征

存放的是key-value类型，**key值是唯一**的，不能重复；但是value值是可以重复的
默认情况下，会**按照key值进行升序**排列
底层实现也是使用的**红黑树**

查找操作

count
find

insert操作

pair<map<int, string>::iterator, bool> ret // = number.insert({5, "dongjing"});// = number.insert(pair<int, string>(5, "dongjing"));= number.insert(make_pair(5, "dongjing"));

map的下标（重要）

查找，不存在就插入
修改

multimap的使用

基本特征

存放的是key-value类型，**key值是不唯一**的，可以重复；但是value值是可以重复的
默认情况下，会按照key值进行升序排列
底层实现使用的也是红黑树

其他基本操作

count
find
insert

不支持下标

下标传进来的是key类型，而**multimap的key是可以重复的**

总结：

key值都是**有序的，默认都使用从小到大**进行排序
底层使用的都是**红黑树**数据结构
map中的元素key值是唯一的，但是multimap中key值是可以重复的

无序关联式容器

哈希

哈希函数

index = H(key)

通过哈希函数找到key值对应的位置。

构建哈希函数的方法

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

哈希冲突

H(key1) = H(key2),  key1 != key2

不同的key值通过哈希函数运算之后，位置值是一样的。

解决哈希冲突的方法

开放定址法、链地址法 (推荐使用这种，这也是STL中使用的方法)、再散列法、建立公共溢出区

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

装载因子

装载因子 = 元素的个数/表长 [0.5,0.75].装载因子值越低，代表冲突的概率越低，内存的使用率越低；装载因子的值越大，代表冲突的概率越高，内存的使用率也越高。数组其实就是一个完美的哈希。

unordered_set的使用

模板参数

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

基本特征

存放的是key类型，key值是**唯一**的，不能重复
元素是**没有顺序**的
底层使用的是**哈希**

其他操作

count
find
insert
erase

不支持修改、不支持下标访问。

针对于自定义类型

针对于std::hash进行改造

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

std::equal_to的改造

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

unordered_multiset的使用

基本特征

存放的是key类型，key值是**不唯一**的，可以重复
元素是**没有顺序**的
底层使用的是**哈希**

针对于自定义类型

与unordered_set针对于自定义类型是完全一样的。

unordered_map的使用

基本特征

存放的是key-value类型，key值是**唯一的，不能重复；但是value值不唯一**，是可以重复的
key值是**无序**的
底层实现使用的是**哈希**

其他的操作

count
find
insert
erase
下标操作

unordered_multimap的使用

基本特征

存放的是key-value类型，key值是**不唯一**的，可以重复；但是value值是可以重复的
key是值**没有顺序**的
底层实现使用的**哈希**

其他操作

count
find
insert
erase

unordered_multimap不支持下标。

容器的选择（重要）

有没有顺序

首先选择的是，关联式容器，元素都是有序的。最不应该想到的是，无序关联式容器，元素是没有顺序的。
备选方案，可以选择序列式容器。list有成员函数sort，vector与deque在算法库中有sort函数。

下标操作

vector、deque、map、unordered_map是具备下标。

时间复杂度

序列式容器，时间复杂度O(N)。

关联式容器，时间复杂度O(logN)。

无序关联式容器，时间复杂度O(1)。

迭代器的类型

序列式容器vector与deque，是随机访问迭代器。

关联式容器以及list，是双向迭代器。

无序关联式容器，是前向迭代器。

是不是所有的容器都有迭代器

容器适配器stack、queue、priority_queue是没有迭代器的。

优先级队列

模板类型

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

基本使用

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

针对于自定义类型

需要改写std::less，可以使用三种方式：模板的特化、函数对象的形式、运算符重载。

迭代器

基本概念

可以将迭代器看成是一种指针，但是不能完全等同于普通类型的指针，因为迭代器有可能是一个类类型，只是类类型中重载了指针一些运算符。

分类

随机访问迭代器、双向迭代器、前向迭代器、输入迭代器、输出迭代器

输出流迭代器

流对应有缓冲区，而缓冲区是可以用来存数据的，所以将流可以看成是容器。

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

class ostream_iterator
{
public://ostream_iterator<int> osi(cout, "\n");//ostream_type& __s = cout;//const _CharT* __c = "\n"ostream_iterator(ostream_type& __s, const _CharT* __c) : _M_stream(&__s)//_M_stream = &cout;, _M_string(__c) //_M_string = "\n"{}// ------------------------------------------------------------------------------ostream_iterator<_Tp>& operator=(const _Tp& __value) { *_M_stream << __value; // 等价 cout << 1if (_M_string) *_M_stream << _M_string; // 等价cout << "\n"return *this;}// -------------------------------------------------------------------------------ostream_iterator<_Tp>& operator*() {return *this;}ostream_iterator<_Tp>& operator++() { return *this; } ostream_iterator<_Tp>& operator++(int) { return *this; } // ----------------------------------------------------------------------------------
private:ostream_type* _M_stream;const _CharT* _M_string;
}; // end of class ostream_iterator// ===========================================================================================last 
1, 3, 5, 7, 6f
// 参数：
// _InputIter __first = vec.bein();
// _InputIter __last = vec.end();
// _OutputIter __result = osi
inline _OutputIter __copy(_InputIter __first, _InputIter __last,_OutputIter __result,input_iterator_tag, _Distance*)
{for ( ; __first != __last; ++__result, ++__first)*__result = *__first; // *__first解引用运算符重载得到1，调用拷贝构造函数return __result;
}
// ==============================================================================================
operator=(const int &rhs)
*osi = 1;Point pt = 10;

输入流迭代器

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

class istream_iterator
{
public:// 参数：// istream_iterator<int> isi(std::cin);// istream_type& __s = cinistream_iterator(istream_type& __s) : _M_stream(&__s) //_M_stream = &cin{ _M_read(); }// ----------------------------------------------------------------istream_iterator() : _M_stream(0), _M_ok(false) {}// ----------------------------------------------------void _M_read() {_M_ok = (_M_stream && *_M_stream) ? true : false;if (_M_ok) {*_M_stream >> _M_value;//cin >> _M_value = 3_M_ok = *_M_stream ? true : false;}}// ----------------------------------------------------bool _M_equal(const istream_iterator& __y) const{ return (_M_ok == __y._M_ok) && (!_M_ok || _M_stream == __y._M_stream); }// ----------------------------------------------------reference operator*() const { return _M_value; }istream_iterator& operator++() { _M_read(); return *this;}istream_iterator operator++(int) {istream_iterator __tmp = *this;_M_read();return __tmp;}
// ----------------------------------------------------
private:istream_type* _M_stream;_Tp _M_value;bool _M_ok;
};// 解析：copy(isi, istream_iterator<int>(), std::back_inserter(vec));
// 参数：
// _InputIter __first = isi;
// _InputIter __last = istream_iterator<int>();
// _OutputIter __result = std::back_inserter(vec);
inline _OutputIter __copy(_InputIter __first, _InputIter __last,_OutputIter __result,input_iterator_tag, _Distance*)
{for ( ; __first != __last; ++__result, ++__first)*__result = *__first;return __result;
}就是 *result = 1;// -------------------------------------------------------------------------
inline bool operator!=(const istream_iterator& __x, const istream_iterator& __y) 
{return !__x._M_equal(__y);
}// --------------------------------------------------------------------------
class back_insert_iterator
{
public:back_insert_iterator<_Container>& operator=(const int& __value) { container->push_back(__value);return *this;}back_insert_iterator<_Container>& operator*() { return *this; }back_insert_iterator<_Container>& operator++() { return *this; }back_insert_iterator<_Container>& operator++(int) { return *this; }
};

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

迭代器适配器

三组插入迭代器

函数模板back_inserter的返回结果是类模板back_insert_iterator类型，底层调用了push_back

函数模板front_inserter的返回结果是类模板front_insert_iterator类型，底层调用了push_front

函数模板inserter的返回结果是类模板insert_iterator类型，底层调用了insert

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

反向迭代器

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

算法

头文件

#include <algorithm>

算法库中的算法都是非成员函数。

for_each算法

template< class InputIt, class UnaryFunction >
UnaryFunction for_each( InputIt first, InputIt last, UnaryFunction f ); // 第三个参数：一元函数

一元函数：函数的参数是一个。

二元函数：函数的参数是两个。

一元谓词（断言）：函数的参数是一个，并且返回类型是bool。

二元谓词（断言）：函数的参数是两个，并且返回类型是bool。

#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>using std::cout;
using std::endl;
using std::for_each;
using std::copy;
using std::vector;
using std::ostream_iterator;void func(int &value) { // 加上引用就是可修改的++value;cout << value << " - ";
}void test() {vector<int> vec = {1, 3, 7, 9, 5, 8};copy(vec.begin(), vec.end(), ostream_iterator<int>(cout, "  "));cout << endl;/* ------------------------ 1 --------------------------------- */for_each(vec.begin(), vec.end(), func); // 只要first不等于last，就会把first进行解引用，解引用得到的值交给第三个参数/* -------------------2. lambda表达式---->匿名函数------------------ */// for_each(vec.begin(), vec.end(), //         [](int &value){//             ++value;//             cout << value << "  ";//         });/* ---------------------------------------------------------------- */cout << endl;copy(vec.begin(), vec.end(), ostream_iterator<int>(cout, "  "));cout << endl;
}int main(int argc, char *argv[]) {test();return 0;
}

lambda表达式

基本使用

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

每个部分的名字

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

捕获列表用法

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

#include <iostream>
#include <string>using std::cout;
using std::endl;
using std::string;void func()
{cout << "hello func" << endl;
}void test()
{int a = 100;/*[]捕获列表()函数的参数列表{}函数的函数体*/[]()->void{cout << "hello" << endl;// cout << a << endl; // error 没有捕获}();// lambda表达式默认是const的，如果想修改可以使用mutable// 值捕获[a]()->void{// ++a; // errorcout << "a = " << a << endl;cout << "hello" << endl;}();[a]()mutable->void{++a;cout << "a = " << a << endl;cout << "hello" << endl;}();// 引用捕获[&a]()->void{++a;cout << "a = " << a << endl;cout << "hello" << endl;}();cout << "aaaaaaa = " << a << endl;
}void test2()
{[](const string &name){cout << "===test2===" << endl;cout << "name = " << name <<endl;}("wangdao");cout << endl << endl;auto f = [](const string &name){cout << "test2" << endl;cout << "name = " << name <<endl;};f("test22222"); // 注释了就不会执行匿名函数cout << endl << endl;typedef void (*pFunc)(const string &); // C风格// using pFunc = void(const string &); // C++风格pFunc pf = [](const string &name){cout << "test2" << endl;cout << "name = " << name <<endl;};pf("wangdao wuhan");
}int main(int argc, char *argv[])
{test2();return 0;
}

#include <iostream>
#include <string>using std::cout;
using std::endl;
using std::string;int gNum = 100;void test()
{int num = 10;int age = 20;string name("wangdao");//值传递[num, name](const string &value){cout << "num = " << num << endl;cout << "name = " << name << endl;cout << "value = " << value << endl;cout << "gNum = " << gNum << endl;}("hello");cout << endl << endl;[&num, name](const string &value){++num;cout << "num = " << num << endl;cout << "name = " << name << endl;cout << "value = " << value << endl;}("hello");cout << endl << endl;[&num, &name](const string &value){++num;name = "wuhan";cout << "num = " << num << endl;cout << "name = " << name << endl;cout << "value = " << value << endl;}("hello");cout << endl << endl;cout << "num = " << num << endl;cout << "name = " << name << endl;cout << endl << "[=, &]"<< endl;// num使用引用传递，其他变量使用<值传递>[=, &num](const string &value){++num;// name = "nihao"; // errorcout << "num = " << num << endl;cout << "name = " << name << endl;cout << "age = " << age << endl;cout << "value = " << value << endl;}("hello");cout << endl << "[&, num]"<< endl;// num使用值传递，其他变量使用引用传递[&, num](const string &value){name = "wangdao";age = 30;// num = 999; // errorcout << "num = " << num << endl;cout << "name = " << name << endl;cout << "age = " << age << endl;cout << "value = " << value << endl;}("hello");
}int main(int argc, char *argv[])
{test();return 0;
}

remove_if

template< class ForwardIt, class UnaryPredicate >
ForwardIt remove_if( ForwardIt first, ForwardIt last, UnaryPredicate p );Removes all elements for which predicate p returns true.
移除谓词p返回true的所有元素。

1, 3, 4, 6, 8, 5, 3, 2
走到6时第一次返回迭代器
//remove_if(vec.begin(), vec.end(), func)f             lst
1, 3, 4, 6, 8, 5, 3, 2i->i 先做一次前置++f             lst
1, 3, 4, 6, 8, 5, 3, 2i->i->i->if             lst
1, 3, 4, 3, 8, 5, 3, 2i->i->i->if          lst
1, 3, 4, 3, 8, 5, 3, 2i->i->i->i->if          lst
1, 3, 4, 3, 2, 5, 3, 2i->i->i->i->iForwardIt remove_if(ForwardIt first, ForwardIt last, UnaryPredicate p){first = std::find_if(first, last, p); // 先看find_if源码if (first != last){for(ForwardIt i = first; ++i != last; ){if (!p(*i)){ // 8 > 4 返回true !p(*i)=false// 5 > 4// 3 < 4 将3赋给first// 2 < 4 将2赋给first*first++ = std::move(*i);}               }           }     return first;
}lst
1, 3, 4, 6, 8, 5, 3, 2f
constexpr InputIt find_if(InputIt first, InputIt last, UnaryPredicate p)
{for (; first != last; ++first) {if (p(*first)) {return first;}}return last;
}

#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>using std::cout;
using std::endl;
using std::for_each;
using std::remove_if;
using std::copy;
using std::vector;
using std::ostream_iterator;bool func(int value)
{return value > 4;
}void test0() {vector<int> vec = {1, 3, 4, 6, 8, 5, 3, 2};for_each(vec.begin(), vec.end(), [](int &value){ cout << value << "  "; });cout << endl;remove_if(vec.begin(), vec.end(), func);for_each(vec.begin(), vec.end(), [](int &value){ cout << value << "  "; });cout << endl;
}void test1()
{vector<int> vec = {1, 3, 4, 6, 8, 5, 3, 2};for_each(vec.begin(), vec.end(), [](int &value){ cout << value << "  "; });cout << endl;// remove_if不能将满足条件的元素一次删除，需要配合erase使用// auto it = remove_if(vec.begin(), vec.end(), bind1st(std::less<int>(), 4));auto it = remove_if(vec.begin(), vec.end(), bind2nd(std::greater<int>(), 4));// auto it = remove_if(vec.begin(), vec.end(), [](int value){ return value > 4; });// auto it = remove_if(vec.begin(), vec.end(), func);vec.erase(it, vec.end());for_each(vec.begin(), vec.end(), [](int &value){ cout << value << "  "; });cout << endl;/*1  3  4  6  8  5  3  2  1  3  4  3  2  5  3  2*/
}int main(int argc, char *argv[])
{test0();return 0;
}

vector扩容导致程序崩溃

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

bind1st、bind2nd

绑定二元函数的第一个、第二个参数

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>using std::cout;
using std::endl;
using std::for_each;
using std::remove_if;
using std::copy;
using std::vector;
using std::ostream_iterator;bool func(int value)
{return value > 4;
}void test0() {vector<int> vec = {1, 3, 4, 6, 8, 5, 3, 2};for_each(vec.begin(), vec.end(), [](int &value){ cout << value << "  "; });cout << endl;remove_if(vec.begin(), vec.end(), func);for_each(vec.begin(), vec.end(), [](int &value){ cout << value << "  "; });cout << endl;/* 输出：1  3  4  6  8  5  3  2  1  3  4  3  2  5  3  2i-----i 这一串多的元素，需要使用erase删除    */
}void test1()
{vector<int> vec = {1, 3, 4, 6, 8, 5, 3, 2};for_each(vec.begin(), vec.end(), [](int &value){ cout << value << "  "; });cout << endl;/* remove_if不能将vector中满足条件的元素一次删除，需要配合erase使用，这么设计是为了保证通用性，其他容器也可使用 */// auto it = remove_if(vec.begin(), vec.end(), func);// auto it = remove_if(vec.begin(), vec.end(), [](int value){ return value > 4; }); // 使用lambda表达式也ok/* 传入一个固定了一个参数的二元谓词 */// auto it = remove_if(vec.begin(), vec.end(), bind1st(std::less<int>(), 4)); // 固定第一个参数bind1st，用less 保留小于等于4的// auto it = remove_if(vec.begin(), vec.end(), bind2nd(std::greater<int>(), 4)); // 固定第二个参数bind2nd，用greater 保留小于等于4的// auto it = remove_if(vec.begin(), vec.end(), bind1st(std::greater<int>(), 4)); // 固定第一个参数bind1st，用greater 保留大于等于4的auto it = remove_if(vec.begin(), vec.end(), bind2nd(std::less<int>(), 4)); // 固定第二个参数bind2nd，用less 保留大于等于4的// auto it = remove_if(vec.begin(), vec.end(), bind2nd(4, std::less<int>())); // errorvec.erase(it, vec.end());for_each(vec.begin(), vec.end(), [](int &value){ cout << value << "  "; });cout << endl;
}int main(int argc, char *argv[])
{test1();return 0;
}

bind的使用（重要）

模板形式

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

引用折叠（模板可以进行推导，可以传左值或者右值）

& && = &;
&& && = &&;
& & = &;
&& & = &;

类似的：完美转发 std::forward

普通函数遇到参数为&&只能传右值

函数指针

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

bind的基本概念

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

function的使用

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

绑定的类型

可以绑定普通函数、成员函数、甚至还可以绑定数据成员。

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

如果使用的是地址传递，开销小，

使用值传递（传对象），开销大；

但是使用传地址，那么对象是不能提前销毁的，

但是传对象，那么可以提前销毁。

bind与function的结合使用

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

成员函数适配器mem_fn

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

函数对象（仿函数）

所有与小括号进行结合展示函数含义的对象。

函数名
函数指针
重载了函数调用运算符的类创建的对象

空间配置器（重要，难）

头文件与成员函数

#include <memory>//申请原始的未初始化的空间
T* allocate( std::size_t n );//释放空间
void deallocate( T* p, std::size_t n );//在指定空间构建对象
void construct( pointer p, const_reference val );//销毁对象
void destroy( pointer p );

特点

空间配置器会将**空间的申请与对象的构建**严格分开。

因为在STL中，元素的个数一般是批量创建，如果此时还创建一个对象就申请对应的空间，可能空间的申请回非常的频繁，那么也有可能会频繁的回收，那么频繁申请空间与回收空间，会导致效率比较低，所以就一次申请一大段空间，然后在该空间上构建对象。

应用

自定义vector实现

原理图

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

//一级空间配置器（malloc）
# ifdef __USE_MALLOC
typedef malloc_alloc alloc;
typedef __malloc_alloc_template<0> malloc_alloc;
class __malloc_alloc_template 
{
public:static void* allocate(size_t __n){void* __result = malloc(__n);if (nullptr == __result) __result = _S_oom_malloc(__n);//oom = out of memoryreturn __result;}static void deallocate(void* __p, size_t /* __n */){free(__p);}};//二级空间配置器（默认的空间配置器）
#else
typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc;
class __default_alloc_template 
{enum {_ALIGN = 8};enum {_MAX_BYTES = 128};enum {_NFREELISTS = 16}; union _Obj {union _Obj* _M_free_list_link;char _M_client_data[1];    /* The client sees this.        */};
public:static void* allocate(size_t __n){void* __ret = 0;if (__n > 128) {__ret = malloc(__n);//调用的是malloc}else {//16个自由链表 + 内存池//1、对于小空间而言，避免频繁申请空间与释放空间，也可以减少内存碎片的问题//2、在进行申请空间的时候，会涉及到用户态与内核态之间的频繁切换}return __ret;};static void deallocate(void* __p, size_t __n){if (__n > 128)malloc_alloc::deallocate(__p, __n);else {_Obj**  __my_free_list = _S_free_list + _S_freelist_index(__n);//_S_free_list[3]_Obj* __q = (_Obj*)__p;__q -> _M_free_list_link = *__my_free_list;*__my_free_list = __q;}}};#endifclass allocator 
{typedef alloc _Alloc;
public:_Tp* allocate(size_type __n, const void* = 0) {return __n != 0 ? static_cast<_Tp*>(_Alloc::allocate(__n * sizeof(_Tp))) : 0;}void deallocate(pointer __p, size_type __n){ _Alloc::deallocate(__p, __n * sizeof(_Tp)); }void construct(pointer __p, const _Tp& __val) { new(__p) _Tp(__val); //定位new表达式}void destroy(pointer __p) { __p->~_Tp(); }
};typename __default_alloc_template::_Obj* __default_alloc_template::_S_free_list[
# if defined(__SUNPRO_CC) || defined(__GNUC__) || defined(__HP_aCC)_NFREELISTS
# else__default_alloc_template::_NFREELISTS
# endif
] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, };static  size_t _S_freelist_index(size_t __bytes) 
{return ((32 + 8-1)/8 - 1); = 4 - 1 = 3
}//向上取整，得到8的整数倍
static size_t _S_round_up(size_t __bytes) //__bytes = 32
{ return ((32 + 8-1) & ~(8 - 1); 39 & ~739 = 32 + 4 + 2 + 1 = 0010 01117 = 0000 0111    1111 10000010 0111
&	1111 10000010 0000 = 32
}40 = 32 + 8 = 0010 10000010 1000
&	1111 10000010 1000 = 40 0001 1111
&	1111 1000	0001 100032---->32    33---->40
31---->32    25---->32
[25,32]------32
3.x  4char* __default_alloc_template::_S_start_free = nullptr;
char* __default_alloc_template::_S_end_free = nullptr;
size_t __default_alloc_template::_S_heap_size = 0;//1、申请32字节，内存池与堆空间中有足够的空间static void* allocate(size_t __n)//__n = 32{void* __ret = 0;else {_Obj** __my_free_list = _S_free_list + _S_freelist_index(__n);_Obj* __result = *__my_free_list;if (__result == nullptr)__ret = _S_refill(_S_round_up(__n));else {*__my_free_list = __result -> _M_free_list_link;__ret = __result;}}return __ret;};//_S_refill切割
void* __default_alloc_template::_S_refill(size_t __n)//__n = 32
{int __nobjs = 20;char* __chunk = _S_chunk_alloc(__n, __nobjs);//640_Obj** __my_free_list;_Obj* __result;_Obj* __current_obj;_Obj* __next_obj;int __i;__my_free_list = _S_free_list + _S_freelist_index(__n);//_S_free_list[3]__result = (_Obj*)__chunk;*__my_free_list = __next_obj = (_Obj*)(__chunk + __n);for (__i = 1; ; __i++) {__current_obj = __next_obj;__next_obj = (_Obj*)((char*)__next_obj + __n);if (__nobjs - 1 == __i) {__current_obj -> _M_free_list_link = 0;break;} else {__current_obj -> _M_free_list_link = __next_obj;}}return (__result);
}//__size = 32
//__nobjs = 20
//_S_chunk_alloc真正的进行申请空间
char* __default_alloc_template::_S_chunk_alloc(size_t __size, int& __nobjs)
{char* __result;size_t __total_bytes = __size * __nobjs = 32 * 20 = 640;size_t __bytes_left = _S_end_free - _S_start_free = 0;else {size_t __bytes_to_get = 2 * __total_bytes + _S_round_up(_S_heap_size >> 4)= 2 * 640 = 1280 ;_S_start_free = (char*)malloc(1280);//申请堆空间_S_heap_size += __bytes_to_get = 1280;_S_end_free = _S_start_free + __bytes_to_get;return (_S_chunk_alloc(__size, __nobjs));//递归调用}char* __result;size_t __total_bytes = __size * __nobjs = 32 * 20 = 640;size_t __bytes_left = _S_end_free - _S_start_free = 1280;if (__bytes_left >= __total_bytes) {__result = _S_start_free;_S_start_free += __total_bytes;return(__result);}
}//2、申请64字节，内存池与堆空间中有足够的空间
static void* allocate(size_t __n)//__n = 64{void* __ret = 0;else {_Obj* * __my_free_list= _S_free_list + _S_freelist_index(__n);//_S_free_list[7]_Obj*  __result = *__my_free_list;if (__result == nullptr)__ret = _S_refill(_S_round_up(__n));else {*__my_free_list = __result -> _M_free_list_link;__ret = __result;}}return __ret;
}//__n = 64
void* __default_alloc_template::_S_refill(size_t __n)
{int __nobjs = 20;char* __chunk = _S_chunk_alloc(__n, __nobjs);_Obj* __STL_VOLATILE* __my_free_list;_Obj* __result;_Obj* __current_obj;_Obj* __next_obj;int __i;__my_free_list = _S_free_list + _S_freelist_index(__n);//_S_free_list[7]__result = (_Obj*)__chunk;*__my_free_list = __next_obj = (_Obj*)(__chunk + __n);for (__i = 1; ; __i++) {__current_obj = __next_obj;__next_obj = (_Obj*)((char*)__next_obj + __n);if (__nobjs - 1 == __i) {__current_obj -> _M_free_list_link = 0;break;} else {__current_obj -> _M_free_list_link = __next_obj;}}return (__result);
}//__size = 64
//__nobjs = 20
char* __default_alloc_template::_S_chunk_alloc(size_t __size, int& __nobjs)
{char* __result;size_t __total_bytes = __size * __nobjs = 64 * 20 = 1280;size_t __bytes_left = _S_end_free - _S_start_free = 640;else if (__bytes_left >= __size) {__nobjs = (int)(__bytes_left/__size) = 640/64 = 10;__total_bytes = __size * __nobjs = 64 * 10 = 640;__result = _S_start_free;_S_start_free += __total_bytes;return(__result);}
}//3、申请96字节，内存池与堆空间中有足够的空间
//__n = 96
static void* allocate(size_t __n)
{void* __ret = 0;else {_Obj* * __my_free_list = _S_free_list + _S_freelist_index(__n);//_S_free_list[11]_Obj*  __result = *__my_free_list;if (__result == nullptr)__ret = _S_refill(_S_round_up(__n));else {*__my_free_list = __result -> _M_free_list_link;__ret = __result;}}return __ret;}
}//__n = 96
void* __default_alloc_template::_S_refill(size_t __n)
{int __nobjs = 20;char* __chunk = _S_chunk_alloc(__n, __nobjs);_Obj* __STL_VOLATILE* __my_free_list;_Obj* __result;_Obj* __current_obj;_Obj* __next_obj;int __i;__my_free_list = _S_free_list + _S_freelist_index(__n);__result = (_Obj*)__chunk;//1920*__my_free_list = __next_obj = (_Obj*)(__chunk + __n);for (__i = 1; ; __i++) {__current_obj = __next_obj;__next_obj = (_Obj*)((char*)__next_obj + __n);if (__nobjs - 1 == __i) {__current_obj -> _M_free_list_link = 0;break;} else {__current_obj -> _M_free_list_link = __next_obj;}}return (__result);}//__size = 96
//__nobjs = 20
char* __default_alloc_template::_S_chunk_alloc(size_t __size, int& __nobjs)
{char* __result;size_t __total_bytes = __size * __nobjs = 96 * 20 = 1920;size_t __bytes_left = _S_end_free - _S_start_free = 0;else {size_t __bytes_to_get = 2 * __total_bytes + _S_round_up(_S_heap_size >> 4)=  2 * 1920 + _S_round_up(1280 >> 4)= 3920;_S_start_free = (char*)malloc(3920);_S_heap_size += __bytes_to_get = 1280 + 3920 = 5200;_S_end_free = _S_start_free + __bytes_to_get;return(_S_chunk_alloc(__size, __nobjs));//递归调用	}char* __result;size_t __total_bytes = __size * __nobjs = 96 * 20 = 1920;size_t __bytes_left = _S_end_free - _S_start_free = 3920;if (__bytes_left >= __total_bytes) {__result = _S_start_free;_S_start_free += __total_bytes;return(__result);}
}//4、申请72字节，内存池与堆空间中没有连续的72字节
//__n = 72
static void* allocate(size_t __n)
{void* __ret = 0;else {_Obj* * __my_free_list = _S_free_list + _S_freelist_index(__n);//_S_free_list[8]_Obj*  __result = *__my_free_list;if (__result == nullptr)__ret = _S_refill(_S_round_up(__n));else {*__my_free_list = __result -> _M_free_list_link;__ret = __result;}}return __ret;}
}//__n = 72
void* __default_alloc_template::_S_refill(size_t __n)
{int __nobjs = 20;char* __chunk = _S_chunk_alloc(__n, __nobjs);_Obj* __STL_VOLATILE* __my_free_list;_Obj* __result;_Obj* __current_obj;_Obj* __next_obj;int __i;if (1 == __nobjs) return(__chunk);
}//__size = 72
//__nobjs = 20
char* __default_alloc_template::_S_chunk_alloc(size_t __size, int& __nobjs)
{char* __result;size_t __total_bytes = __size * __nobjs = 72 * 20 = 1440;size_t __bytes_left = _S_end_free - _S_start_free = 0;else {size_t __bytes_to_get =  2 * __total_bytes + _S_round_up(_S_heap_size >> 4)> 2880 ;_S_start_free = (char*)malloc(__bytes_to_get);if (0 == _S_start_free) {size_t __i;_Obj* * __my_free_list;_Obj* __p;//72 80 88 96for (__i = 72; __i <= 128;__i += 8) {//_S_free_list[8] _S_free_list[9] _S_free_list[10] _S_free_list[11]__my_free_list = _S_free_list + _S_freelist_index(__i);__p = *__my_free_list;if (nullptr != __p) {*__my_free_list = __p -> _M_free_list_link;_S_start_free = (char*)__p;_S_end_free = _S_start_free + __i;return(_S_chunk_alloc(__size, __nobjs));//递归调用}}}}char* __result;size_t __total_bytes = __size * __nobjs = 72 * 20 = 1440;size_t __bytes_left = _S_end_free - _S_start_free = 96;else if (__bytes_left >= __size) {__nobjs = (int)(__bytes_left/__size)  = 96/72 = 1;__total_bytes = __size * __nobjs = 72 * 1 = 72;__result = _S_start_free;_S_start_free += __total_bytes;return(__result);} 
}

总结：

allocate就是空间配置器进行申请空间的函数。
1、_S_freelist_index 取下标
2、_S_round_up 向上取整，得到8的整数倍
3、_S_refill 将申请回来的空间进行切割（按照指定大小切割多份，以链表的形式进行挂接）
4、_S_chunk_alloc 才是真正申请空间的函数，该函数有可能会调用malloc，该函数有可能会递归调用

空间配置器申请的空间都在堆上

https://blog.csdn.net/xy913741894/article/details/66974004

当自由链表中没有对应的内存块，系统会执行以下策略：
如果用户需要是一块n字节的区块，且n <= 128（调用第二级配置器），此时Refill填充是这样的：（需要注意的是：系统会自动将n字节扩展到8的倍数也就是RoundUP（n），再将RoundUP（n）传给Refill）。用户需要n块，且自由链表中没有，因此系统会向内存池申请nobjs * n大小的内存块，默认nobjs=20

如果内存池大于 nobjs * n，那么直接从内存池中取出
如果内存池小于nobjs * n，但是比一块大小n要大，那么此时将内存最大可分配的块数给自由链表，并且更新nobjs为最大分配块数x （x < nobjs）
如果内存池连一个区块的大小n都无法提供，那么首先先将内存池残余的零头给挂在自由链表上，然后向系统heap申请空间，申请成功则返回，申请失败则到自己的自由链表中看看还有没有可用区块返回，如果连自由链表都没了最后会调用一级配置器

最后

也就是STL可能存在的问题，通俗的讲就是优缺点吧

我们知道，引入相对的复杂的空间配置器，主要源自两点：

频繁使用malloc，free开辟释放小块内存带来的性能效率的低下
内存碎片问题，导致不连续内存不可用的浪费

引入两层配置器帮我们解决以上的问题，但是也带来一些问题：

内碎片的问题，自由链表所挂区块都是8的整数倍，因此当我们需要非8倍数的区块，往往会导致浪费，比如我只要1字节的大小，但是自由链表最低分配8块，也就是浪费了7字节，我以为这也就是通常的以空间换时间的做法，这一点在计算机科学中很常见。
我们发现似乎没有释放自由链表所挂区块的函数？确实是的，由于配置器的所有方法，成员都是静态的，那么他们就是存放在静态区。释放时机就是程序结束，这样子会导致自由链表一直占用内存，自己进程可以用，其他进程却用不了。
t __i;
_Obj* * __my_free_list;
_Obj* __p;
```
 	//72 80 88 96for (__i = 72; __i <= 128;__i += 8) {//_S_free_list[8] _S_free_list[9] _S_free_list[10] _S_free_list[11]__my_free_list = _S_free_list + _S_freelist_index(__i);__p = *__my_free_list;if (nullptr != __p) {*__my_free_list = __p -> _M_free_list_link;_S_start_free = (char*)__p;_S_end_free = _S_start_free + __i;return(_S_chunk_alloc(__size, __nobjs));//递归调用}}}
```
}

char* __result;
size_t __total_bytes = __size * __nobjs = 72 * 20 = 1440;
size_t __bytes_left = _S_end_free - _S_start_free = 96;

else if (__bytes_left >= __size)
{
__nobjs = (int)(__bytes_left/__size) = 96/72 = 1;
__total_bytes = __size * __nobjs = 72 * 1 = 72;
__result = _S_start_free;
_S_start_free += __total_bytes;
return(__result);
}
}

## 总结：allocate就是空间配置器进行**申请空间**的函数。
1、`_S_freelist_index` 取下标
2、`_S_round_up` 向上取整，得到8的整数倍
3、`_S_refill` 将申请回来的空间进行切割（按照指定大小切割多份，以链表的形式进行挂接）
4、`_S_chunk_alloc` 才是真正申请空间的函数，该函数有可能会调用malloc，该函数有可能会递归调用空间配置器申请的空间都在堆上https://blog.csdn.net/xy913741894/article/details/66974004当自由链表中没有对应的内存块，系统会执行以下策略：
如果用户需要是一块n字节的区块，且n <= 128（调用第二级配置器），此时Refill填充是这样的：（需要注意的是：系统会自动将n字节扩展到8的倍数也就是RoundUP（n），再将RoundUP（n）传给Refill）。用户需要n块，且自由链表中没有，因此系统会向内存池申请nobjs * n大小的内存块，默认nobjs=20- 如果内存池大于 nobjs * n，那么直接从内存池中取出- 如果内存池小于nobjs * n，但是比一块大小n要大，那么此时将内存最大可分配的块数给自由链表，并且更新nobjs为最大分配块数x （x < nobjs）- 如果内存池连一个区块的大小n都无法提供，那么首先先将内存池残余的零头给挂在自由链表上，然后向系统heap申请空间，申请成功则返回，申请失败则到自己的自由链表中看看还有没有可用区块返回，如果连自由链表都没了最后会调用一级配置器## 最后也就是STL可能存在的问题，通俗的讲就是优缺点吧我们知道，引入相对的复杂的空间配置器，主要源自两点：1. 频繁使用malloc，free开辟释放小块内存带来的性能效率的低下
2. 内存碎片问题，导致不连续内存不可用的浪费引入两层配置器帮我们解决以上的问题，但是也带来一些问题：1. 内碎片的问题，自由链表所挂区块都是8的整数倍，因此当我们需要非8倍数的区块，往往会导致浪费，比如我只要1字节的大小，但是自由链表最低分配8块，也就是浪费了7字节，我以为这也就是通常的以空间换时间的做法，这一点在计算机科学中很常见。
2. 我们发现似乎没有释放自由链表所挂区块的函数？确实是的，由于配置器的所有方法，成员都是静态的，那么他们就是存放在静态区。释放时机就是程序结束，这样子会导致自由链表一直占用内存，自己进程可以用，其他进程却用不了。