STL-关联式容器 map
寫在前面:
關聯容器(Associative containers) [??s???i?t?v]
標準庫容器類型:
1、順序容器
比如:vector、list、deque、forward_list(C++11)等。
2、關聯容器
關聯式容器也是用來存儲數據的,與順序容器不同的是,其里面存儲的是
<key, value> 結構的鍵值對,在 數據檢索時比序列式(也就是順序)容器效率更高。
兩者之間的差別: 關聯容器通過鍵(key)存儲和讀取元素 而順序容器則通過元素在容器中的位置存儲和訪問元素且關聯式容器大部分和順序容器相同 比較特別的地方就是關聯容器支持鍵的使用 。
鍵值對
用來表示具有一一對應關系的一種結構,該結構中一般只包含兩個成員變量key和value,key代表鍵值, value表示與key對應的信息
關聯容器共享大部分順序容器的操作 但是關聯容器不提供
front、push_front、pop_front、back、push_back 以及pop_pack操作
但關聯容器可以支持
begin、end、rbegin、rend操作
同時關聯容器還有以下和順序容器公共的構造函數
C<T> c;//創建一個空的容器
C<T> c1(c2);//用c2來拷貝構造c1 ,前提是c2必須和c1的類型相同
C<T> c(b,e);//將序列中的元素復制到c中 b和e是表示序列的迭代器
關聯容器支持通過鍵來高效地查找和讀取元素 兩個基本的關聯容器的類型是
map set
map 的元素以 鍵 – 值 (key --value) 對的形式組織, 鍵用在map中的索引 而值表示所存儲和讀取的數據
set 僅包含一個值 并有效的支持某個值是否存在的查詢
注:
如果希望有效的存儲不同值的集合 那么使用set容器比較合適
而 map容器則更使用于需要存儲、修改 每個鍵所關聯的值的情況
比如說map可以用來實現一個簡單的字典
map 和set 類型的對象所包含的元素都具有不同的鍵值 不允許為同一個鍵 添加第二個元素 也就是一個key 不能對應兩個不同的value
如果一個鍵必須對應多個實例 則需要使用multimp 或multiset
multimap :支持同一個鍵多次出現的map類型
multiset :支持同一個鍵多次出現的set類型
關聯容器也支持很多順序容器也提供相同的操作 此外 還提供 管理或只用鍵的特殊操作
| set | 大小可變的集合,支持通過鍵實現的快速讀取 |
| multimap | 支持同一個鍵多次出現的map類型 |
| multiset | 支持同一個鍵多次出席那的set類型 |
這次的博客主要來整理map的相關知識要點!
1. 頭文件 <map>
2. map:
1.map是關聯容器,它按照特定的次序(按照key來比較)存儲由鍵–key和值–value組合而成的元素。 (有序)
2. 在map中,鍵值key通常用于排序和惟一地標識元素,而值value中存儲與此鍵值key關聯的內容。鍵值 key和值value的類型可能不同,并且在map的內部,key與value通過成員類型value_type綁定在一起, 為其取別名稱為pair: typedef pair value_type;
3.在內部,map中的元素總是按照鍵值key進行比較排序的。
4. map中通過鍵值訪問單個元素的速度通常比unordered_map容器慢,但map允許根據順序對元素進行 直接迭代(即對map中的元素進行迭代時,可以得到一個有序的序列)。
5.map支持下標訪問符,即在[ ]中放入key,就可以找到與key對應的value。
6. map通常被實現為二叉搜索樹(更準確的說:平衡二叉搜索樹(紅黑樹))。
注意:
關于 pair 對象就不再這里重復的介紹了,稍微的提一下
pair 也是一種類模板 ,這個類將一對值耦合在一起,這些值可能是不同類型的 ,單個值可以通過其公共成員 first 和 second 訪問。
因此這里說的 key 和 value 也就是 pair 對象中的 公共成員 first 和 second
3. map類型
腦子里記住這個不是地圖了喲!
map 是 "鍵–值對"的集合。
map類型通常可理解為關聯數組;
可使用 "鍵"作為下標來獲取一個值,正如內置數組類型一樣 而關聯的本質在于元素的值與某個特定的鍵相關聯,而并非通過元素在數組中的位置來獲取。
4.模板參數
key: 鍵值對中key的類型
T: 鍵值對中value的類型
Compare: 比較器的類型,map中的元素是按照key來比較的,缺省情況下按照 less (小于)來比較,一般情況 下(內置類型元素)該參數不需要傳遞,如果無法比較時(自定義類型),需要用戶自己顯式傳遞比較規則 (一般情況下按照函數指針或者仿函數來傳遞)
Alloc:通過空間配置器來申請底層空間,不需要用戶傳遞,除非用戶不想使用標準庫提供的空間配置器 注意:在使用map時,需要包含頭文件。
5. 容器屬性
關聯容器中的元素由它們的key作為引用而不是他們在容器中的絕對位置
容器中所有的元素總是有著嚴格的順序,所有插入的元素都按此順序都有確定的位置
容器中的任何兩個元素都不能具有等效的key. 也就是key不能相同
6. map對象的定義
要使用 map 對象,則必須包含 map 頭文件。在定義 map 對象時,必須分 別指明"鍵"和"值"的類型(value type)
例如 :定義鍵和值都是string 類型的 map對象。
7. map的構造函數
| map<k, v>m; | 創建一個名為 m 的空 map 對象,其鍵和值的類型分別為 k 和 v |
| map<k, v> m(m2); | 創建 m2 的副本 m也就是用m2來拷貝構造m,m 與 m2 必須有相同的鍵類型和值類型 |
| map<k, v> m(b, e); | 使用存儲迭代器 b 和 e 標記的范圍內所有 元素的副本來創建m。元素的類型必須能轉換為 pair<const k, v> |
示例:
void Test1() {map<string,string>m;//創建一個空的map對象 m.insert(pair<string,string>("helloworld!","你好世界!"));//插入數據map<string, string> m1(m);//拷貝構造map<string, string> m2(m.begin(), m.end());//使用迭代器進行構造for (auto e : m){cout << e.first << " " << e.second << endl;}for (auto e : m1){cout << e.first << " " << e.second << endl;} for (auto e : m2){cout << e.first << " " << e.second << endl;} }8. map的迭代器
函數聲明 功能簡介
| iterator end () | 返回最后一個元素的下一個位置 |
| const_iterator begin () const | 返回第一個元素的const迭代器 |
| const_iterator end () const | 返回最后一個元素下一個位置的const迭代器 |
| reverse_iterator rbegin() | 返回第一個元素位置的反向迭代器即rend |
| reverse_iterator rend() | 返回最后一個元素下一個位置的反向迭代器即 rbegin |
| const_reverse_iterator rbegin() const | 返回第一個元素位置的const反向迭代器即rend |
| const_reverse_iterator rend() const | 返回最后一元素下一個位置的反向迭代器即rbegin |
大家會發現其實這個和我們之前的vector的迭代器沒有多大的差別不過就是多了一個 const 的反向迭代器,用法和vector是差不多的。
做幾個簡單的示例:假設map對象里的值,我們事先是已經插入好了的。
map<int, string>m;m.insert(pair<int, string>(1001, "小明"));m.insert(pair<int, string>(1003, "小紅"));m.insert(pair<int, string>(1002, "小花"));m.insert(pair<int, string>(1000, "小花"));Test2(m);普通正向迭代器遍歷修改
cout << "普通正向迭代器遍歷" << endl;map<int, string>::iterator mite = m1.begin();while (mite != m1.end()){cout << mite->first << " " << mite->second << endl;++mite;}注意:
這里再對map對象的 first 和 second 訪問是使用的是 " - >" --箭頭操作符
這里大家會發現map里面的是已經排好序了的,會默認把鍵值小的排在前面,是一個升序的排列,相對于int類型的值就會直接進行比較而 string 類型或者別的是按ASCCI碼來比較如以下:
普通反向迭代器遍歷修改
cout << "普通反向迭代器遍歷" << endl;map<int, string>::reverse_iterator rmite = m1.rbegin();while (rmite != m1.rend()){rmite->second = "李飛";cout << rmite->first << " " << rmite->second << endl;++rmite;}const 正向迭代器遍歷
cout << "const迭代器遍歷" << endl;map<int, string>::const_iterator cite = m1.begin();while (cite != m1.end()){cout << cite->first << " " << cite->second << endl;++cite;}const反向迭代器遍歷
cout << "const反向迭代器遍歷" << endl;map<int, string>::const_reverse_iterator crite = m1.rbegin();while (crite != m1.rend()){cout << crite->first << " " << crite->second << endl;++crite;}范圍for 與 auto 關鍵字遍歷(推薦使用)
其實這樣遍歷還是比較麻煩的,相比有兩種比較簡約而又方便的遍歷方式推薦給大家,但是他們的底層還是使用的相關迭代器進行實現的
范圍 for 遍歷
void Test4(map<int,string> &m) {cout << "范圍 for遍歷" << endl;for (auto e : m){cout << e.first << " " << e.second << endl;} }auto 自動識別迭代器遍歷
void Test5(map<int, string> &m) {cout << "auto關鍵字的使用" << endl;auto mite = m.begin();while (mite != m.end()){cout <<mite->first << " " << mite->second << endl;++mite;} }9. map 對象中元素的修改
| pair<iterator,bool> insert ( const value_type& x ) | 在map中插入鍵值對x,注意x是一個鍵值對,返回 值也是鍵值對:iterator代表新插入元素的位置, bool代表釋放插入成功 |
| iterator insert ( iterator position, const value_type& x ) | 在position位置插入值為x的鍵值對,返回該鍵值對 在map中的位置,注意:元素不一定必須插在 position位置,該位置只是一個參考 |
| template void insert ( InputIterator ?rst, InputIterator last ) | 在map中插入[?rst, last)區間中的元素 |
| void erase ( iterator position ) | 刪除position位置上的元素 |
| size_type erase ( const key_type& x ) | 刪除鍵值為x的元素 |
| void erase ( iterator ?rst, iterator last ) | 刪除[?rst, last)區間中的元素 |
| void swap ( map<Key,T,Compare,Allocator>& mp ) | 交換兩個map中的元素 |
| void clear ( ) 將map中的元素清空 | iterator ?nd ( const key_type& x ) |
| const_iterator ?nd ( const key_type& x ) const | 在map中插入key為x的元素,找到返回該元素的位 置的const迭代器,否則返回cend |
| size_type count ( const key_type& x ) const | 返回key為x的鍵值在map中的個數,注意map中 key是唯一的,因此該函數的返回值要么為0,要么 為1,因此也可以用該函數來檢測一個key是否在 map中 |
insert 插入一個數據
這里的插入肯定是插入一個 pair 對象,那么請看示例;
map<int, string> m;pair<int, string> p1(2, "two");m.insert(pair<int, string>(1, "one"));m.insert(p1);for (auto e : m){cout << e.first <<" "<<e.second << endl;}注意
在一個map對象中 key 的值是唯一的,是不允許插入兩個相同的 key ,相同的key 所對應的value也無法插入
erase 刪除一個數據
map<int, string>m;m.insert(pair<int, string>(1, "one"));m.insert(pair<int, string>(2, "two")); m.insert(pair<int, string>(3, "three"));auto a = m.begin();m.erase(a);//刪除迭代器位置的元素m.erase(3);//刪除 key 為3的元素 即 first=3 的數據交換兩個map對象
10. map的大小容量以及 [ ]
| bool empty ( ) const | 檢測map中的元素是否為空,是返回true,否則 返回false |
| size_type size() const | 返回map中有效元素的個數 |
| mapped_type& operator[] (const key_type& k) | 返回去key對應的value |
注意:
雖然 key 不能修改但是 value是可以修改的,也可以通過 [ key ]來訪問對應的 value 或者修改:
如:
總結
以上是生活随笔為你收集整理的STL-关联式容器 map的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 408计算机组成原理有汇编吗,2021考
- 下一篇: Linux下SSH远程连接断开后让程序继