最近在使用C++寫代碼,也是剛接觸C++,恰巧碰到一個需要使用map的地方,不知道其查找元素的性能怎么樣,所以研究了下,做個記錄,目前從x86平臺測試map查找一個元素大概需要2us,這里你需要考慮在自身硬件平臺比如arm,做一些cpu加壓情況下再查看map效率以評估map是否滿足業務需求。
在C++編程的世界中,STL(標準模板庫)一直以其強大的數據結構和算法而著稱。其中,std::map是STL提供的一個關聯容器,它的核心是紅黑樹(Red-Black Tree)數據結構。紅黑樹是一種自平衡的二叉查找樹,以其出色的性能和平衡機制而備受推崇。
本文將深入探討std::map以及其核心紅黑樹的原理,解釋其關鍵特性,包括插入、查找和刪除操作,以及有序性的優勢。我們還將進行性能測試,以展示std::map在實際應用中的卓越性能。
std::map的核心數據結構是紅黑樹(Red-Black Tree)數據結構。紅黑樹是一種自平衡二叉查找樹,它具有以下特性:
這些性質保證了紅黑樹的平衡性,使得樹的高度保持相對較小,從而提供了高效的查找、插入和刪除操作。
當您向std::map插入新的鍵值對時,紅黑樹需要進行一系列旋轉和著色操作,以保持樹的平衡。這確保了即使在大規模數據集下,插入操作仍然高效。
// 插入操作示例std::map<int, std::string> myMap;myMap[42] = "Hello, World!";
在插入操作中,紅黑樹遵循一些規則,例如:
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;}
刪除操作也是相對復雜的,因為它需要保持樹的平衡。當刪除一個節點時,可能會引起樹的不平衡,需要執行旋轉和著色操作來修復它。這些操作確保了紅黑樹的性質仍然得以維持。
// 刪除操作示例myMap.erase(42);
在刪除操作中,紅黑樹也遵循一系列規則,包括:
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都展現了其出色之處,使其成為處理大規模數據集的理想之選。
本文鏈接:http://www.www897cc.com/showinfo-26-32434-0.htmlC++ STL之std::map:紅黑樹的魔法與性能測試
聲明:本網頁內容旨在傳播知識,若有侵權等問題請及時與本網聯系,我們將在第一時間刪除處理。郵件:2376512515@qq.com
上一篇: 21個優秀開源網絡爬蟲庫,適合Python、Java、Go、JavaScript開發語言
下一篇: C語言代碼:數字雨