跳到主要内容

STL组成组件

STL是C++标准库中的一个重要部分，提供了一组灵活通用的数据结构，核心是模板类。 接下来是STL的主要组件及其功能简介。

1. 容器​

容器是用来存储和管理一组数据的对象。不同的容器适用于不同类型的数据存储需求。

可理解为各种形式实现的存储结构

顺序容器​

  • vector: 动态数组，支持快速随机访问和尾部插入/删除操作。
  • deque: 双端队列，支持快速随机访问和头尾插入/删除操作。
  • list: 双向链表，支持快速插入/删除操作，不支持随机访问。
  • array: 固定大小的数组，支持快速随机访问，但大小在编译时确定。
  • forward_list: 单向链表，只支持单向遍历和快速插入/删除操作。

关联容器​

  • set: 集合，存储唯一元素，自动排序，支持快速查找、插入、删除操作。
  • map: 映射（字典），存储键值对，按键自动排序，支持快速查找、插入、删除操作。
  • multiset: 允许重复元素的集合，自动排序。
  • multimap: 允许重复键的映射，自动排序。

无序关联容器​

  • unordered_set: 无序集合，使用哈希表实现，支持快速查找、插入、删除操作。
  • unordered_map: 无序映射，使用哈希表实现。
  • unordered_multiset: 无序多重集合，允许重复元素。
  • unordered_multimap: 无序多重映射，允许重复键。

2. 迭代器​

迭代器是用于遍历容器中的元素的指针类对象，为容器提供了统一的访问接口。

可理解为该存储结构的头指针，哨兵等用来访问数组的东西。所以例如动态数组Vector，在扩容后由于扩容后的数组与原数组无关，会导致原迭代器失效。

  • 输入迭代器（Input Iterator）: 只读访问，单向遍历。
  • 输出迭代器（Output Iterator）: 只写访问，单向遍历。
  • 前向迭代器（Forward Iterator）: 读写访问，单向遍历。
  • 双向迭代器（Bidirectional Iterator）: 读写访问，支持双向遍历。
  • 随机访问迭代器（Random Access Iterator）: 读写访问，支持双向遍历和随机访问。

3. 算法​

STL提供了一系列通用算法用于操作容器中的数据，这些算法大多是以函数模板的形式提供的。

可理解为执行部分操作的方法，即算法，例如数组的sort本质是快排。

  • 非修改算法: 如for_each、find、count等，这些算法不修改容器内容。
  • 修改算法: 如copy、swap、replace等，这些算法会改变容器的内容。
  • 排序算法: 如sort、partial_sort、stable_sort等，用于排序容器中的元素。
  • 搜索算法: 如binary_search、lower_bound、upper_bound等，用于在有序容器中查找元素。
  • 数值算法: 如accumulate、inner_product、adjacent_difference等，用于数值计算。

4. 函数对象​

函数对象是重载了operator()的对象，可以像函数一样调用。STL中的许多算法可以接受函数对象作为参数，这些对象可以封装复杂的操作。

可理解为对该数据结构封装，给出某个操作。

  • 标准函数对象: 如std::plus、std::minus、std::greater、std::less等，封装了基本的算术和比较操作。
  • 自定义函数对象: 用户可以定义自己的函数对象以实现特定的操作。

5. 适配器​

适配器是一类修改容器、迭代器或函数行为的组件。

可以理解为对封装的内容进行二次封装。

  • 容器适配器: 如stack（栈）、queue（队列）、priority_queue（优先队列），它们是对其他容器的包装，提供特定的数据访问方式。
  • 迭代器适配器: 如reverse_iterator、back_insert_iterator、front_insert_iterator、insert_iterator等，用于改变迭代器的行为。
  • 函数适配器: 如std::bind、std::mem_fn、std::function，用于调整或封装函数调用方式。

6. 空间配置器​

空间配置器是STL中负责内存管理的组件。它们定义了内存的分配与释放策略，以及对象的构造与析构方式。默认的空间配置器是std::allocator，它提供了针对动态内存分配的一般性实现。用户也可以自定义自己的空间配置器，以满足特定的性能需求或内存管理策略。

可理解为负责内存管理的机制或策略。

主要功能

  • 内存分配: 负责分配指定大小的原始内存块（通常未初始化）。
  • 内存释放: 释放之前分配的内存块。
  • 对象构造与析构: 在已分配的内存上构造对象，并在对象生命周期结束时析构对象。

自定义空间配置器 用户可以通过实现std::allocator的接口或继承自其基类，来自定义内存分配策略。比如，在嵌入式系统中，可能需要自定义空间配置器以控制内存的精确使用，减少碎片化。