日韩成人免费在线_国产成人一二_精品国产免费人成电影在线观..._日本一区二区三区久久久久久久久不

當前位置:首頁 > 科技  > 軟件

C++ STL之std::map:紅黑樹的魔法與性能測試

來源: 責編: 時間:2023-11-21 17:13:22 391觀看
導讀最近在使用C++寫代碼,也是剛接觸C++,恰巧碰到一個需要使用map的地方,不知道其查找元素的性能怎么樣,所以研究了下,做個記錄,目前從x86平臺測試map查找一個元素大概需要2us,這里你需要考慮在自身硬件平臺比如arm,做一些cpu加壓

最近在使用C++寫代碼,也是剛接觸C++,恰巧碰到一個需要使用map的地方,不知道其查找元素的性能怎么樣,所以研究了下,做個記錄,目前從x86平臺測試map查找一個元素大概需要2us,這里你需要考慮在自身硬件平臺比如arm,做一些cpu加壓情況下再查看map效率以評估map是否滿足業務需求。KRj28資訊網——每日最新資訊28at.com

KRj28資訊網——每日最新資訊28at.com

在C++編程的世界中,STL(標準模板庫)一直以其強大的數據結構和算法而著稱。其中,std::map是STL提供的一個關聯容器,它的核心是紅黑樹(Red-Black Tree)數據結構。紅黑樹是一種自平衡的二叉查找樹,以其出色的性能和平衡機制而備受推崇。KRj28資訊網——每日最新資訊28at.com

本文將深入探討std::map以及其核心紅黑樹的原理,解釋其關鍵特性,包括插入、查找和刪除操作,以及有序性的優勢。我們還將進行性能測試,以展示std::map在實際應用中的卓越性能。KRj28資訊網——每日最新資訊28at.com

一、紅黑樹,std::map的核心

std::map的核心數據結構是紅黑樹(Red-Black Tree)數據結構。紅黑樹是一種自平衡二叉查找樹,它具有以下特性:KRj28資訊網——每日最新資訊28at.com

  • 每個節點是紅色或黑色:每個節點都被標記為紅色或黑色,這是紅黑樹的基本性質之一。
  • 根節點是黑色:樹的根節點始終是黑色的。
  • 每個葉子節點(NIL節點,通常表示為黑色)都被認為是黑色的:NIL節點是樹的末端節點,它們通常被表示為黑色。
  • 如果一個節點是紅色的,那么它的子節點必須是黑色的:這一性質確保沒有兩個相鄰的紅色節點。
  • 從任何給定節點到其后代葉子節點的每條路徑都包含相同數量的黑色節點:這個性質保證了樹的平衡。

這些性質保證了紅黑樹的平衡性,使得樹的高度保持相對較小,從而提供了高效的查找、插入和刪除操作。KRj28資訊網——每日最新資訊28at.com

二、std::map常見操作

1.插入操作:保持平衡

當您向std::map插入新的鍵值對時,紅黑樹需要進行一系列旋轉和著色操作,以保持樹的平衡。這確保了即使在大規模數據集下,插入操作仍然高效。KRj28資訊網——每日最新資訊28at.com

// 插入操作示例std::map<int, std::string> myMap;myMap[42] = "Hello, World!";

在插入操作中,紅黑樹遵循一些規則,例如:KRj28資訊網——每日最新資訊28at.com

  • 新插入的節點通常是紅色的。
  • 如果插入破壞了紅黑樹的性質,就需要執行旋轉和著色操作來恢復平衡。

KRj28資訊網——每日最新資訊28at.com

2.查找操作:速度與效率

std::map的查找操作非常高效,因為紅黑樹的結構使得它可以迅速定位到所需的節點。查找操作會從根節點開始,根據鍵值比較逐步沿樹向下移動,直到找到目標節點或確定目標節點不在樹中。這個過程的時間復雜度是O(log N),其中N是樹中元素的數量。KRj28資訊網——每日最新資訊28at.com

// 查找操作示例auto result = myMap.find(42);if (result != myMap.end()) {    std::cout << "Found: " << result->second << std::endl;} else {    std::cout << "Not found!" << std.endl;}

KRj28資訊網——每日最新資訊28at.com

3.刪除操作:平衡的維護

刪除操作也是相對復雜的,因為它需要保持樹的平衡。當刪除一個節點時,可能會引起樹的不平衡,需要執行旋轉和著色操作來修復它。這些操作確保了紅黑樹的性質仍然得以維持。KRj28資訊網——每日最新資訊28at.com

// 刪除操作示例myMap.erase(42);

在刪除操作中,紅黑樹也遵循一系列規則,包括:KRj28資訊網——每日最新資訊28at.com

  • 如果刪除的節點是紅色的,可能不會破壞樹的性質。
  • 如果刪除的節點是黑色的,就可能會引發平衡問題,需要執行一系列的操作來修復。

KRj28資訊網——每日最新資訊28at.com

4.有序性:按鍵排序

std::map中的元素是按鍵值有序排列的,這意味著您可以使用迭代器來遍歷元素,或者進行范圍查找。KRj28資訊網——每日最新資訊28at.com

// 使用迭代器遍歷示例for (const auto& pair : myMap) {    std::cout << "Key: " << pair.first << ", Value: " << pair.second << std::endl;}

三、性能測試:查找操作

下面是一個性能測試示例,因為我對查找某個元素的性能是有要求的,所以做了一個簡單測試:KRj28資訊網——每日最新資訊28at.com

#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個隨機鍵值對,然后執行查找操作,并記錄查找到的元素數量,并計算時間。KRj28資訊網——每日最新資訊28at.com

使用g++編譯執行結果:KRj28資訊網——每日最新資訊28at.com

KRj28資訊網——每日最新資訊28at.com

四、總結

std::map是C++編程中的神奇工具,它提供高效的查找、插入和刪除操作,并按鍵排序數據。紅黑樹的自平衡性確保了它在各種操作下都能保持高效性。無論是實現關鍵功能還是性能測試,std::map都展現了其出色之處,使其成為處理大規模數據集的理想之選。KRj28資訊網——每日最新資訊28at.com

本文鏈接:http://www.www897cc.com/showinfo-26-32434-0.htmlC++ STL之std::map:紅黑樹的魔法與性能測試

聲明:本網頁內容旨在傳播知識,若有侵權等問題請及時與本網聯系,我們將在第一時間刪除處理。郵件:2376512515@qq.com

上一篇: 21個優秀開源網絡爬蟲庫,適合Python、Java、Go、JavaScript開發語言

下一篇: C語言代碼:數字雨

標簽:
  • 熱門焦點
Top 主站蜘蛛池模板: 全州县| 蓬莱市| 涞源县| 曲周县| 巴彦淖尔市| 富宁县| 方正县| 敦化市| 德阳市| 乌恰县| 景洪市| 沈丘县| 阜城县| 湟中县| 郑州市| 彰化市| 东山县| 都兰县| 婺源县| 沙湾县| 教育| 上饶市| 瑞金市| 嘉鱼县| 清丰县| 年辖:市辖区| 枞阳县| 郎溪县| 岑巩县| 墨脱县| 迭部县| 吉安县| 盘山县| 襄汾县| 家居| 探索| 潜山县| 桑日县| 金塔县| 定日县| 磴口县|