C++-setmap詳解

C++set&map

1. 序列式容器和關聯式容器

1.1 序列式容器

序列式容器按照線性順序存儲元素,元素的位置取決于插入的時間和位置,與元素的值無關。

主要特點:

  • 元素按插入順序存儲

  • 可以通過位置(索引)直接訪問元素

  • 不自動排序

  • 允許重復元素

常見的序列式容器:

  1. array(C++11)

    • 固定大小的數組

    • 內存連續分配

    • 大小在編譯時確定

    • 快速隨機訪問

  2. vector

    • 動態數組

    • 內存連續分配

    • 可動態擴展

    • 在尾部插入/刪除高效

    • 支持快速隨機訪問

  3. deque(雙端隊列)

    • 雙端可擴展

    • 內存分段連續

    • 在頭尾插入/刪除高效

    • 支持快速隨機訪問(比vector稍慢)

  4. list

    • 雙向鏈表

    • 內存非連續分配

    • 在任何位置插入/刪除高效

    • 不支持隨機訪問

  5. forward_list(C++11)

    • 單向鏈表

    • 內存非連續分配

    • 更節省空間

    • 只支持單向遍歷

1.2 關聯式容器

關聯式容器按照特定順序存儲元素,元素的順序取決于元素的鍵(key),而不是插入的順序。

主要特點:

  • 元素按特定順序(平衡二叉搜索樹或哈希)存儲

  • 通過鍵(key)快速查找元素

  • 通常實現為平衡二叉搜索樹或哈希表

  • 有些版本不允許重復元素

常見的關聯式容器:

  1. 有序關聯容器(基于紅黑樹實現)

    • set:唯一鍵的集合,按鍵排序

    • map:鍵值對集合,按鍵排序,鍵唯一

    • multiset:鍵可重復的set

    • multimap:鍵可重復的map

  2. 無序關聯容器(C++11引入,基于哈希表實現)

    • unordered_set:唯一鍵的集合,基于哈希

    • unordered_map:鍵值對集合,基于哈希,鍵唯一

    • unordered_multiset:鍵可重復的unordered_set

    • unordered_multimap:鍵可重復的unordered_map

2. 認識pair類型

2.1 概念

pair是C++標準模板庫(STL)中的一個實用模板類,用于將兩個值組合成一個單一對象,可以存儲兩個不同類型的元素,稱為firstsecond。這兩個值可以是相同類型,也可以是不同類型。它定義在<utility>頭文件中,是許多STL容器(如map)的基礎構建塊。

2.2 pair實現

template <class T1, class T2>
struct pair
{typedef T1 first_type;typedef T2 second_type;first_type first;second_type second;pair(): first(T1()), second(T2()) {}    // 默認構造pair(const T1& a, const T2& b): first(a), second(b) {}template<class U, class V>pair (const pair<U,V>& pr): first(pr.first), second(pr.second) {}    // 拷貝構造
};

為什么拷貝構造需要使用類中內嵌模板?

template <typename U1, typename U2> pair(const pair<U1, U2>& p);?這個構造函數的存在是為了支持跨類型的拷貝構造,而不僅僅是同類型的拷貝構造。這是 C++ 模板類設計中的一個重要特性,稱為轉換構造函數

  1. 類型轉換支持

    • 允許從?pair<U1, U2>?構造?pair<T1, T2>

    • 只要?U1?可以轉換為?T1U2?可以轉換為?T2

  2. 場景:

    std::pair<int, double> p1(42, 3.14);
    std::pair<long, float> p2(p1);  // 需要這個模板構造函數
    
  3. 與普通拷貝構造的區別:

    • 普通拷貝構造:pair(const pair<T1, T2>& p)

    • 模板拷貝構造:template <typename U1, typename U2> pair(const pair<U1, U2>& p)

  4. 如果沒有這個模板拷貝構造函數會怎么樣?

    std::pair<int, std::string> p1(1, "hello");
    std::pair<double, const char*> p2(p1);  // 編譯錯誤
    // 因為沒有從 pair<int,string> 到 pair<double,const char*> 的轉換路徑
    

