C++ STL之std::map：紅黑樹的魔法與性能測試
最近在使用C++寫代碼，也是剛接觸C++，恰巧碰到一個需要使用map的地方，不知道其查找元素的性能怎么樣，所以研究了下，做個記錄，目前從x86平臺測試map查找一個元素大概需要2us，這里你需要考慮在自身硬件平臺比如arm，做一些cpu加壓情況下再查看map效率以評估map是否滿足業務需求。
在C++編程的世界中，STL（標準模板庫）一直以其強大的數據結構和算法而著稱。其中，std::map是STL提供的一個關聯容器，它的核心是紅黑樹（Red-Black Tree）數據結構。紅黑樹是一種自平衡的二叉查找樹，以其出色的性能和平衡機制而備受推崇。
本文將深入探討std::map以及其核心紅黑樹的原理，解釋其關鍵特性，包括插入、查找和刪除操作，以及有序性的優勢。我們還將進行性能測試，以展示std::map在實際應用中的卓越性能。
一、紅黑樹,std::map的核心
std::map的核心數據結構是紅黑樹（Red-Black Tree）數據結構。紅黑樹是一種自平衡二叉查找樹，它具有以下特性：
- 每個節點是紅色或黑色：每個節點都被標記為紅色或黑色，這是紅黑樹的基本性質之一。
- 根節點是黑色：樹的根節點始終是黑色的。
- 每個葉子節點（NIL節點，通常表示為黑色）都被認為是黑色的：NIL節點是樹的末端節點，它們通常被表示為黑色。
- 如果一個節點是紅色的，那么它的子節點必須是黑色的：這一性質確保沒有兩個相鄰的紅色節點。
- 從任何給定節點到其后代葉子節點的每條路徑都包含相同數量的黑色節點：這個性質保證了樹的平衡。
這些性質保證了紅黑樹的平衡性，使得樹的高度保持相對較小，從而提供了高效的查找、插入和刪除操作。
二、std::map常見操作
1.插入操作：保持平衡
當您向std::map插入新的鍵值對時，紅黑樹需要進行一系列旋轉和著色操作，以保持樹的平衡。這確保了即使在大規模數據集下，插入操作仍然高效。
// 插入操作示例
std::map<int, std::string> myMap;
myMap[42] = "Hello, World!";在插入操作中，紅黑樹遵循一些規則，例如：
- 新插入的節點通常是紅色的。
- 如果插入破壞了紅黑樹的性質，就需要執行旋轉和著色操作來恢復平衡。
2.查找操作：速度與效率
std::map的查找操作非常高效，因為紅黑樹的結構使得它可以迅速定位到所需的節點。查找操作會從根節點開始，根據鍵值比較逐步沿樹向下移動，直到找到目標節點或確定目標節點不在樹中。這個過程的時間復雜度是O(log N)，其中N是樹中元素的數量。
// 查找操作示例
auto result = myMap.find(42);
if (result != myMap.end()) {
std::cout << "Found: " << result->second << std::endl;
} else {
std::cout << "Not found!" << std.endl;
}3.刪除操作：平衡的維護
刪除操作也是相對復雜的，因為它需要保持樹的平衡。當刪除一個節點時，可能會引起樹的不平衡，需要執行旋轉和著色操作來修復它。這些操作確保了紅黑樹的性質仍然得以維持。
// 刪除操作示例
myMap.erase(42);在刪除操作中，紅黑樹也遵循一系列規則，包括：
- 如果刪除的節點是紅色的，可能不會破壞樹的性質。
- 如果刪除的節點是黑色的，就可能會引發平衡問題，需要執行一系列的操作來修復。
4.有序性：按鍵排序
std::map中的元素是按鍵值有序排列的，這意味著您可以使用迭代器來遍歷元素，或者進行范圍查找。
// 使用迭代器遍歷示例
for (const auto& pair : myMap) {
std::cout << "Key: " << pair.first << ", Value: " << pair.second << std::endl;
}三、性能測試:查找操作
下面是一個性能測試示例，因為我對查找某個元素的性能是有要求的，所以做了一個簡單測試：
#include <iostream>
#include <map>
#include <random>
#include <chrono>
int main() {
std::map<int, int> testMap;
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<int> dist(1, 1000000);
// 插入100,000個隨機鍵值對
for (int i = 0; i < 100000; ++i) {
int key = dist(gen);
int value = i;
testMap[key] = value;
}
// 測試查找操作的效率
int totalIterations = 100000;
int foundCount = 0;
std::chrono::high_resolution_clock::time_point start = std::chrono::high_resolution_clock::now();
for (int i = 0; i < totalIterations; ++i) {
int key = dist(gen);
if (testMap.find(key) != testMap.end()) {
foundCount++;
}
}
std::chrono::high_resolution_clock::time_point end = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> duration = std::chrono::duration_cast<std::chrono::duration<double>>(end - start);
std::cout << "查找 " << totalIterations << " 個元素所用時間: " << duration.count() << " 秒" << std::endl;
std::cout << "找到 " << foundCount << " 個元素" << std::endl;
std::cout << "查找單個元素耗時: " << (duration.count()*1000000) / totalIterations << " 微秒" << std::endl;
return 0;
}我們首先插入了100,000個隨機鍵值對，然后執行查找操作，并記錄查找到的元素數量，并計算時間。
使用g++編譯執行結果：
四、總結
std::map是C++編程中的神奇工具，它提供高效的查找、插入和刪除操作，并按鍵排序數據。紅黑樹的自平衡性確保了它在各種操作下都能保持高效性。無論是實現關鍵功能還是性能測試，std::map都展現了其出色之處，使其成為處理大規模數據集的理想之選。
