[數據結構]淺談C++ STL 的map和set容器

2019-11-08 19:25:26

字體：大中小

來源：轉載

供稿：網友

[數據結構]淺談C++ STL 的map和set容器

在C++的STL庫中，有許多種不同結構、不同用途的容器。容器又可以分為兩大類，分別是：

序列式容器（sequence containers）關聯式容器（associative containers）

其中序列式容器包括vector、queue和list等，本文中的map和set屬于關聯式容器。先說說set容器，set的特性是，所有的元素再插入的時候都會根據元素的鍵值來排序。（默認為升序，需要時可以傳入模板參數改為降序排序）。set元素的鍵值就是實值，實值就是鍵值，所以set中的值不能修改，只能做插入和刪除的操作。set不允許兩個元素有相同的鍵值。 set的底層實現是紅黑樹，所以set容器的效率非常高。

set常用成員有（具體用法見SetTest()）

1. 迭代器（前向/反向/const迭代器）2. Insert a. 直接插入一個值（返回pair <K，V>）first->元素位置 second->成功標志 b. 在某位置插入 c. 插入一個區間3. Erase a. 刪除一個有效迭代器所指的位置，否則assert b. 刪除一個值未找到不報錯，找到即刪除 c. 刪除一個迭代器區間的值4. Swap5. Clear6. Emplace——構造插入，比insert效率高（C++11）7. Find8. count——常用于快速判斷一個元素是否存在

容器map的特性是,所有元素都會根據元素的鍵值自動排序。map的所有元素都是pair，同時擁有實值和鍵值。pair的第一元素被視為鍵值，第二元素被視為實值。map同樣不允許有兩個元素擁有相同的鍵值，也不能修改元素的鍵值，不過實值可以修改。map與set相似的是底層也是map容器實現。

map常用成員（測試用例見MapTest）

1. Insert a. 插入一個pair<Key,Value>() 2. Operator[] a. 以K值為參數，返回V值引用

#include <iostream>#include <string>#include <set>#include <map>using namespace std;void SetTest(){ int i; int a[5]={0,1,2,3,4}; set<int> s(a,a+5); cout<<"Size="<<s.size()<<endl;//size=5; cout<<"3 count="<<s.count(3)<<endl;//3 count=1 s.insert(3); cout<<"Size="<<s.size()<<endl;//size=5; cout<<"3 count="<<s.count(3)<<endl;//3 count=1 s.insert(5); cout<<"Size="<<s.size()<<endl;//size=6; cout<<"3 count="<<s.count(3)<<endl;//3 count=1 s.erase(1); cout<<"Size="<<s.size()<<endl;//size=5; cout<<"3 count="<<s.count(3)<<endl;//3 count=1 cout<<"1 count="<<s.count(1)<<endl;//1 count=0 //insert一個值到set時，可通過insert的返回值來判斷 //insert的返回值是一個pair<iterator,bool>類型的值 //若插入成功，iterator值為插入位置的迭代器，bool的值為true //若插入失敗，iterator值為已有元素的迭代器，bool的值為false pair<set<int>::iterator,bool> PR=s.insert(8); cout<<"insert 8 pr.first:"<<*pr.first<<"-"<<"pr.second:"<<pr.second<<endl; pr=s.insert(0); cout<<"insert 0 pr.first:"<<*pr.first<<"-"<<"pr.second:"<<pr.second<<endl; s.erase(1);//erase一個不存在的元素，對set無影響 set<int>::iterator is=s.find(1);//未找到元素1 is值為s.end() 即is是一個無效的迭代器; //s.erase(is); //erase一個無效的迭代器會觸發assert，所以向erase傳入迭代器時要保證其合法性 cout<<"升序排列的is1："; set<int>::iterator is1=s.begin(); while (is1!=s.end()) { cout<<*is1++<<" "; } cout<<endl; set<int>::iterator is2=s.begin(); //*is2 = 9;//無法通過編譯，在set中其底層實現是const_iterator，故不能通過迭代器修改值 //set默認升序排列，也可以通過改變模板參數改為降序排列 set<int,greater<int>> s1; s1.insert(a,a+5); cout<<"降序排列的is3："; set<int,greater<int>>::iterator is3=s1.begin(); while (is3!=s1.end()) { cout<<*is3++<<" "; } cout<<endl;}void MapTest(){ map<string,int> m;//以string為鍵值，以int為實值 m["[]"]=1;//map內對[]操作符進行重載，以鍵值為參數，返回值為實值的引用 //相當于(*((insert(value_type(k,T()))).first)).second m.insert(make_pair<string,int>("make_pair",2)); pair<string,int> value("pair",3); pair<map<string,int>::iterator,bool> ret; ret=m.insert(value); cout<<"ret.first:"<<"("<<(ret.first)->first<<","<<(ret.first)->second<<")"<<" "<<"ret.second:"<<ret.second<<endl; map<string,int>::iterator mi=m.begin(); while (mi!=m.end()) { cout<<(*mi).first<<": "<<mi->second<<endl; mi++; }}int main (){ cout<<"SetTest()"<<endl; SetTest(); cout<<endl; cout<<endl; cout<<"MapTest()"<<endl; MapTest(); cout<<endl; cout<<endl; return 0;}

運行結果

這里寫圖片描述