2.3 創建和初始化pair

2.3.1 構造函數
std::pair<int, std::string> p1(1, "apple");
2.3.2 使用make_pair函數(自動推導類型)

make_pair函數模板原型:

template <class T1,class T2>
inline pair<T1,T2> make_pair (T1 x, T2 y)
{return ( pair<T1,T2>(x,y) );
}
auto p2 = std::make_pair(2, "banana");
2.3.3 C++11-initializer_list初始化
std::pair<int, std::string> p3 = {3, "cherry"};

2.4 訪問pair成員

通過 firstsecond 訪問成員。

2.4.1 普通訪問
std::pair<int, std::string> p(1, "apple");std::cout << "First: " << p.first << std::endl;    // 輸出: First: 1
std::cout << "Second: " << p.second << std::endl;  // 輸出: Second: apple
2.4.2 結構化綁定(C++17)
auto p = std::make_pair(3.14, "pi");
auto [value, name] = p;  // value=3.14, name="pi"

3. set

set是C++ STL中的關聯式容器,它存儲唯一元素(key)并自動排序去重。

set原型

template < class T, class Compare = less<T>, class Alloc = allocator<T>> class set;
  • T就是set底層關鍵字(key)的類型

  • set默認要求T?持?于?較(仿函數less支持搜索樹大于往右走,小于往左走,greater則相反),若比較的類型和方式比較復雜,可以自己實現仿函數

  • set底層是?紅?樹實現,增刪查效率是O(logN) ,迭代器遍歷是?的搜索樹的中序,根據搜索樹的性質,遍歷是有序的

3.1 成員函數

3.1.1 成員類型
成員類型解釋
key_type第一個模板參數T
value_type第一個模板參數T
key_compare第二個模板參數(less仿函數)
allocator_type第三個模板參數,STL空間配置器(內存池)
3.1.2 構造函數
序號函數原型說明
1??explicit set (const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type())默認構造
2??set (const set& x)拷貝構造
3??set (initializer_list<value_type> il, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type())使用 initializer_list 初始化
4??template <class InputIterator> set (InputIterator first, InputIterator last, const key_compare& comp = key_compare(), const allocator_type& = allocator_type())使用一段迭代器區間初始化
3.1.3 賦值重載
序號函數原型說明
1??set& operator= (const set& x)兩個已存在的 set 對象的賦值
2??set& operator= (initializer_list<value_type> il)使用 initializer_list 賦值
3.1.4 迭代器
序號函數原型說明
1??iterator begin()返回指向 set 對象中第一個元素的迭代器
2??const_iterator begin() const返回指向 set 對象中第一個元素的 const 迭代器
3??iterator end()返回指向 set 對象末尾元素之后位置的迭代器
4??const_iterator end() const返回指向 set 對象末尾元素之后位置的 const 迭代器
5??reverse_iterator rbegin()返回指向 set 對象末尾元素的反向迭代器
6??const_reverse_iterator rbegin() const返回指向 set 對象末尾元素的 const 反向迭代器
7??reverse_iterator() rend()返回指向 set 對象起始元素之前位置的反向迭代器
8??const_reverse_iterator() rend() const返回指向 set 對象起始元素之前位置的 const 反向迭代器

注意:set迭代器是按中序的方式遍歷的。

3.1.5 容量相關的接口
序號函數原型說明
1??bool empty() const判斷 set 對象是否為空
2??size_type size() const返回 set 對象中元素的數量
3.1.6 修改相關的接口
序號函數原型說明
1??pair<iterator,bool> insert (const value_type& val)向 set 對象中插入 val 元素
2??iterator erase (const_iterator position)刪除 set 對象中 position 迭代器位置元素,返回刪除元素的下一個有效迭代器
3??size_type erase (const value_type& val)刪除 set 對象中 val 元素,返回值返回為刪除的 val 元素(0或1)
4??void clear()清空 set 對象

pair<iterator,bool> insert (const value_type& val) 返回值解析

