前言

仿函数提供了一种调用算法的方式、算法通过迭代器对容器里边的数据进行访问和处理、迭代器是访问容器中数据的重要方式、而容器所占有的内存空间是由配置器分配和管理的。此外，适配器是对容器、迭代器或仿函数的一个封装。

1、配置器

(1)What

负责空间配置与管理，从实现角度来看，配置器是一个实现了动态空间配置、空间管 理、空间释放的类模板

(2)Why

动态内存管理（内存分配、对象构造、对象析构、内存释放、内存重新分配等）

(3)How

A.调用new和delete实现内存分配与销毁

B.STL Allocator

对象的构造由allocator类的construct负责，对象的释放由destroy负责
内存配置由allocate()负责，内存释放由deallocate()负责

(4)allocator类

A.What

C++11中预定义的配置器类，用于管理容器的内存分配是释放

B.How

allocator类的使用主要关注它的四个成员函数：

• 分配内存：allocate()
• 构造对象：construct()，在分配好的内存中构造对象
• 销毁对象：destroy()，回收已分配的内存空间，释放数据对象
• 回收内存：deallocate()，将内存空间归还给操作系统

//分配 10 个 string 类型的对象的内存（未初始化） 
std::allocator<string> alloca;
auto const p=alloca.allocate(10); //分配未构造的内存
alloca.construct(p,"zhangsan"); 
auto q=p;
alloca.construct(++q,"lisi"); 
alloca.construct(++q,"wangwu"); 
cout<<(*q)<<endl; //打印：wangwu
//使用完对象后，必须对每个构造的元素调用 destroy 类销毁它们 
while(q!=p)
{ 
	alloca.destroy(--q); 
}
//元素被销毁之后，可以重新使用 alloca,也可以归还给系统 
alloca.deallocate(p,10);

C.allocator的算法

//拷贝和填充未初始化内存的算法：在未初始化的内存中创建对象 
std::vector<int> vec_a{1,2,3,4,5};
std::allocator<int> alloca_int; 
int* p_int=alloca_int.allocate(vec_a.size()*2);//p_int 为 int 类型的指针
//拷贝元素到 alloca_int 的内存中去
std::uninitialized_copy(vec_a.begin(),vec_a.end(),p_int);
for(int i=0;i<vec_a.size();++i){cout<<*(p_int+i)<<" ";}cout<<endl;//打印：1 2 3 4 5
//将剩余的元素初始化为 100
std::uninitialized_fill_n(p_int,vec_a.size(),100);
for(int i=0;i<vec_a.size();++i){cout<<*(p_int+i)<<" ";}cout<<endl;//打印：100 100 100 100 100

2、容器

(1)What

本质是标准库中特定用于存储和管理数据的类模板

(2)Which（有哪些容器）

• 序列容器（顺序容器）：容器中的数据是有序的
• 关联容器：通过键值对(key-valuepair)来组织和访问元素，将红黑树作为底层数据结构，用于维护 键值对集合，并提供高效的元素访问和操作能力，本质是类模板

(3)序列容器（顺序容器）

A.Which

array、deque、forwarrd_list、list、vector

B.array：存储固定长度元素的序列

基本使用：导入array、构建array对象、调用array对象函数、使用算法对容器元素进行操作

#include <array>
std::array<int, 6> array01{11,22,33,44,55,66};

非成员函数

• get(array):

