[C++知识库]C++ STL重点、难点复习总结

前言

【C++】学习已经接近尾声了，这篇文章里都是面试复习的知识点，在排版界面方面可能会有点乱，博主没有把精力放在这些上，主要是一些干货，帮助那些需要面试的小伙伴以及回顾一些重点知识。

一.STL的本质

6大组件：容器、算法、迭代器、仿函数（函数对象）、适配器、空间配置器

它们之间的关系是：

二.容器（重点中重点）：

string/vector/list+map/sett/unordered_map/unordered_set + 其它容器(如deque/array/forward_list/bit_set 这些答酱油的了解一下就🆗)

三.迭代器（重点）

迭代器是一种设计模式，让用户通过特定的接口访问容器的数据，不需要了解容器内部的底层数据结构。

C++中迭代器本质：是一个指针，让该指针按照具体的结构去操作容器中的数据

1. 使用角度分类：正向/反向+const组合成4种类型

2. 功能角度分类（了解）：单向迭代器/双向迭代器/随机迭代器**（容器的底层实现结构决定的）**

   2.1 单向：forward_list、unordered_xxx 支持++

   2.2 双向：list、map/set 支持++、–

   2.3 随机：string、deque、array、vector 支持++、–、+、-

四.算法

swap、find、reverse、sort；算法：问题的求解步骤，以有限的步骤，解决数学或逻辑中的问题。STL中的算法主要分为两大类：与数据结构相关算法(容器中的成员函数)和通用算法(与数据结构不相干)。STL中通用算法总共有70多个，主要包含：排序，查找，排列组合，数据移动，拷贝，删除，比较组合，运算等。

vector<int>v1={1,2,3,4,5};
vector<int>v2={10,20,30,40,50};
swap(v1,v2);

C++98中不建议这样交换，因给涉及深拷贝，不仅仅是vector，所以容器的交换，都不建议用这个，推荐用这个v1.swap(v2)，使用底层的成员函数交换（拷贝构造、赋值构造）

C++11，可以随便用，为什么呢？我们看它底层实现代码（移动构造、移动赋值）

迭代器按功能分类跟算法之间的关系：

vector<int>v={1,2,3,4,5,6};//随机
list<int>l={1,2,3,4,5};//双向
fowrward_list<int>f1={1,2,3,4,5};//单向

reverse(v.begin(),v.end());//ok
reverse(l.begin(),l.end());//ok
//reverse(f.begin(),f.end());//error,单向不支持其它迭代

我们手机是不是都是6位密码保护，告诉你哪几个数字，你有哪些组合破解它呢？有一种就是 全排列算法：

vector<int>v={5,1,2,4,3};
//全排列要求数据有序
sort(v.begin(),v.end());
do
{
    for(auto e: v)
    {
        cout<<e<<" ";
    }
}while(next_permutation(v.begin(),v.end()));

next_permutation升序prev_permutation降序

1.sort

排序在实际应用中需要经常用到，而在目前的排序中，快排平均情况下是性能最好的一种排序，但是快排也有其自身的短板，比如说：元素接近有序、元素量比较大的情况下，直接使用快排时，堪称一场灾难。因此STL中sort算法并没有直接使用快排，而是针对各种情况进行了综合考虑。下面关于sort函数分点进行说明：

1. sort函数提供了两个版本
   sort(first, last)：默认按照小于方式排序，排序结果为升序，一般用排内置类型数据
   sort(first, last, comp)：可以通过comp更改元素比较方式，即可以指定排序的结果为升序或
   者降序，一般以仿函数对象和函数指针的方式提供
2. sort并不是一种排序算法，而是将多个排序算法混合而成
3. 当元素个数少于__stl_threshold阈值时(16)，使用直接插入排序处理__
4. 当元素个数超过__stl_threshold时，考虑是否能用快排的方式排序，因为当元素数量达到一定程度，递归式的快排可能会导致栈溢出而崩，因此：
   通过__lg函数判断递归的深度

template <class Size>
inline Size __lg(Size n)
{
Size k;
for (k = 0; n > 1; n >>= 1) ++k;
return k;
}

数组指针可以当成随机迭代器用，应为它们具备相同的功能。其实string/vector的迭代器本身也是随机迭代器

int a[] = {1,3,5,1,2,5};
sort(a, a + sizeof(a) / sizeof(int));