返回值是一個 std::pair,包含兩個部分:

  1. iterator:指向插入元素的迭代器

    • 如果插入成功:指向新插入的元素

    • 如果插入失敗(元素已存在):指向已存在的元素

  2. bool:表示插入是否成功

    • true:元素被成功插入

    • false:元素已存在,未插入新元素

3.1.7 其他
序號函數原型說明
1??iterator find (const value_type& val)在 set 對象中查找 val 元素,成功返回該位置迭代器,失敗返回迭代器end()
2??size_type count (const value_type& val) const返回 set 對象中 val 元素的數量(0或1)

3.2 set與multiset的區別

set和multiset都是C++ STL中的關聯容器,它們的主要區別在于元素的唯一性。

主要區別

  1. 元素唯一性

    • set:存儲唯一元素,不允許重復

    • multiset:允許存儲重復元素

  2. 插入操作

    • set插入已存在元素時,插入操作會失敗

    • multiset可以重復插入相同元素

  • set與multiset接口一致。

  • 對于包含重復元素的multiset,find接口會返回按照容器排序順序(默認是中序遍歷順序)出現的第一個與key相等的元素的迭代器。

4. map

map 是C++標準模板庫(STL)中的一個關聯容器,它存儲的元素是pair類型,并且根據鍵(key)自動排序去重。

map原型

template < class Key, class T, class Compare = less<Key>, class Alloc = allocator<pair<const Key,T>> > class map;

map中存儲的pair類型

typedef pair<const Key, T> value_type;
  • Key就是map底層關鍵字的類型,T是map底層value的類型

  • map默認要求Key?持?于?較(仿函數less支持搜索樹大于往右走,小于往左走,greater則相反),若比較的類型和方式比較復雜,可以自己實現仿函數

  • map底層是?紅?樹實現,增刪查效率是O(logN) ,迭代器遍歷是?的搜索樹的中序,根據搜索樹的性質,遍歷是有序的

4.1 成員函數

4.1.1 成員類型
成員類型解釋
key_type第一個模板參數Key
mapped_type第二個模板參數T
value_typemap 中實際存儲的元素 pair<const key_type,mapped_type>
key_compare第三個模板參數(less仿函數)
allocator_type第死個模板參數,STL空間配置器(內存池)
4.1.2 構造函數
序號函數原型說明
1??explicit map (const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type())默認構造
2??map(const map& x)拷貝構造
3??map(initializer_list<value_type> il, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type())使用 initializer_list 初始化
4??template <class InputIterator> map (InputIterator first, InputIterator last, const key_compare& comp = key_compare(), const allocator_type& = allocator_type())使用一段迭代器區間初始化
4.1.3 賦值重載
序號函數原型說明
1??map& operator= (const map& x)兩個已存在的 map 對象的賦值
2??map& operator= (initializer_list<value_type> il)使用 initializer_list 賦值
4.1.4 迭代器
序號函數原型說明
1??iterator begin()返回指向 map 對象中第一個元素的迭代器
2??const_iterator begin() const返回指向 map 對象中第一個元素的 const 迭代器
3??iterator end()返回指向 map 對象末尾元素之后位置的迭代器
4??const_iterator end() const返回指向 map 對象末尾元素之后位置的 const 迭代器
5??reverse_iterator rbegin()返回指向 map 對象末尾元素的反向迭代器
6??const_reverse_iterator rbegin() const返回指向 map 對象末尾元素的 const 反向迭代器
7??reverse_iterator() rend()返回指向 map 對象起始元素之前位置的反向迭代器
8??const_reverse_iterator() rend() const返回指向 map 對象起始元素之前位置的 const 反向迭代器

注意:map迭代器是按中序的方式遍歷的。

4.1.5 容量相關的接口
序號函數原型說明
1??bool empty() const判斷 map 對象是否為空
2??size_type size() const返回 map 對象中元素的數量
4.1.6 元素的訪問
序號函數原型
1??mapped_type& operator[] (const key_type& k)

