STL知识总结

1. STL简介

STL（Standard Template Library，标准模板库）是 C++ 标准库的一部分，提供了一组通用的模板类和函数，用于实现常见的数据结构和算法。STL 主要由以下几个核心组件组成：

2. 容器（Containers）

容器是 STL 中存储数据的类模板。它们提供了一种统一的数据存储方式，允许开发者根据需求选择不同类型的容器。

(1) 容器类型

STL 中的容器大体分为以下几类：

序列容器（Sequence Containers）

序列容器保存元素的顺序：即元素在容器中的排列是按照插入的顺序进行的。

• vector：动态数组，支持快速随机访问，但插入和删除操作较慢。
• deque：双端队列，支持从两端进行插入和删除，访问速度相对较快。
• list：双向链表，支持高效的插入和删除操作，但不支持随机访问。
• array：固定大小的数组（C++11 引入），大小在编译时已知。
• forward_list：单向链表，内存更为紧凑，提供较快的插入和删除操作。

1.2 关联容器（Associative Containers）

关联容器按照一定规则（如键值对）来存储数据，通常是有序的，并允许根据键快速查找对应的值。

• set：存储唯一元素，按照元素的顺序进行排序。
• map：存储键值对，键是唯一的，按键进行排序。
• multiset：与 set 相似，但允许多个相同的元素。
• multimap：与 map 相似，但允许多个相同的键值对。

1.3 无序容器（Unordered Containers） （C++11 引入）

无序容器允许元素的存储不进行排序，通过哈希表实现快速的查找、插入和删除操作。

• unordered_set：存储唯一元素，不保证元素的顺序。
• unordered_map：存储键值对，不保证元素的顺序。
• unordered_multiset：允许多个相同的元素，顺序不保证。
• unordered_multimap：允许多个相同的键值对，顺序不保证。

(2) Vector：动态数组

vector是一个动态数组容器，具有如下核心成员变量：

三个迭代器：

• _start：数据的开始。
• _finish：数据的逻辑末尾（即当前元素的个数）。
• _end_of_storage：分配的物理空间末尾。

vector的两个概念：

• size：当前元素个数，_finish - _start
• capacity：当前最大可容纳元素个数，_end_of_storage - _start

内存分配

底层通过 std::allocator<T> 进行分配，分为两个阶段：

1. 分配原始内存：调用 allocate(n) 分配原始未构造的 T 类型对象内存；
2. 对象构造：调用 construct(p, val) 构造对象；
3. 析构与释放：调用 destroy(p) 和 deallocate(p, n)。

扩容策略

当size == capacity时，再次插入元素会触发扩容，常见实现为2倍扩容策略。

扩容步骤：

1. 申请一块新内存；
2. 将原内存的数据搬迁（调用移动/拷贝构造函数）；
3. 析构旧元素，释放旧内存；
4. 更新指针 _start, _finish, _end_of_storage。

这是一项线性摊销复杂度为 O(1) 的操作，因为多次插入中只有一小部分涉及搬迁。

特性

(3) List：双向链表

List是C++ STL中的一个双向链表（Doubly Linked List）容器，适用于频繁的插入和删除操作，但不适合随机访问。

特点：

• List的内存布局是分散不连续的。
• 任意位置插入删除效率为O(1)。
• 不支持随机访问，访问第 n 个元素必须从头或尾开始遍历，时间复杂度为 O(n)。
• 插入删除元素时，其它节点的迭代器不失效。
• 每个节点通过内存分配器动态分配内存，不像vector使用连续数组。

struct Node 
{
    T data;
    Node* prev;
    Node* next;
};

每个节点都包含：

• 数据 data
• 指向前一个节点的指针 prev
• 指向下一个节点的指针 next

List通常有两个指针成员：

• head：指向链表的第一个元素
• tail：指向链表的最后一个元素（有时也用一个 dummy 节点作为哨兵节点）

(4) Deque：双向队列

3. 算法（Algorithms）

STL 提供了很多算法，用来在容器中执行常见的操作。算法是独立于容器的，它们通过迭代器（iterator）与容器中的数据进行交互。常见的算法包括：

• 排序算法：如 sort、stable_sort。
• 查找算法：如 find、binary_search。
• 修改算法：如 reverse、rotate、swap。
• 拷贝算法：如 copy、move。
• 集合操作：如 set_union、set_intersection。
• 数值算法：如 accumulate、inner_product。

所有的 STL 算法都是以迭代器为基础的，通常采用类似如下的语法：

std::sort(container.begin(), container.end());

4. 函数对象（Function Objects）

函数对象（也称为“仿函数”）是实现了 operator() 的类对象。它们可以像函数一样被调用。STL 中的许多算法使用了函数对象来提供更灵活的操作方式。例如：

• std::less<T>：一个函数对象，用于判断某个元素是否小于另一个元素，常用于排序。
• std::greater<T>：一个函数对象，用于判断某个元素是否大于另一个元素。
• std::equal_to<T>：用于判断两个元素是否相等。

函数对象的优点是它们比普通的函数指针更高效（可以在构造时绑定一些常量或状态），并且可以像对象一样被传递和存储。

5. 迭代器（Iterators）

迭代器是类模板，它封装了指针并重载了运算符，使得它可以遍历部分或全部容器元素对象。

迭代器返回的是对象的引用，因此不能直接访问，需要用*解引用才能访问。

迭代器是 STL 的关键部分，它们提供了一种统一的方式来访问容器中的元素。迭代器就像指针，能够让你遍历容器中的数据。STL 提供了以下几种迭代器类型：

