rangersly/material
1
1
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity
material/program/c_cpp/STL/containers.md

8.6 KiB
Raw Permalink Blame History

STL 容器

index

概念

函数符概念

其实就是重载了()的伪函数

  • 生成器:无参数
  • 一元函数:一个参数
  • 二元函数:两个参数
  • 谓词:返回bool的一元函数
  • 二元谓词:返回bool的二元函数

通性

  • begin() 和 end() 用于获取容器的迭代器,指向容器的第一个元素和最后一个元素的“后继”
  • rbegin() 和 rend() 用于获取容器的反向迭代器，指向容器的最后一个元素和第一个元素的“前驱”位置
  • size() 返回容器中元素的数量
  • empty() 如果容器为空，返回true；否则返回false
  • max_size() 返回容器可能存储的最大元素数量
  • clear() 清空容器中的所有元素，但不释放内存
  • swap() 交换两个容器的内容
  • data() 仅适用于序列容器 返回指向容器底层存储的指针
    • 提供对容器底层数据的直接访问
    • 适用于需要与C语言风格的API交互的场景
  • front() 和 back() 仅适用于序列容器 返回容器的第一个元素和最后一个元素的引用
  • operator[] 和 at() 仅适用于序列容器 访问容器中的特定元素
    • at() 进行边界检查，如果索引超出范围，会抛出std::out_of_range异常

序列容器

存储元素的顺序与插入顺序一致

vector

  1. 定义和初始化

std::vector<int> vec1; // 定义一个空的 vector
std::vector<int> vec2 = {1, 2, 3, 4, 5}; // 使用初始化列表初始化
std::vector<int> vec3(10, 0); // 10个元素，初始值为0
std::vector<int> vec4(vec2); // 拷贝构造 std::vector<int> vec5(std::move(vec2)); // 移动构造

  1. 元素访问

支持序列容器的大部分访问方法

  1. 修改容器

push_back() 在容器末尾添加一个元素 pop_back() 删除容器末尾的元素
insert() 在指定位置插入一个或多个元素 erase() 删除指定位置的元素

  1. 容量和大小

capacity() 返回容器当前分配的内存容量（以元素数量计） reserve() 预分配内存，减少动态扩展的次数 shrink_to_fit() 收缩内存，释放多余空间

使用技巧

  1. 预分配内存

如果知道容器将存储大量元素，可以使用 reserve() 预分配内存，以减少动态扩展的次数

  1. 使用 std::move()

vec2.push_back(std::move(vec1[0])); // 将vec1的第一个元素移动到vec2

  1. 使用vector的bool值特性

std::vector<bool> 是一个特化版本，它使用位存储来优化空间占用，但可能会牺牲某些操作的性能

  1. 使用 std::vector 的指针特性

如果需要存储动态分配的对象，可以使用 std::vector<std::unique_ptr<T>> 或 std::vector<std::shared_ptr<T>>

vector 的 capacity 和 size 属性区别

size 是当前 vector 容器真实占用的大小，也就是容器当前拥有多少个容器。

capacity 是指在发生 realloc 前能允许的最大元素数，即预分配的内存空间。

使用 resize() 容器内的对象内存空间是真正存在的。

使用 reserve() 仅仅只是修改了 capacity 的值，容器内的对象并没有真实的内存空间(空间是"野"的)。

deque

  1. 插入和删除
  • push_back() 和 pop_back()：尾部操作
  • push_front() 和 pop_front()：头部操作
  • insert() 和 erase()：在任意位置插入或删除
  1. 大小操作
  • resize()：调整容器大小

使用技巧

高效头部操作：deque 是处理头部和尾部频繁插入删除的理想选择 随机访问优化：虽然 deque 的内存不连续，但通过下标访问效率较高 排序：由于支持随机访问，可以使用 std::sort 对 deque 进行排序 迭代器失效：在添加或删除元素后，迭代器可能失效，需要重新获取

注意事项

内存不连续：deque 的元素可能分散在多个内存块中，但通过下标或迭代器访问不会受到影响 迭代器失效：在容器大小发生变化时（如插入或删除元素），迭代器可能会失效 性能权衡：虽然 deque 在头部和尾部操作高效，但在中间插入或删除元素的性能不如 list

相比vector的优势