根据左闭右开，a指向1，a + sizeof(a) / sizeof(int）指向5的下一个位置；

2.适配器

stack/queue默认是对deque的封装转化而来，当然也可以用vector和list去适配；priority_queue是对vector的适配器，不过vector上面使用堆算法。

五.仿函数

使用场景：

1. priority_queue,可以使用仿函数控制优先级
2. map/set,可以使用仿函数控制key的比较方式
3. unordered_map和unordered_set，可以使用仿函数控制key转换成整型，去取模映射
4. sort，可以使用仿函数控制数据的比较大小的方式，控制升序还是降序

仿函数能做的事，函数指针也可以，lamber表达式也可以。（lamber表达式底层实现其实也是仿函数）

六.空间配置器

空间配置器其实就是个内存池；举个栗子：*在以前的时候，我们每次用水都要重复跑去河里打水用，这很麻烦，就在家自己建立一个储水池，没水了就抽水到池子里，这个蓄水池就是相当于内存池，要用的时候就去池子取。*计算机也是，我们STL需要申请内存，内存被操作系统管理，每次申请都要向操作系统要，这就导致效率低；后面就搞出内存池这个东西，，直接去内存池取。（下面有专讲内存池这块）

这就是池化技术，还有线程池、连接池；缺点：不用的时候占用这些资源

1.为什么需要空间配置器

前面在模拟实现vector、list、map、unordered_map等容器时，所有需要空间的地方都是通过new申请的，虽然代码可以正常运行，但是有以下不足之处：

• 空间申请与释放需要用户自己管理，容易造成内存泄漏

• 频繁向系统申请小块内存块，容易造成内存碎片

• 频繁向系统申请小块内存，影响程序运行效率

• 直接使用malloc与new进行申请，每块空间前有额外空间浪费

• 申请空间失败怎么应对

• 代码结构比较混乱，代码复用率不高

• 未考虑线程安全问题

  因此需要设计一块高效的内存管理机制。

STL的空间配置器分为一级空间配置器和二级空间配置器：

• 一级空间配置器：就是malloc和free的封装，并增加了C++中set_new_handle思想。

template <int inst>
class __malloc_alloc_template
{
private:
	static void *oom_malloc(size_t);
public:
// 对malloc的封装
static void * allocate(size_t n)
{
// 申请空间成功，直接返回，失败交由oom_malloc处理
void *result = malloc(n);
	if (0 == result)
		result = oom_malloc(n);
	return result;
}
// 对free的封装
static void deallocate(void *p, size_t /* n */)
{ free(p);}
// 模拟set_new_handle
// 该函数的参数为函数指针，返回值类型也为函数指针
// void (* set_malloc_handler( void (*f)() ) )()
static void (* set_malloc_handler(void (*f)()))()
{
	void (* old)() = __malloc_alloc_oom_handler;
	__malloc_alloc_oom_handler = f;
	return(old);
}
};
// malloc申请空间失败时代用该函数
template <int inst>
void * __malloc_alloc_template<inst>::oom_malloc(size_t n)
{
	void (* my_malloc_handler)();
	void *result;
	for (;;)
	{
	// 检测用户是否设置空间不足应对措施，如果没有设置，抛异常，模式new的方式
		my_malloc_handler = __malloc_alloc_oom_handler;
	if (0 == my_malloc_handler)
	{
		__THROW_BAD_ALLOC;
	}
	// 如果设置，执行用户提供的空间不足应对措施
	(*my_malloc_handler)();
	// 继续申请空间，可能就会申请成功
	result = malloc(n);
	if (result)
		return(result);
	}
}
typedef __malloc_alloc_template<0> malloc_alloc;

oom_malloc:是个函数指针，申请内存失败以后，调用设置的回调函数

(*my_malloc_handler)();没有设置失败的处理函数，就直接抛异常，如果你设置了，就调用你设置的函数，相当于给予使用者一个处理错误的借口；

注意的事，默认情况下是没有设置这个函数指针句柄，也就是说默认情况下，一级空间配置器功能跟operetor new基本一样，失败了抛异常。

有人会问，那为什么不用operator new呢？因为这里它想搞一个自己实现的机制

• 二级空间配置器：专门负责处理小于128字节的小块内存。如何才能提升小块内存的申请与释放的方式呢？SGISTL采用了内存池的技术来提高申请空间的速度以及减少额外空间的浪费，采用哈希桶的方式来提高用户获取空间的速度与高效管理。

六.内存池

内存池就是：先申请一块比较大的内存块已做备用，当需要内存时，直接到内存池中去去，当池中空间不够时，再向内存中去取，当用户不用时，直接还回内存池即可。避免了频繁向系统申请小块内存所造成的效率低、内存碎片以及额外浪费的问题。

申请简单，释放难（解决方法：哈希桶）

1.SGI-STL中二级空间配置器设计

SGI-STL中的二级空间配置器使用了内存池技术，但没有采用链表的方式对用户已经归还的空间进行管理(因为用户申请空间时在查找合适的小块内存时效率比较低)，而是采用了哈希桶的方式进行管理。

那是否需要128桶个空间来管理用户已经归还的内存块呢？

答案是不需要，因为用户申请的空间基本都是4的整数倍，其他大小的空间几乎很少用到。因此：SGI-STL将用户申请的内存块向上对齐到了8的整数倍

申请内存X byte内存；看X对应映射位置的哈希桶中有没有内存对象，如果有，就直接取走，如果没有，就去内存池中切出一块20个对象内存，也就是X*20大小的内存，返回一个剩下19个挂到这个位置下面，下一次你再申请X byte大小内存，直接再这个位置下去取就可以。

释放X byte内存对象，找到X对应映射的位置，将内存对象挂到对应位置下面就可以

如果申请的不是8的整数倍怎么办？

向8整数倍对其就可以；比如申请1-8byte给你8byte，申请9-16byte给你是16byte

2. SGI-STL二级空间配置器之空间申请

1.前期准备

// 去掉代码中繁琐的部分
template <int inst>
class __default_alloc_template
{
private:
	enum { __ALIGN = 8 }; // 如果用户所需内存不是8的整数倍，向上对齐到8的整数倍
	enum { __MAX_BYTES = 128 }; // 大小内存块的分界线
	enum { __NFREELISTS = __MAX_BYTES / __ALIGN }; // 采用哈希桶保存小块内存时所需桶的个
	数
		// 如果用户所需内存块不是8的整数倍，向上对齐到8的整数倍
		static size_t ROUND_UP(size_t bytes)
	{
			return (((bytes)+__ALIGN - 1) & ~(__ALIGN - 1));
		}
private:
	// 用联合体来维护链表结构----同学们可以思考下此处为什么没有使用结构体
	union obj
	{
		union obj * free_list_link;
		char client_data[1]; /* The client sees this. */
	};
private:
	static obj * free_list[__NFREELISTS];
	// 哈希函数，根据用户提供字节数找到对应的桶号
	static size_t FREELIST_INDEX(size_t bytes)
	{
		return (((bytes)+__ALIGN - 1) / __ALIGN - 1);
	}
	// start_free与end_free用来标记内存池中大块内存的起始与末尾位置
	static char *start_free;
	static char *end_free;
	// 用来记录该空间配置器已经想系统索要了多少的内存块
	static size_t heap_size;
	// ...
};

2.申请空间

// 函数功能：向空间配置器索要空间
// 参数n: 用户所需空间字节数
// 返回值：返回空间的首地址
static void * allocate(size_t n)
{
	obj * __VOLATILE * my_free_list;
	obj * __RESTRICT result;
	// 检测用户所需空间释放超过128(即是否为小块内存)
	if (n > (size_t)__MAX_BYTES)
	{
		// 不是小块内存交由一级空间配置器处理
		return (malloc_alloc::allocate(n));
	}
	// 根据用户所需字节找到对应的桶号
	my_free_list = free_list + FREELIST_INDEX(n);
	result = *my_free_list;
	// 如果该桶中没有内存块时，向该桶中补充空间
	if (result == 0)
	{
		// 将n向上对齐到8的整数被，保证向桶中补充内存块时，内存块一定是8的整数倍
		void *r = refill(ROUND_UP(n));
		return r;
	}
	// 维护桶中剩余内存块的链式关系
	*my_free_list = result->free_list_link;
	return (result);
};

3.填充内存块

// 函数功能：向哈希桶中补充空间
// 参数n：小块内存字节数
// 返回值：首个小块内存的首地址
template <int inst>
void* __default_alloc_template<inst>::refill(size_t n)
{
	// 一次性向内存池索要20个n字节的小块内存
	int nobjs = 20;
	char * chunk = chunk_alloc(n, nobjs);
	obj ** my_free_list;
	obj *result;
	obj *current_obj, *next_obj;
	int i;
	// 如果只要了一块，直接返回给用户使用
	if (1 == nobjs)
		return(chunk);
	// 找到对应的桶号
	my_free_list = free_list + FREELIST_INDEX(n);
	// 将第一块返回值用户，其他块连接在对应的桶中
	// 注：此处代码逻辑比较简单，但标准库实现稍微有点复杂，同学们可以自己实现
	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->free_list_link = 0;
			break;
		}
		else
		{
			current_obj->free_list_link = next_obj;
		}
	}
	return(result);
}

七.扩展

内存碎片：

• 外碎片：大量小块借出去使用，还回来了大部分内存，但是它们不连续，碎片化，导致我们申请不出连续的大块内存，就是我有内存，但是碎片化了，导致申请连续的大块内存申请不出来

  

• 内碎片：你要5byte，给你8byte，有3byte空置，但是用不上，这种对象内存的碎片，就叫内碎片问题

内核中针对大量小块内存申请到碎片化的问题，使用一个slab分配器的东西解决，这个结构类似我们上面的二级空间配置器的哈希桶结构

内核中已经有slab分配器申请小块内存，为什么STL还要搞一个？

1. 内核时针对整个系统的所有程序的，并且每个去申请消耗是比较大的。
2. STL的容器需要全是小块内存，而且需大小比较集中，那么它自己设计一个，自己用，效率很高，也能顺便解决内存碎片问题

一个进程中有一个空间配置器，进程中所有的容器需要内存，都找的这个空间配置器