六大權益！華為8月服務日開啟：手機免費貼膜、維修免人工費
8月5日消息，一年一度的華為開發者大會2023（Together）日前在松山湖拉開帷幕，與此同時，華為8月服務日也式開啟，到店可享六大專屬權益。華為用戶可在華為商城Ap
最近在使用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語言代碼：數字雨
Copyright ? 2016-2023 天津谷騏科技有限公司 版權所有 sitemap.xml
違法及侵權請聯系：2376512515@qq.com 津ICP備18001702號
津公網安備 12010102000574號