头部操作高效：deque 在头部插入和删除操作的时间复杂度为 O(1)，而 vector 为 O(n)。 动态变化灵活：deque 的分块内存分配使其更灵活，性能损耗更小,且内存不足时不用搬运所有元素 随机访问性能接近：虽然 deque 的随机访问效率略低于 vector，但差距不大

list

  1. 特点
  • 双向链表结构：每个元素包含指向前后元素的指针，支持双向遍历
  • 高效插入和删除：在任意位置插入或删除元素的时间复杂度为 O(1)，前提是已知位置
  • 不支持随机访问：无法通过索引直接访问元素，只能通过迭代器遍历
  • 稳定的迭代器：插入和删除操作不会使迭代器失效，除非删除了迭代器所指向的元素
  1. 插入和删除
  • push_back() 和 pop_back()：尾部操作
  • push_front() 和 pop_front()：头部操作
  • insert() 和 erase()：在任意位置插入或删除
  1. 其他
  • resize()：调整容器大小
  • swap()：交换两个 list 的内容
  • splice()：将一个 list 的元素插入到另一个 list 的指定位置
  • sort()、merge()、reverse()：排序、合并和反转

注意事项

不支持随机访问：无法通过索引访问元素，只能通过迭代器 内存开销：每个元素存储额外的指针，内存开销较大 缓存局部性差：元素不连续存储，遍历性能不如 std::vector 适用场景有限：只有在需要频繁中间插入和删除时才适合使用

关联容器

存储元素时会自动排序，通常基于键值对

set

基于红黑树实现 适用于需要去重、排序和高效查找的场景

  1. 特点
  • 元素唯一性：容器中不允许存储重复元素
  • 自动排序：元素会根据指定的比较规则自动排序，默认为升序
  • 高效查找：插入、删除和查找操作的时间复杂度均为 O(log n)
  1. 构造与初始化
  • 默认构造
  • 初始化列表
  • 拷贝构造
  • 自定义比较规则
struct Compare {
    bool operator()(int a, int b) const {
        return a > b;  // 降序排序
    }
};
  1. 常用操作
  • 插入元素 s1.insert(5);
  • 删除元素 s1.erase(3); // 删除值为 3 的元素
  • 查找元素 s1.find(4); // 返回指向元素的迭代器，未找到时返回 s1.end()
  • 统计元素 int count = s1.count(4);
  • 范围查询
auto lower = s1.lower_bound(3);  // 返回第一个 >= 3 的元素的迭代器
auto upper = s1.upper_bound(5);  // 返回第一个 > 5 的元素的迭代器
  1. 高级用法
  • 自定义排序规则:使用仿函数或 std::greater 可以改变排序规则
  • 存储复杂数据类型:可以存储 std::pair 或自定义结构体，通过自定义比较函数排序
  • 范围删除 s1.erase(s1.lower_bound(10), s1.upper_bound(50)); // 删除值在 [10, 50) 范围内的所有元素

注意事项

修改元素：无法直接修改容器中的元素值，需要先删除再插入 性能开销：由于自动排序的特性，插入和删除操作比无序容器慢 迭代器失效：插入操作不会使迭代器失效，但删除操作会使指向被删除元素的迭代器失效

map

用于存储键值对（key-value pairs），并根据键自动排序

  1. 特点
  • 键的唯一性：每个键在 map 中是唯一的，不允许重复
  • 自动排序：容器会根据键的默认比较规则（通常是 < 运算符）自动排序
  • 高效操作：插入、删除和查找操作的时间复杂度均为 O(log n)，其中 n 是容器中元素的数量
  1. 常用操作
  • 插入元素:map1.insert({4, "four"});或map1[5] = "five"; // 如果键不存在，则插入新键值对；如果键存在，则更新值
  • 查找元素:map1.find(3); 或者使用 operator[] 直接访问键对应的值
  • 删除元素:map1.erase(3); // 删除键为 3 的元素。

无序容器

存储元素时不排序，基于哈希表实现

预定义函数符

  • + plus

  • - minus

  • * multiplies

  • / divides

  • % modulus

  • == equal_to

  • != not_equal_to

  • > greater

  • < less

  • >= greater_equal

  • <= less_equal

  • && logical_and

  • || logical_or

  • ! logical_not