网站导航
> 文章列表 > 【C++】STL之空间配置器 | STL总结

【C++】STL之空间配置器 | STL总结

网友: 文章列表 2024-03-21 15:45:49

【C++】STL之空间配置器 | STL总结

​🌠 作者：@阿亮joy.
🎆专栏：《吃透西嘎嘎》
🎇 座右铭：每个优秀的人都有一段沉默的时光，那段时光是付出了很多努力却得不到结果的日子，我们把它叫做扎根
在这里插入图片描述

目录

    • 👉什么是空间配置器👈
    • 👉为什么需要空间配置器👈
    • 👉SGI-STL空间配置器实现原理👈
    • 👉空间配置器的优势👈
    • 👉空间配置器与容器结合👈
    • 👉STL总结👈
    • 👉总结👈

👉什么是空间配置器👈

空间配置器，顾名思义就是为各个容器高效的管理空间（空间的申请与回收）的，在默默地工作。虽然在常规使用 STL 时，可能用不到它，但站在学习研究的角度，学习它的实现原理对我们有很大的帮助。注：空间配置器是内存池。

在这里插入图片描述
直接向堆区申请内存的有 Windows 下的 VirtualAlloc 和 Linux 下的 brk，这个一般不符合我们的需求。而 malloc 是向堆区申请内存的函数，也本质是一个内存池，可用于整个程序的内存管理。STL 的空间配置器也是内存池，其是专门服务 STL 容器的内存管理，以提高效率。

👉为什么需要空间配置器👈

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

  • 空间申请与释放需要用户自己管理，容易造成内存泄漏
  • 频繁向系统申请小块内存块，容易造成内存碎片
  • 频繁向系统申请小块内存，影响程序运行效率
  • 直接使用 malloc 与 new 进行申请，每块空间前有额外空间浪费
  • 申请空间失败怎么应对
  • 代码结构比较混乱，代码复用率不高
  • 未考虑线程安全问题

👉SGI-STL空间配置器实现原理👈

以上提到的几点不足之处，最主要还是：频繁向系统申请小块内存造成的。那什么才算是小块内存？SGI-STL 以 128 作为小块内存与大块内存的分界线，将空间配置器其分为两级结构，一级空间配置器处理大块内存，二级空间配置器处理小块内存。

在这里插入图片描述
一级空间配置器

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
二级空间配置器

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
如果申请的内存大小小于 128 字节时，就走二级空间配置器。首先，看看该大小的内存对应的桶中有没有内存，如果有就直接返回；如果没有，就去调用 malloc 申请大块内存，并将大块内存切分成小块内存头插到对应的桶中。如果多次申请该大小的内存时，就能够提高效率了。

free_list 的桶和哈希桶的区别：哈希桶挂的是节点，这些节点都是一样的；free_list 的桶挂的是内存，不同的桶挂的内存大小是不一样的。因为一个指针是4个字节 或 8 个字节，而我们只需要让内存的头 4 个或 8 个字节指向下一个内存的地址，最后一块内存的头 4 个或 8 个内存指向空。

在这里插入图片描述
在这里插入图片描述

假设现在要申请 40 个字节，发现桶没有，就去看大块内存够不够 40 个字节。假设没有且再去用 malloc 申请大块内存也失败了，这时候就会去看后面的桶有没有比 40 大的内存，如果有，就将该内存切分成 40 大小的内存和更小的内存，并将该内存挂在对应的桶上。如果还是没有，那么就抛异常。

在这里插入图片描述
STL 的空间配置器是专门服务容器的，假设 list 的一个节点大小为 12 个字节，set 的一个节点为 16 字节。假设 list 尾插了 15 次，那么它就使用了 15 个 16 字节大小的内存（大块内存可以被切分成 20 个 所需空间的小内存）。那么现在还是剩下 5 个 16 字节大小的内存，此时 set 开始 insert，那么这 5 个内存就可以被 set 使用。假设 set insert 3 次后，list 析构了并将其内存挂回了 free_list 的桶上，那么这些内存也就可以被 set 所使用。这也是空间配置器提高效率的做法。

一个进程里面应该只有一个空间配置器，所以空间配置器可以设计成单例模式的类。SGI 的 STL 空间配置器是通过静态成员来间接实现单例模式的。

👉空间配置器的优势👈

  1. 频繁申请小块内存时，效率高（memory 头文件中的 allocator 就是 STL 的空间配置器，可以和 malloc 进行效率对比）。
  2. 一定程度上缓解了内存碎片的问题，内存碎片分为外碎片和内碎片
  • 外碎片问题是由频繁向系统申请小块内存造成的。频繁向系统小块内存会造成有足够的内存，但是不连续，无法申请大块的内存。
  • 内碎片问题是实际申请到的内存多于所需的内存，而多出来的内存用户也无法使用。内存块按一定的对齐规则挂起来管理，就会导致内碎片问题。比如：list 的一个节点需要 12 个字节，系统给了用户 16 个字节，多出来的 4 个字节用户也无法使用。内存池一般都会有内碎片问题，内碎片问题不是很严重。

malloc 和 内存池的对比