template <int Index, class T, size_t N> constexpr T& get(array<T,N>&arr> noexcept;

std::array<int,4> c0{0,1,2,3}; //创建并初始化一个array类对象c0
for(const int &iTmp:c0)
{
	cout<<" "<<iTmp;
}
int i1 = std::get<1>(c0); // 得到1
int i3 = std::get<3>(c0); // 得到3

• swap(array01, array02):

template<class T, std::size_t N>
void swap(array<T, N>&arr01, array<T,N> &arr01);

//成员函数
arr01.swap(arr02);
//非成员函数
swap(arr01, arr02);

• 其它非成员函数：
  
  成员函数

成员函数	说明
array()	构造函数
at()	返回指定位置的引用
font() / back()	返回第一个元素 （最后一个）元素的引用
begin() / end()	返回第一个（最后一个）元素的迭代器
cbegin() / cend()	返回第一个（最后一个）元素的常量迭代器
rbegin() / rend()	返回反向数据中第一个（最后一个）元素的迭代器
data()	返回第一个元素的地址
empty()	测试array对象中是否存在数据
fill()	将所有元素替换为指定值
assign()	同fill
size()	返回array对象中元素的个数
swap()	交换两个array对象的数据

C.deque队列

基本使用：导入deque、创建deque对象、调用对象函数、使用算法对容器中元素进行操作

#include <deque>
std::deque<int> q01(10); //指定队列长度
std::vector<int> vec{1,2,3,4,5}
std::deque<int> q02(vec.begin(),vec.end()); //q02有初始值

非成员函数：

• swap(q01,q02)：交换两个队列数据

成员函数：

成员函数	说明
at()	返回指定位置的引用
font() / back()	返回第一个元素 （最后一个）元素的引用
begin() / end()	返回第一个（最后一个）元素的迭代器
cbegin() / cend()	返回第一个（最后一个）元素的常量迭代器
rbegin() / rend()	返回反向数据中第一个（最后一个）元素的迭代器
data()	返回第一个元素的地址
empty()	测试容器中是否存在数据
fill()	将所有元素替换为指定值
assign()	同fill
size()	返回array对象中元素的个数
swap()	交换两个容器的数据
emplace()	就地构造元素插入到deque指定位置
emplace_back() / emplace_front()	就地构造元素插入到末尾（开头）
erase()	从指定位置删除一个或多个元素
insert()	在指定位置插入一个或多个元素
pop_back() / pop_front()	清除deque末尾（开头）元素
push_back() / push_front()	添加元素到末尾（开头）
resize()	为deque指定新的大小

D.vector

基本使用：导入vector、构建vector对象、调用vector函数、使用算法对容器中元素进行处理

#include <vector>
std::vector<int> vecArr01;

非成员函数：

• hash()：返回vector对象的哈希值
• swap( vec01, vec02);

成员函数：

成员函数	说明
font() / back()	返回第一个元素 （最后一个）元素的引用
begin() / end()	返回第一个（最后一个）元素的迭代器
cbegin() / cend()	返回第一个（最后一个）元素的常量迭代器
emplace_back()	在末尾处添加元素
emplace()	在指定位置插入就地构造的元素
push_back() / pop_back()	添加（删除）末尾处的元素
sort()	对容器中的元素进行排序
reverse()	颠倒元素中的顺序
size()	返回容器中元素的数量
shrink_to_fit()	放弃额外的容量
swap()	交换两个容器的元素

E.forward_list

基本使用：导入forward_list、创建对象、调用对象函数、使用算法对容器中元素进行处理

#include <forward_list>
std::forward_list flst01(10);

成员函数:

成员函数	说明
font()	返回第一个元素 （最后一个）元素的引用
begin() / end()	返回第一个（最后一个）元素的迭代器
cbegin() / cend()	返回第一个（最后一个）元素的常量迭代器
emplace_after()	在指定位置之后创建元素
erase_after()	删除指定位置之后的元素
insert_after()	在指定元素之后添加元素
pop_front()	删除起始处的一个元素
push_front()	在起始处插入一个元素
sort()	对容器中的元素进行排序
reverse()	颠倒元素中的顺序

F.list

基本使用：导入list、构建list对象、调用list对象函数、使用算法对容器中元素进行处理

#include <list>
std::list<int> lst;

非成员函数：

• swap(lst01, lst02);

成员函数：

成员函数	说明
font() / back()	返回第一个元素 （最后一个）元素的引用
begin() / end()	返回第一个（最后一个）元素的迭代器
cbegin() / cend()	返回第一个（最后一个）元素的常量迭代器
emplace_after()	在指定位置之后创建元素
emplace_front()	在起始位置处添加一个元素
emplace_after()	在结尾位置处添加一个元素
erase()	从列表中指定位置删除一个元素
insert()	在指定位置插入一个或多个元素
pop_back() / pop_front()	删除末尾（起始）元素
push_back() / push_front()	在末尾（起始）处添加元素
sort()	对容器中元素进行排序
splice()	将自定义的列表从list对象中删除或加入

G.string

基本使用：导入string、创建对象、调用string对象的函数、使用算法对string对象中元素进行处理

#include <string>
std::string strFlePth = "D:\\a.text";

非成员函数：

• getline(strSrc, line); //逐行提取srtSrc中的字符串
• swap(str01, str02); //交换两个字符数组

专用化非成员模板函数：

函数名	说明
stod() / stof() / stoi() / stold() / stoll() / stoul() / stoull()	将string转为double / float / int / long double / unsigned long long
to_string()	将其它类型转为string类型
to_wstring()	转为宽字符串类型

H.tuple

What:

用于存储多个不同类型的元素的通用容器类模板

Why:

灵活地适应不同类型的元素，并提供相应的操作和访问方式；当我们希望将一些数据 组合成对象，但又不想自定义数据结构来表示该对象时，tuple 将非常有用

How:

构造tuple对象和初始化

// 默认构造函数
std::tuple<string, int, vector<double>> t0; 
cout << std::boolalpha << (std::get<1>(t0) == 0) << endl; // 打印：true
// 参数化构造函数
std::tuple<string, int, vector<double>> t1("zhangsan", 23, {32, 33, 34});
// 拷贝构造函数
auto t1_copyF(t1); cout << std::get<0>(t1_copyF) << endl; // 打印：zhangsan
// 移动构造函数
auto t1_mvF(std::move(t1_copyF)); cout << std::get<0>(t1_mvF) << endl; // 打印：zhangsan cout << std::boolalpha << (std::get<0>(t1_copyF) == "") << endl; // 打印：true
// 拷贝赋值运算符
auto t1_copy = t1; 
cout << std::get<0>(t1_copy) << endl; // 打印：zhangsan 
cout << std::get<0>(t1) << endl; // 打印：zhangsan
// 移动赋值运算符
cout << std::get<0>(t1) << endl; // 打印：zhangsan 
auto t1_mv = std::move(t1);
cout << std::get<0>(t1_mv) << endl; // 打印：zhangsan 
cout << std::boolalpha << (std::get<0>(t1) == "") << endl; // 打印：true

make_tuple

// make_tuple 
std::tuple<string, int, vector<double>> t2 = 
				std::make_tuple("lisi", 24, vector<double>({44.0, 45, 46}));
cout << std::get<0>(t2) << ", " << std::get<1>(t2) << ", {"
	<< std::get<2>(t2)[0] << "," << std::get<2>(t2)[1] << "," 
	<< std::get<2>(t2)[2] << "}" << endl;

函数名	说明
get(tp)	返回第i个元素的引用
typle_size<typleType:>::value	返回元组的长度
tuple_element<i,tupleType>::type	返回元组第i项的类型

(4)关联容器

A.What

通过键值对(key-valuepair)来组织和访问元素，将红黑树作为底层数据结构，用于维护 键值对集合，并提供高效的元素访问和操作能力，本质是类模板

B.Which

C.Why

• 维护映射关系：一个值（也称为数据）与一个唯一的键相关联
• 快速查找：通过以键作为索引，可以高效地查找、访问和修改相应的值
• 自动排序：关联容器中的元素通常是自动根据键进行排序的，这样可以保持元素的有序性
• 唯一性保证：关联容器中的键是唯一的，这意味着每个键只能关联一个值

D.pair

基本使用：导入pair、创建pair对象、调用对象的函数

#include <utility> 
std::pair<string,int> name_age{"赵家的狗",5000};

常见函数： make_pair()

#include <utility> 
std::pair<string,int> name_age{"赵家的狗",5000}; std::pair<string,int> mingDynasty_age("明朝",276); 
string songDynasty="宋朝"; int ageSong=247;
auto songDynasty_age=std::make_pair(songDynasty,ageSong); cout<<name_age.first<<","<<name_age.second<<endl;
cout<<mingDynasty_age.first<<","<<mingDynasty_age.second<<endl; cout<<songDynasty_age.first<<","<<songDynasty_age.second<<endl;

E.map

基本使用：导入库、创建对象、调用对象函数、使用算法对容器元素处理

#include <map>
std::map<int, string> map01;

非成员函数：

• swap(map01, map02);

成员函数：

成员函数	说明
begin() / end()	返回第一个（最后一个）元素的迭代器
cbegin() / cend()	返回第一个（最后一个）元素的常量迭代器
clear()	清除容器中所有元素
contains()	检查容器中是否包含具有指定键的元素
emplace()	就地构造元素插入到map中
empty()	判断容器是否为空
erase()	从指定位置移除容器中的元素
get_allocator()	返回map对象的副本
lower_bound()	返回一个迭代器，迭代器指向键值大于等于指定键值的第一个元素
upper_bound()	类比lower_bound()
swap()	交换两个map元素

说明：set、multimap、multiset等和map函数差不多，这里就不继续陈列相关函数说明了，值得一提的是无序关联容器

F.unordered_map

无序容器使用一个哈希函数将元素映射到桶，访问元素时，先计算元素的哈希值，根 据哈希值找到桶，容器将具有一个特定哈希值的所有元素都保存在相同的桶中

桶接口：

成员函数：

成员函数	说明
at	查找具有指定键的元素
bucket()	获取键值对的桶编号
hash_function()	获取存储的哈希函数对象
rehash()	重新生成哈希表

说明：其它成员函数类比于map类的成员函数

重载hasher()和eqOp()函数：

3、迭代器

(1)What

一种“泛型指针”,也叫“广义指针”,本质是重载了各种操作符的类模板

(2)Why

可以循环访问 C++ 标准库容器中的元素，而不必考虑容器的类型和存储细节

(3)Which（迭代器类型）

A.输出迭代器

输出迭代器	说明
ostream_iterator	用于将数据写入输出流，例如 std::cout
back_insert_iterator	用于在容器的末尾插入元素, std::back_inserter(container)
front_insert_iterator	用于在容器的开头插入元素, std::front_inserter(container)
insert_iterator	用于在容器的指定位置插入元素, std::inserter(container,position)

ostream_iterator

std::ostream_iterator<int> it_cout(std::cout, " "); 
*it_cout = 100; 
++it_cout; 
*it_cout = 200;
std::cout << std::endl; // 打印：100 200

back_insert_iterator

std::vector<int> years{1894, 1927, 1928, 1935, 1937, 1945, 1949, 1951, 1956, 1959, 1964, 1973, 1978, 1998};
std::back_insert_iterator<std::vector<int>> it_inster_years_back(years); 
*it_inster_years_back = 2001; 
++it_inster_years_back;
*it_inster_years_back = 2008; 
for (auto const &item : years){ std::cout << item << std::endl;} // 打印：1894-2008

B.输入迭代器

输入迭代器	说明
istream_iterator	用于从输入流（如标准输入 cin）中按顺序读取数据的迭代器
istreambuf_iterator	用于从输入流缓冲区中读取字符的迭代器
istream_token_iterator	扩展了 istream_iterator，可以使用分隔符将输入流分割成单词或标记。可以使用自定义的分隔符来指定如何划分输入

std::ifstream in_stream2; 
in_stream2.open(sentences_file_path.c_str()); 
if (!in_stream2.is_open())
{
	std::cout << "Open failed!" << std::endl; 
}
std::istream_iterator<string> it_istream(in_stream2); 
std::istream_iterator<string> it_end;
while (it_istream != it_end)
{
	std::cout << *it_istream << std::endl; ++it_istream;
}

C.单向迭代器

一种只能向前遍历容器元素的迭代器，用于访问支持顺序访问的容器（如链表、单 向链表等）

单向迭代器	说明
forward_list 迭代器	用于遍历 forward_list（单向链表）容器的元素。它只能向前遍历，不支持反向遍历或随机访问
unordered_set 和 unordered_multiset 迭代器	它们使用哈希表存储元素，不保证元素的顺序。迭代器按照插入顺序遍历。这些迭代器只支持向前遍历。
unordered_map 和 unordered_multimap 迭代器	迭代器按照插入顺序遍历键值对。这些迭代器也只支持向前遍历

D.双向迭代器

双向迭代器	说明
list 迭代器	它支持双向遍历，可以使用 ++ 和 – 操作符向前或向后遍历元素
set 和 multiset 迭代器	它们按照一定的排序规则存储元素，迭代器按照升序遍历
map 和 multimap 迭代器	它们存储键值对，并按照键进行排序

E.随机访问迭代器

• std::vector 的迭代器
• std::deque 的迭代器
• std::array 的迭代器
• std::string 的迭代器

4、适配器

(1)What

标准库中的一种特殊容器类型，是对容器的一种封装：stack、queue、priority_queue
默认情况下:
stack 和 queue 是基于 deque 实现的
priority_queue 是基于 vector 实现的

(2)Why

封装细节，进一步解放程序员对底层代码的操作，使其只需关注业务逻辑

(3)栈适配器

std::stack<int> s;
s.push(1);
s.push(2);
s.push(3);
s.pop();
int iTop = s.top(); // 2

(4)队列适配器

std::queue<int> que;
que.push(1);
que.push(2);
que.push(3);
int iFir = que.front(); // 1
que.pop();
iFir = que.front(); // 2
int iLst = que.back(); // 3

5、算法

(1)What（什么是STL中的算法）

用来处理标准容器的函数模板

(2)Which

<algorithm>：提供了大量通用的算法函数，用于对各种容器中的元素进行操作和处理
<cstdlib>：stdlib.h的 C++版本，提供了动态内存管理、随机数生成、与环境交互、整数算术、搜索、排序、字符串转换以及多字节或宽字符处理等功能
<numeric>：定义了一些基础性的数值算法

(3)<algorithm>

函数名	说明
adjacent_find	搜索相等或满足指定条件的两个相邻元素
all_of	测试所有元素都满足指定条件
binary_search	测试有序范围中是否有指定要查找的值
sort	对范围内的序列进行排序
find	在指定范围内查找指定值
reverse	反转指定范围内的元素
count	计算指定范围内指定数据出现的次数

说明：由于该库存在大量算法，这里仅对几个常用函数进行介绍，读者在实践中，但凡需要对容器中的数据进行某种处理，就可以查看algorithm库是否存在您所需要的算法

(4)cstdlib

函数名	说明
malloc	分配指定字节数的内存块，如果内存不够，返回NULL
calloc(num, size)	分配num个连续内存空间，每一块大小为size
free(ptr)	释放指定内存
atof(const char *ch) | atoi |atol | atoll	将char指针转为double、int、long等
srand(uint seed)	设置随机数生成器的种子
rand()	产生一个范围在0到RAND_MAX（32767）之间的随机整数
char getenv(const charname)	返回一个指向环境变量的指针
abort()	异常终止一个进程
exit(int state)	程序中止执行，返回调用过程。参数state为0表示正常中止，非0表示非正常中止
qsort()	对数组进行快速排序
abs() |labs()	计算绝对值

(5)numric

函数名	说明
accumulate	求和
adjacent_difference	计算相邻元素之间的差值（后一个减前一个元素）
inner_product	对两个序列进行内积运算
partial_sum	对指定范围内的元素进行局部求和

6、仿函数

(1)What

一种重载了 operator()函数调用符的类或类模板，行为类似函数

(2)Why（仿函数的作用）

A.可作为排序规则

class StudentScoreRule {
public: 
	bool operator()(Student stu01, Student stu02) 
	{
		return stu01.getScore() > stu02.getScore();
	}
};
int main()
{ 
	std::set<Student, StudentScoreRule> studentSet;
	studentSet.clear();
	Student zs("张三", 23, 168); 
	Student ls("李四", 24, 178); 
	Student ww("王五", 25, 188); 
	Student zl("赵六", 26, 144); 
	Student qq("钱七", 27, 177); 
	Student nb("牛八", 28, 288); 
	studentSet.insert({zs, ls, ww, zl, qq, nb});
	cout << "*****************************************" << endl; 
	for (auto stu : studentSet)
		cout << stu.getName() << "\t" << stu.getAge() << "\t" << stu.getScore() << endl; 
	cout << "*****************************************" << endl;
}

studentSet对象将按照学生的分数进行排序存储

B.作为判别式使用

class Number
{
public:
	int num; 
	Number(int num_) : num(num_) {} 
	Number() { num = 0; }
	bool operator()(int a) {
		return a % this->num == 0;
	}
};

//删除所有能被 2 整除的元素 
std::list<int> tmp_list;
for (int i = 1; i < 20; ++i) 
	tmp_list.emplace_back(i); 
auto pos = std::remove_if(tmp_list.begin(), tmp_list.end(), Number(2));
tmp_list.erase(pos, tmp_list.end());

C.可携带更多信息，拥有多种内部状态

class mySequence
{
private:
	int val; 
public:
	mySequence(int val_) : val(val_) {} 
	int operator()() {
		return this->val++;
	}
};
std::list<int> list01; 
std::generate_n(std::back_inserter(list01), 9, mySequence(1));

D.作为算法 for_each 的返回值

class Average {
private:
	int count_n; 
	double sum; public:
	Average(int val = 0, int count_n_ = 0) : sum(val), count_n(count_n_) {}
	void operator()(double x) {
		++count_n; 
		sum += x; 
	}
	double getAveValue() { return sum / count_n; }
}; 
std::set<double> money{10.88, 12.88, 14, 13, 16.88, 20, 21.98}; 
Average res = std::for_each(money.begin(), money.end(), Average()); 
cout << res.getAveValue() << endl;
//方法 2 cout << "**********************************************" << endl; 
double sum = 0;
std::for_each(money.rbegin(), money.rend(), [&sum](double x){ sum += x; }); 
cout << sum / money.size() << endl;