• input_iterator：能够读取元素的迭代器。
• output_iterator：能够写入元素的迭代器。
• forward_iterator：能向前遍历的迭代器。
• bidirectional_iterator：能向前和向后遍历的迭代器。
• random_access_iterator：能进行任意位置随机访问的迭代器。

常见的迭代器操作包括：

• begin()：返回指向容器第一个元素的迭代器。
• end()：返回指向容器最后一个元素之后位置的迭代器。
• advance()：将迭代器向前或向后移动。
• operator*：解引用迭代器，获取元素。
• operator++：迭代器递增。

6. 适配器（Adapters）

适配器是用来修改容器的接口的工具。适配器提供了一些新功能，但不改变容器的底层实现。STL 中主要有三种适配器：

• 容器适配器（Container Adapters）：
  • stack：栈，基于其他容器（如 deque 或 vector）实现的先进后出（LIFO）结构。
  • queue：队列，基于其他容器（如 deque）实现的先进先出（FIFO）结构。
  • priority_queue：优先队列，基于其他容器（如 vector）实现的按优先级排序的队列。
• 迭代器适配器（Iterator Adapters）：
  • reverse_iterator：反向迭代器，使得容器可以从尾到头遍历。
  • insert_iterator：插入迭代器，用于将元素插入容器的特定位置。
  • stream_iterator：输入输出流迭代器，用于将数据流与容器结合。
• 函数适配器（Function Adapters）：
  • bind：将一个函数对象与某些参数绑定，生成一个新的函数对象。
  • function：可调用对象封装器，类似于函数指针，但可以存储任何类型的可调用对象。

7. 内存分配器（Allocator）

(1) 介绍

Allocator 是一个类模板，是一个内存管理策略类，用于定义容器如何申请和释放内存。

标准容器（如 vector、list、map 等）都支持以模板参数的形式传入allocator类型，默认使用的是 std::allocator<T>。

STL 默认使用 std::allocator，它为容器提供内存分配的功能。分配器提供了以下功能：

• 内存分配：为容器分配内存。
• 内存释放：释放容器占用的内存。
• 构造和析构：为对象分配内存时进行对象的构造，为对象释放内存时调用析构函数。

通常情况下，开发者不会直接与分配器交互，除非有特殊的内存管理需求。

(2) 举个例子

在这个过程当中，发生了什么？

std::vector<int> nums(5);

第一步：调用allocator分配内存，返回裸内存指针（int*）。

std::allocator<int> allocator;
T* data = allocator.allocate(5);

std::allocator<T>::allocate(n)的底层实现大致如下：

T* allocate(size_t n) 
{
    if (n > max_size()) throw std::bad_alloc();
    return static_cast<T*>(::operator new(n * sizeof(T)));
}

第二步：构造对象

C++11 之后，这种构造一般会由std::allocator_traits<Allocator>::construct()代理。

for (size_t i = 0; i < 5; ++i) 
{
    allocator.construct(data + i, 0); // 构造 int，值为 0（默认值）
}

销毁

for (size_t i = 0; i < 5; ++i)
{
    allocator.destroy(data + i); // 调用析构函数（对 int 无实际作用）
}

allocator.deallocate(data, 5);   // 释放内存

(3) 两级分配器

不同大小的对象，采用不同的分配策略，从而在“效率”与“灵活性”之间取得平衡。

小于128B的内存申请：采用内存池技术快速分配，使用链表管理。

大于128B的内存申请：使用一级分配器，malloc() / realloc() / free() 进行空间分配

(4) 内存池技术

一个经典的简单内存池实现：

template <bool threads, int inst>
class __default_alloc_template 
{
    // 小对象内存池
    static char* start_free;  // 空闲内存开始
    static char* end_free;    // 空闲内存结束
    static size_t heap_size;

    // 自由链表（freelist），每种 block size 有一条链表
    static obj* free_list[NFREELISTS]; // 例如 16个，每8字节为一个节点

    static void* refill(size_t n);     // 不够时补充
    static char* chunk_alloc(size_t size, int& nobjs); // 向系统申请 chunk
};

（7）总结

STL 由多个组件组成，每个组件负责不同的功能。它们共同构成了一个强大的模板库，使得开发者能够更加高效地编写代码，减少了常见数据结构和算法的实现工作。以下是 STL 的主要组件总结：

• 容器（Containers）：存储数据的类模板。
• 算法（Algorithms）：处理容器数据的常用操作。
• 迭代器（Iterators）：统一的访问容器数据的方式。
• 函数对象（Function Objects）：可调用的对象，通常用于算法。
• 分配器（Allocators）：负责内存分配和管理。
• 适配器（Adapters）：修改容器和迭代器接口的工具。

这些组件共同为 C++ 提供了灵活、高效、可扩展的工具，使得我们在处理常见任务时能够专注于算法和业务逻辑，而不必过多关注底层的实现。

找不同

（1）Vector和List的区别

• vector底层是连续结构；list底层是非连续结构
• vector支持随机访问；list不支持随机访问
• vector迭代器是原生指针；list迭代器是封装结点的一个类
• vector在插入和删除时可能会导致迭代器失效；list在删除的时候会导致当前迭代器指向的结点失效
• vector不容易造成内存碎片，空间利用率高；list容易造成内存碎片，空间利用率低
• vector在非尾插，删除的时间复杂度为O(n)，list在任何地方插入和删除的时间复杂度都为O(1)

使用场景：

• vecotr需要高效存储，支持随机访问，不关心插入删除效率；list大量插入和删除操作，不关心随机访问

（2）map和multimap的区别