注：一下实现的定长内存池是高并发内存池项目中的组件，以后会详细讲解！定长内存池的空间是不释放的，因为大块内存已经被切分了好多次，无法正确释放。但是只要进程是正常结束的，也不要造成内存泄漏问题。进程正常结束，操作系统会回收内存。

在这里插入图片描述

// ObjectPool是针对某一类对象的定长内存池
#pragma once#include <iostream>
#include <vector>
#include <time.h>
// 工程项目中不要将std整个命名空间展开,避免命名污染
using std::cout;
using std::endl;// 操作系统的控制,如果是Windows系统则包含windows.h
// 如果是Linux系统,则包含brk系统调用对应的头文件
#ifdef _WIN32
#include <windows.h>
#else
// 
#endif// 因为要实现的高并发内存池要使用到定长
// 内存池,所以就不采用下方的实现方式了
// 定长内存池
//template <size_t N>
//class ObjectPool
//{};// 直接去堆上按页申请空间(Windows的VirtualAlloc和Linux的brk)
// kpage是页数,假设一页是8KB
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32void* ptr = VirtualAlloc(0, kpage << 13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else// linux下brk mmap等
#endifif (ptr == nullptr)throw std::bad_alloc();return ptr;
}template <class T>
class ObjectPool
{
public:T* New(){T* obj = nullptr;// 优先把还回来的内存重复使用if (_freeList){// 将_freeList强转为void,对其解引用即可// 得到四个字节或八个字节的地址void* next = *((void**)_freeList);obj = (T*)_freeList;_freeList = next;	// 指向下一块内存}else{// 剩余内存不够一个对象的大小时,则再申请大块内存if (_leftBytes < sizeof(T)){_leftBytes = 128 * 1024;// 使用VirtualAlloc是为了完全和malloc脱离//_memory = (char*)malloc(_leftBytes);// 假设一页是8KB,右移13位即可算出页数_memory = (char*)SystemAlloc(_leftBytes >> 13);if (_memory == nullptr){throw std::bad_alloc();}}obj = (T*)_memory;// 保证申请的内存大小至少是一个指针的大小// 以保证能够存下一块内存的起始地址size_t objSize = sizeof(T) < sizeof(void*) ? sizeof(void*) : sizeof(T);_memory += objSize;_leftBytes -= objSize;}// 定位new,显式调用T的构造函数初始化new(obj) T;return obj;}void Delete(T* obj){// 显示调用T的析构函数清理对象obj->~T();// 将_freeList强转为void,对其解引用即可// 得到四个字节或八个字节的地址// 头插*(void**)obj = _freeList;_freeList = obj;}private:// 使用char*比较方便,因为其加一就是跳过一个字节char* _memory = nullptr;  // 指向大块内存的指针size_t _leftBytes = 0;  // 大块内存在切分过程中剩余字节数void* _freeList = nullptr;  // 自由链表的头指针,自由链表中存的是返回来的内存
};struct TreeNode
{int _val;TreeNode* _left;TreeNode* _right;TreeNode():_val(0), _left(nullptr), _right(nullptr){}
};void ObjectPoolTest()
{// 申请释放的轮次const size_t Rounds = 5;// 每轮申请释放多少次const size_t N = 1000000;std::vector<TreeNode*> v1;v1.reserve(N);size_t begin1 = clock();for (size_t j = 0; j < Rounds; ++j){for (int i = 0; i < N; ++i){v1.push_back(new TreeNode);}for (int i = 0; i < N; ++i){delete v1[i];}v1.clear();}size_t end1 = clock();std::vector<TreeNode*> v2;v2.reserve(N);ObjectPool<TreeNode> Pool;size_t begin2 = clock();for (size_t j = 0; j < Rounds; ++j){for (int i = 0; i < N; ++i){v2.push_back(Pool.New());}for (int i = 0; i < N; ++i){Pool.Delete(v2[i]);}v2.clear();}size_t end2 = clock();cout << "new cost time:" << end1 - begin1 << endl;cout << "object pool cost time:" << end2 - begin2 << endl;
}

在这里插入图片描述
通过上图，我们很明显就能够看到 malloc 和内存池在效率上的差别。

👉空间配置器与容器结合👈

在这里插入图片描述
如果你觉得 STL 的空间配置器写的不好，你就可以自己写一个内存池，该内存池需要有 allocate 和 deallocate 接口，再将你写的内存池显式地传给类模板即可。

👉STL总结👈

  • 从使用的角度来看，我们只需要关注 STL 的容器，算法和迭代器。
  • 而从底层实现的角度来看，我们需要关注 STL 的六大组件（容器、迭代器、算法、仿函数、适配器、空间配置器），理解六大组件的内在联系。六大组件的内在联系如下图：

在这里插入图片描述

👉总结👈

本篇博客主要讲解了 STL 的空间配置器、定长内存池与 malloc 的效率对比以及 STL 六大组件内在联系的总结等等。那么以上就是本篇博客的全部内容了，如果大家觉得有收获的话，可以点个三连支持一下！谢谢大家！💖💝❣️

网络标签：

相关问题