C++23 新增扁平化关联容器详解

一、引言

在 C++23 标准中，引入了四个新的关联容器：std::flat_set、std::flat_multiset、std::flat_map 和 std::flat_multimap。这些容器是对底层有序随机访问容器进行包装的容器适配器，旨在为开发者提供在某些场景下比传统关联容器更高效的选择。在介绍这四个新容器之前，我们先回顾一下 C++ 中已有的关联容器。

已有关联容器回顾

• C++98：引入了 std::map、std::set、std::multimap 和 std::multiset，这些容器基于红黑树实现，元素按键有序存储，插入、删除和查找操作的时间复杂度为 $O(logn)$。
• C++11：引入了 std::unordered_map、std::unordered_set、std::unordered_multimap 和 std::unordered_multiset，这些容器基于哈希表实现，元素无序存储，平均情况下插入、删除和查找操作的时间复杂度为 $O(1)$。

新容器的引入原因

新容器的引入主要是为了在内存消耗和性能方面提供不同的选择。与传统的关联容器相比，平铺容器在某些场景下具有更好的缓存局部性，从而提高性能。

二、std::flat_set

定义与特性

std::flat_set 是一个类似于 std::set 的容器，但它使用扁平化存储的唯一键集合。它的底层实现使用排序的连续存储（通常是 std::vector 或类似结构），而不是树结构。这使得元素在内存中是连续存储的，具有以下特点：

• 查找速度快：查找操作使用二分查找，时间复杂度为 $O(logn)$。由于内存连续，缓存命中率高，总体查找速度比 std::set 快。
• 插入和删除较慢：插入和删除操作通常需要对数组中的元素进行整体移动，尤其在不支持移动构造时，时间复杂度为 $O(n)$。
• 迭代速度快：由于内存局部性，迭代速度比 std::set 快。
• 内存占用小：相对于平衡二叉树，减少了节点指针的维护，从而节省了内存空间。

代码示例

#include <flat_set>
#include <iostream>int main() {std::flat_set<int> primes{2, 3, 5, 7, 11};// 插入元素primes.insert(13);// 检查存在性if (primes.contains(7)) {std::cout << "7 is a prime number" << std::endl;}// 范围查询auto [begin, end] = primes.equal_range(5);for (auto it = begin; it != end; ++it) {std::cout << *it << " ";}std::cout << std::endl;return 0;
}

适用场景

• 需要频繁查找但较少插入/删除：由于查找速度快，插入和删除操作相对较慢，适合用于需要频繁查找元素的场景。
• 需要快速迭代：内存连续的特性使得迭代速度快，适合需要快速遍历元素的场景。
• 内存受限环境：内存占用小的特点使得它在内存受限的环境中更具优势。

三、std::flat_multiset

定义与特性

std::flat_multiset 类似于 std::flat_set，但允许存储多个具有相同键的元素。它同样使用排序的连续存储，具有与 std::flat_set 类似的性能特点：

• 查找速度快：查找操作使用二分查找，时间复杂度为 $O(logn)$。
• 插入和删除较慢：插入和删除操作通常需要对数组中的元素进行整体移动，时间复杂度为 $O(n)$。
• 迭代速度快：由于内存局部性，迭代速度快。
• 内存占用小：相对于平衡二叉树，减少了节点指针的维护，从而节省了内存空间。

代码示例

#include <flat_set>
#include <iostream>int main() {std::flat_multiset<int> numbers{1, 2, 2, 3, 3, 3};// 插入元素numbers.insert(4);// 查找元素auto range = numbers.equal_range(2);for (auto it = range.first; it != range.second; ++it) {std::cout << *it << " ";}std::cout << std::endl;return 0;
}

适用场景

• 需要存储重复元素且需要快速查找：与 std::flat_set 类似，但允许存储重复元素，适合需要存储重复元素且需要快速查找的场景。
• 需要快速迭代：内存连续的特性使得迭代速度快，适合需要快速遍历元素的场景。
• 内存受限环境：内存占用小的特点使得它在内存受限的环境中更具优势。

四、std::flat_map

定义与特性

std::flat_map 是一个类似于 std::map 的容器，但它使用扁平化存储的键值对容器。它的底层实现使用两个有序数组，一个存储键，另一个存储值，具有以下特点：