map?的?operator[]?是一個非常有用的成員函數,它提供了對映射值的快速訪問和修改能力。

功能說明

  1. 查找與修改:如果鍵?k?存在于 map 中,返回對應的映射值(value)的引用

  2. 插入與修改:如果鍵?k?不存在,會自動插入一個新的鍵值對,鍵為?k,值為?mapped_type?的默認構造值,然后返回這個新值(value)的引用

operator[]實現

(*( (insert(make_pair(k,mapped_type()))).first).second)

解析

mapped_type& operator[] (const key_type& k) {pair<iterator, bool> ret = insert({ k, mapped_type() });iterator it = ret.first;return it->second;
}
4.1.7 修改相關的接口
序號函數原型說明
1??pair<iterator,bool> insert (const value_type& val)向 map 對象中插入 val 元素
2??iterator erase (const_iterator position)刪除 map 對象中 position 迭代器位置元素,返回刪除元素的下一個有效迭代器
3??size_type erase (const key_type& val)刪除 map 對象中 val 元素,返回值返回為刪除的 val 元素(0或1)
4??void clear()清空 map 對象

pair<iterator,bool> insert (const value_type& val) 返回值解析

返回值是一個 std::pair,包含兩個部分:

  1. iterator:指向插入元素的迭代器

    • 如果插入成功:指向新插入的元素

    • 如果插入失敗(元素已存在):指向已存在的元素

  2. bool:表示插入是否成功

    • true:元素被成功插入

    • false:元素已存在,未插入新元素

4.1.8 其他
序號函數原型說明
1??iterator find (const value_type& val)在 map 對象中查找 val 元素,成功返回該位置迭代器,失敗返回迭代器end()
2??size_type count (const value_type& val) const返回 map 對象中 val 元素的數量(0或1)

4.2 map與multimap的區別

map和multimap都是C++ STL中的關聯容器,它們的主要區別在于元素的唯一性。

主要區別

  1. 元素唯一性

    • map:存儲唯一元素,不允許重復

    • multimap:允許存儲重復元素

  2. 插入操作

    • map插入已存在元素時,插入操作會失敗

    • multimap可以重復插入相同元素

  3. operator[]

    • map:支持 operator[] 訪問

    • multimap:不支持 operator[],因為鍵不唯一

  • map與multimap接口一致。

  • 對于包含重復元素的multimap,find接口會返回按照容器排序順序(默認是中序遍歷順序)出現的第一個與key相等的元素的迭代器。

5. set與map迭代器失效問題

  • 只有指向被刪除元素的迭代器會失效

循環中刪除元素

