STL笔记1

简介: STL笔记

顺序容器有vector、list、deque。
关联容器有map、set。
容器类自动申请和释放内存,无需new和delete操作。
但是需要连接STL各个容器的内存管理

STL六大组件:
容器,算法,迭代器,仿函数、适配器和空间配置器
容器:容纳一组元素的对象
迭代器:提供一种访问容器中每一个元素的方法
适配器:用来修饰容器,比如queue和stack,底层借助了deque。
空间适配器:负责空间配置和管理

空间配置器:
对象构造前的空间配置和对象析构后的空间释放,由负责。
设计哲学如下:
先system heap要求空间
考虑多线程状态
考虑内存不足时的应变措施
考虑碎片问题

对于碎片问题,有双层及配置器:
第一级直接使用allocate()调用malloc()、deallocate()调用free(),使用类似new_handler机制解决内存不足(抛出异常),配置无法满足的问题(如果在申请动态内存时找不到足够大的内存块,malloc 和new 将返回NULL 指针,宣告内存申请失败)。

第二级视情况使用不同的策略,当配置区块大于128bytes时,调用第一级配置器,当配置区块小于128bytes时,采用内存池的整理方式:配置器维护16个(128/8)自由链表,负责16种小型区块的此配置能力。内存池以malloc配置而得,如果内存不足转第一级配置器处理。

1、第一级配置器详解

2、第二级空间配置器详解
  第二级空间配置器实际上是一个内存池,维护了16个自由链表。自由链表是一个指针数组,有点类似与hash桶,它的数组大小为16,每个数组元素代表所挂的区块大小,比如free list[0]代表下面挂的是8bytes的区块,free list[1]代表下面挂的是16bytes的区块…….依次类推,直到free _ list[15]代表下面挂的是128bytes的区块。

3、空间配置器存在的问题
自由链表所挂区块都是8的整数倍,因此当我们需要非8倍数的区块,往往会导致浪费。

由于配置器的所有方法,成员都是静态的,那么他们就是存放在静态区。释放时机就是程序结束,这样子会导致自由链表一直占用内存,自己进程可以用,其他进程却用不了。

各种容器的特点和适用情况:
vector:可变大小的数组,支持快速随机访问,在尾部之外的位置插入或删除元素会较慢。
deque:双端队列,支持快速随机访问,在头尾位置插入删除速度快。
list:双向链表,只支持双向顺序访问,在list任何位置插入/删除速度都很快。
forward_list:单向链表,只支持单向顺序访问
array:固定大小的数组支持随机访问,不能添加或者删除元素。
string:和vector相似,随机访问快,在尾位置插入/删除元素快。

目录
相关文章
|
存储 算法 搜索推荐
【C++ STL基础入门】初识STL
【C++ STL基础入门】初识STL
145 0
|
7月前
|
存储 编译器 C++
STL笔记
STL笔记
|
5月前
|
存储 算法 数据处理
|
5月前
|
存储 算法 数据处理
【C++】STL简介
**STL是C++标准库的关键部分,源于Alexander Stepanov的泛型编程研究。它提供了数据结构(如vector、list)和算法,是高效、通用的软件框架。STL始于惠普,后由SGI发展,现已成为C++1998标准的一部分并不断进化。它包括容器、迭代器、算法、仿函数、配接器和分配器六大组件,带来高效性、通用性和可扩展性,但也存在性能开销和学习难度。学习STL涉及理解底层数据结构、用法、实现和实践。推荐[cplusplus.com](https://cplusplus.com)作为学习资源。**
|
7月前
|
算法 安全 Linux
【C++】STL简介(了解)
【C++】STL简介(了解)
|
7月前
|
存储 C++ 索引
C++的STL学习笔记
C++的STL学习笔记
106 0
|
7月前
|
算法 安全 Linux
【C++】—— STL简介(了解)
【C++】—— STL简介(了解)
|
7月前
|
算法 Linux C语言
(C++)STL简介
(C++)STL简介
57 0
|
存储 C++
一些关于STL的笔记
一些关于STL的笔记
|
存储 算法 安全
初识STL&STL简介
初识STL&STL简介
124 0