一、引言

在 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 為開發者提供了在某些場景下比傳統關聯容器更高效的選擇。這些容器在查找和迭代操作上具有更好的性能，同時內存占用更小。然而，它們的插入和刪除操作相對較慢，迭代器也不穩定。因此，在選擇使用這些容器時，需要根據具體的應用場景進行權衡。如果需要頻繁進行查找和迭代操作，且插入和刪除操作較少，那么這些平鋪容器是一個不錯的選擇。