std::set<int> s = {1, 2, 3, 4, 5};
for (auto it = s.begin(); it != s.end(); ) {if (*it % 2 == 0) {it = s.erase(it);  // erase返回下一個有效迭代器} else {++it;}
}

今天的看不懂,會成為明天的太簡單。

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/pingmian/93040.shtml
繁體地址,請注明出處:http://hk.pswp.cn/pingmian/93040.shtml
英文地址,請注明出處:http://en.pswp.cn/pingmian/93040.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

解決程序連不上RabbitMQ:Attempting to connect to/access to vhost虛擬主機掛了的排錯與恢復

前言&#xff1a;在分布式系統里&#xff0c;RabbitMQ作為消息中間件&#xff0c;是服務間通信的關鍵紐帶。但實際使用中&#xff0c;程序連接RabbitMQ失敗的情況時有發生。本文結合真實報錯&#xff0c;細致呈現從問題發現到解決的完整排錯思路&#xff0c;還會深入講解Rabbit…

K8S中如何配置PDB(Pod Disruption Budget)

1. PDB 核心概念作用&#xff1a;控制自愿中斷&#xff08;如節點升級、縮容&#xff09;期間&#xff0c;應用的最小可用副本數或最大不可用比例。關鍵參數&#xff1a;minAvailable&#xff1a;必須保持運行的 Pod 數量&#xff08;如 2 或 50%&#xff09;。maxUnavailable&…

從 0 到 1:用 MyCat 打造可水平擴展的 MySQL 分庫分表架構

一、為什么要分庫分表&#xff1f; 單機 MySQL 的極限大致在&#xff1a;維度經驗值單表行數≤ 1 000 萬行&#xff08;B 樹三層&#xff09;單庫磁盤≤ 2 TB&#xff08;SSD&#xff09;單機 QPS≤ 1 萬&#xff08;InnoDB&#xff09;當業務繼續增長&#xff0c;數據量和并發…

電池模組奇異值分解降階模型

了解如何將奇異值分解 (SVD) 降階模型 (ROM) 應用于電池模塊熱模擬。挑戰隨著電池模塊在電動汽車和儲能系統中的重要性日益提升&#xff0c;其熱性能管理也成為一項重大的工程挑戰。高功率密度會產生大量熱量&#xff0c;如果散熱不當&#xff0c;可能導致電池性能下降、性能下…

《Python函數:從入門到精通,一文掌握函數編程精髓》

堅持用 清晰易懂的圖解 代碼語言&#xff0c;讓每個知識點變得簡單&#xff01; &#x1f680;呆頭個人主頁詳情 &#x1f331; 呆頭個人Gitee代碼倉庫 &#x1f4cc; 呆頭詳細專欄系列 座右銘&#xff1a; “不患無位&#xff0c;患所以立。” Python函數&#xff1a;從入門到…

【記錄貼】STM32 I2C 控制 OLED 卡死?根源在 SR1 與 SR2 的讀取操作

問題描述最近在復用以前STM32F407控制OLED的代碼&#xff0c;移植到STM32F103 上&#xff0c;使用硬件 I2C 通信方式。按照常規流程&#xff0c;先發送 OLED 的從機地址&#xff0c;OLED 有正常應答&#xff0c;但當發送第一個控制命令&#xff08;0xAE&#xff09;前的控制字節…

【AI驅動的語義通信:突破比特傳輸的下一代通信范式】

文章目錄1 語義通信簡介1.1 基本概念&#xff1a;什么是語義通信&#xff1f;語義通信的核心目標1.2 基本結構&#xff1a;語義通信系統結構語義通信系統的通用結構組成語義通信系統的結構關鍵模塊1.3 基于大模型的語義通信關鍵技術&#x1f9e0;語義通信系統中AI大模型的設計建…

網絡原理-HTTP

應用層自定義協議自定義協議是指根據特定需求設計的通信規則&#xff0c;用于設備或系統間的數據交換。其核心在于定義數據結構、傳輸方式及處理邏輯。協議結構示例典型的自定義協議包含以下部分&#xff1a;頭部&#xff08;Header&#xff09;&#xff1a;標識協議版本、數據…

ROS配置debug指南

一. 安裝插件 下面的這一個插件過期了需要用下面的這一個插件來替換:二. 設置CMakeLists.txt的編譯模式 set(CMAKE_BUILD_TYPE "Debug") set(CMAKE_CXX_FLAGS_DEBUG "$ENV{CXXFLAGS} -O0 -Wall -g -ggdb") set(CMAKE_CXX_FLAGS_RELEASE "$ENV{CXXFLAG…

微軟正式將GPT-5接入Microsoft Copilot Studio(國際版)

微軟宣布正式在Microsoft Copilot Studio&#xff08;國際版&#xff09;中集成GPT-5&#xff0c;推動智能體構建能力實現突破性升級。此次更新不僅為企業用戶帶來更高效的響應速度、更精準的語境理解能力&#xff0c;還通過增強的邏輯推理功能&#xff0c;顯著提升了AI交互的深…

微算法科技(NASDAQ:MLGO)通過蟻群算法求解資源分配的全局最優解,實現低能耗的區塊鏈資源分配

隨著區塊鏈網絡規模的不斷擴大和業務需求的日益復雜&#xff0c;資源分配問題逐漸成為制約其發展的關鍵因素之一。傳統的區塊鏈資源分配方法往往存在效率低下、能耗過高、難以達到全局最優解等問題。高能耗不僅增加了運營成本&#xff0c;還對環境造成了較大的壓力。因此&#…

深入淺出JVM:Java虛擬機的探秘之旅

深入淺出JVM&#xff1a;Java虛擬機的探秘之旅一、JVM 初相識&#xff1a;揭開神秘面紗 在 Java 的世界里&#xff0c;JVM&#xff08;Java Virtual Machine&#xff0c;Java 虛擬機&#xff09;就像是一個神秘的幕后大 boss&#xff0c;掌控著 Java 程序運行的方方面面。你可以…

Nginx學習筆記(八)—— Nginx緩存集成

&#x1f5c4;&#x1f5c4; Nginx緩存集成 &#x1f4cc;&#x1f4cc; 一、緩存核心價值 #mermaid-svg-CNji1KUDOsF8MwoY {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-CNji1KUDOsF8MwoY .error-icon{fill:#5522…

httpx 設置速率控制 limit 時需要注意 timeout 包含 pool 中等待時間

假設通過 httpx.Client 設置 limit 速率控制后&#xff0c;同時發起多個請求訪問 youtube。并且由于科學原因一直連接不上 假設一共 4 個連接&#xff0c;max_connection2&#xff0c;timeout5s。 默認會發生的情況不是前兩個連接 tcp 握手 timeout&#xff0c;后兩個連接再發起…

【網絡】TCP/UDP總結復盤

1.UDP的格式2.TCP的格式3.TCP是來解決什么問題的&#xff1f;答&#xff1a;解決IP層的不可靠傳輸問題&#xff0c;可能數據包丟失、損壞、重復等為上層應用層提高可靠有序的數據傳輸服務通過校驗和、確認應答機制、序列號來解決不可靠傳輸和無序性問題通過流量控制--->>…

Nginx 配置中,root 和 alias 區別

在 Nginx 配置中&#xff0c;root 和 alias 都用于定義文件路徑&#xff0c;但它們的行為有重要區別&#xff0c;特別是 路徑拼接方式 和 末尾斜杠 (/) 的影響。1. root 和 alias 的區別 (1) root 指令 作用&#xff1a;root 會將 location 的 URI 拼接到 root 路徑后面&#x…

基于vue.js的無縫滾動

方法一&#xff1a;基于requestAnimationFrame demo <template><h-page-container class"hoem-page"><h1>無縫滾動</h1><h2>垂直方向</h2><div class"container1"><AutoScroll :data"list" :item-…

【Linux學習|黑馬筆記|Day4】IP地址、主機名、網絡請求、下載、端口、進程管理、主機狀態監控、環境變量、文件的上傳和下載、壓縮和解壓

【DAY4】 今天看的是Linux第四章剩余部分 至此Linux暫時學到這&#xff0c;第五章還包含很多軟件的安裝&#xff0c;但是等我要用的時候再裝吧 我現在只裝了MySQL8.0&#xff0c;具體教程請看筆記安裝教程 內容包含更換鏡像源和安裝配置步驟 文章目錄【DAY4】6&#xff09;IP地…

【合新通信】射頻光纖傳輸模塊詳解

射頻光纖傳輸模塊是一種將射頻(RF)信號通過光纖進行傳輸的關鍵設備&#xff0c;廣泛應用于通信、軍事、廣播電視等領域。以下是關于射頻光纖傳輸模塊的全面介紹&#xff1a;基本原理與組成射頻光纖傳輸模塊主要由以下幾部分組成&#xff1a;電光轉換單元&#xff1a;將輸入的射…

【信息收集】從GET到POST:破解登錄表單的全流程

目標&#xff1a;將瀏覽器數據代理至BP的proxy模塊。將個人PHP的留言板項目首頁登錄數據包代理至BP&#xff0c;并轉發至intrder模塊&#xff0c;進行暴力破解。免責聲明&#xff1a;本文章內容僅用于個人網絡安全知識學習與研究&#xff0c;嚴禁用于任何未經授權的攻擊或非法活…