• 查找速度快：查找操作使用二分查找，时间复杂度为 $O(logn)$。由于内存连续，缓存命中率高，总体查找速度比 std::map 快。
• 插入和删除较慢：插入和删除操作通常需要对数组中的元素进行整体移动，尤其在不支持移动构造时，时间复杂度为 $O(n)$。
• 迭代速度快：由于内存局部性，迭代速度比 std::map 快。
• 内存占用小：相对于平衡二叉树，减少了节点指针的维护，从而节省了内存空间。
• 使用随机访问迭代器：与 std::map 使用双向迭代器不同，std::flat_map 使用随机访问迭代器。
• 迭代器不稳定：插入和删除元素时迭代器会失效。
• 无法存储不可复制和不可移动的值类型：由于需要对元素进行移动和复制，无法存储不可复制和不可移动的值类型。
• 异常安全性弱：在删除和插入时移动值可能会抛出异常。

代码示例

#include <flat_map>
#include <iostream>
#include <string>int main() {std::flat_map<std::string, int> ages{{"Alice", 30},{"Bob", 25},{"Charlie", 35}};// 插入元素(可能触发排序和移动)ages.insert({"David", 28});// 查找元素if (auto it = ages.find("Alice"); it != ages.end()) {std::cout << "Alice is " << it->second << " years old" << std::endl;}// 迭代for (const auto& [name, age] : ages) {std::cout << name << ": " << age << std::endl;}return 0;
}

适用场景

• 需要频繁查找但较少插入/删除：由于查找速度快，插入和删除操作相对较慢，适合用于需要频繁查找元素的场景。
• 需要快速迭代：内存连续的特性使得迭代速度快，适合需要快速遍历元素的场景。
• 内存受限环境：内存占用小的特点使得它在内存受限的环境中更具优势。

五、std::flat_multimap

定义与特性

std::flat_multimap 类似于 std::flat_map，但允许存储多个具有相同键的键值对。它同样使用排序的连续存储，具有与 std::flat_map 类似的性能特点：

• 查找速度快：查找操作使用二分查找，时间复杂度为 $O(logn)$。
• 插入和删除较慢：插入和删除操作通常需要对数组中的元素进行整体移动，时间复杂度为 $O(n)$。
• 迭代速度快：由于内存局部性，迭代速度快。
• 内存占用小：相对于平衡二叉树，减少了节点指针的维护，从而节省了内存空间。

代码示例

#include <flat_map>
#include <iostream>
#include <string>int main() {std::flat_multimap<std::string, int> scores{{"Alice", 80},{"Bob", 90},{"Alice", 85}};// 插入元素scores.insert({"Charlie", 75});// 查找元素auto range = scores.equal_range("Alice");for (auto it = range.first; it != range.second; ++it) {std::cout << it->first << ": " << it->second << std::endl;}return 0;
}

适用场景

• 需要存储重复键的键值对且需要快速查找：与 std::flat_map 类似，但允许存储重复键的键值对，适合需要存储重复键的键值对且需要快速查找的场景。
• 需要快速迭代：内存连续的特性使得迭代速度快，适合需要快速遍历元素的场景。
• 内存受限环境：内存占用小的特点使得它在内存受限的环境中更具优势。

六、与其他容器的比较

与 std::set 和 std::multiset 的比较

特性	std::set/std::multiset	std::flat_set/std::flat_multiset
底层实现	红黑树	排序的连续存储（通常是 std::vector）
查找速度	$O(logn)$	$O(logn)$，但缓存友好，总体速度更快
插入和删除速度	$O(logn)$	$O(n)$
迭代速度	较慢	较快
内存占用	较大	较小
迭代器稳定性	稳定	不稳定

与 std::map 和 std::multimap 的比较

特性	std::map/std::multimap	std::flat_map/std::flat_multimap
底层实现	红黑树	排序的连续存储（通常是 std::vector）
查找速度	$O(logn)$	$O(logn)$，但缓存友好，总体速度更快
插入和删除速度	$O(logn)$	$O(n)$
迭代速度	较慢	较快
内存占用	较大	较小
迭代器稳定性	稳定	不稳定
迭代器类型	双向迭代器	随机访问迭代器

七、总结

C++23 引入的 std::flat_set、std::flat_multiset、std::flat_map 和 std::flat_multimap 为开发者提供了在某些场景下比传统关联容器更高效的选择。这些容器在查找和迭代操作上具有更好的性能，同时内存占用更小。然而，它们的插入和删除操作相对较慢，迭代器也不稳定。因此，在选择使用这些容器时，需要根据具体的应用场景进行权衡。如果需要频繁进行查找和迭代操作，且插入和删除操作较少，那么这些平铺容器是一个不错的选择。