【C++】認識map和set

前言：

一：認識map和set

二：map和set的使用

1.set的使用

2.map的使用?

三：map的insert方法返回值

四：map的[ ]的使用

五：multiset和multimap

六：map和set的底層數據結構

七：map和set的迭代器

總結：

前言：

我們通過之前的學習，已經學會了AVL樹和紅黑樹，但是STL中并沒有這兩種類，它是對紅黑樹進行了封裝，供上層使用的。

這里，我們就要先學會使用map和set了，是STL中的類模板，它們的底層都是紅黑樹。

一：認識map和set

大家有沒有想過，生活中很多東西都是一對一的。比如去停車場停車時，收費站會先記錄車牌號，之后一個車牌號對應一個存放時間；或者通訊錄中一個號碼對應一個聯系人等。這種方法就是鍵值對。一個唯一的鍵，對應一個唯一的值。但是你可以發現，這個值是可以修改的，而鍵不能修改。

比如一個老師要對每個學生管理，就要把每個學生學號管理起來，此時沒有用到值，只有鍵。

通過以上兩個例子，你就會發現，鍵都是唯一的，而值不是。這里再次說明，鍵也是不能修改的。

map中就是使用鍵值對的方式存儲；而set中只有鍵。

map中的值能修改，鍵不能修改；set中只有鍵，不能修改。

二：map和set的使用

既然我們知道了map存儲的是鍵值對，set存儲的是鍵，那么接下來，我們就要使用它們了。

1.set的使用

這個很簡單，引入<set>頭文件，之后可以去觀察cplusplus官網查看方法的使用(這里不是作者偷懶，而是我們到了現在這個階段，就必須學會看文檔了)。以下給出使用方法：

int main()
{set<int> s;s.insert(4);s.insert(6);s.insert(3);s.insert(5);set<int>::iterator it = s.begin();//auto it = s.begin();//底層是二叉搜索樹 默認中序遍歷while (it != s.end()){cout << *it << " ";++it;}cout << endl;//刪除最小值 也就是最左邊的迭代器指向的位置s.erase(s.begin());  //通過返回值判斷是否刪除成功int x;cin >> x;//int num = s.erase(x);//if (num == 0)//{//	cout << x << "不存在！" << endl;//}for (auto e : s){cout << e << " ";}cout << endl;set<int>::iterator pos = s.find(x);if (pos != s.end()){s.erase(pos);}else{cout << x << "不存在！" << endl;}for (auto e : s){cout << e << " ";}cout << endl;//使用算法頭文件的find查找auto pos1 = find(s.begin(), s.end(), x); //O(N) auto pos2 = s.find(x);                   //O(logN)//用find查找元素是否存在并不方便 使用count方便cin >> x;if (s.count(x)){cout << x << "在！" << endl;}else{cout << x << "不存在！" << endl;}return 0;
}

對沒錯，就這么多。

2.map的使用?

map存儲的是鍵值對，那么當然要有兩個模板參數，但是我們如何插入數據呢？

在此之前我們先來認識一個pair類：

可以發現它是一個結構體，兩個模板參數。

成員變量為：

對，很簡單，map就是存的它，但是對first加上了const修飾。接下來我們看看map的使用方法：

int main()
{map<string, string> dict;//我們要使用一個類向map中插入數據pair<string, string> kv1("left", "左邊");dict.insert(kv1);//傳入匿名對象dict.insert(pair<string, string>("right", "右邊"));//還有一個函數模板 make_pair 只用傳入鍵值對 就可以返回一個pair對象dict.insert(make_pair("insert", "插入"));//還有我們可以傳入多參數的初始化對象的方法dict.insert({ "string", "字符串" });map<string, string> dict1 = { {"left", "左邊"}, {"right", "右邊"} };map<string, string>::iterator it = dict.begin();while (it != dict.end()){//*it返回的是pair 但是其不支持流提取//cout << (*it) << endl;//可以去看pair 兩個成員變量 first 和 second//這里不是插入順序 而是字符ASCII碼排序 中序遍歷//cout << (*it).first << ":" << (*it).second << endl;cout << it->first << ":" << it->second << endl; //最好用第二種++it;}cout << endl; //用自定義類型寫范圍for遍歷map 最好這樣寫 不用深拷貝for (const auto& e : dict){cout << e.first << ":" << e.second << endl;}cout << endl;string arr[] = { "蘋果", "西瓜","蘋果","西瓜","蘋果" };map<string, int> Count;int tmp = 1;for (const auto& str : arr){//find返回的是迭代器auto ret = Count.find(str);//找到返回那個未知的迭代器 沒有找到返回endif (ret == Count.end()){//沒有這個元素Count.insert({str, 1});}else{++ret->second;}}auto it1 = Count.begin();while (it1 != Count.end()){//*it返回的是pair 但是其不支持流提取//cout << (*it) << endl;//可以去看pair 兩個成員變量 first 和 second//這里不是插入順序 而是字符ASCII碼排序 中序遍歷//cout << (*it).first << ":" << (*it).second << endl;cout << it1->first << ":" << it1->second << endl; //最好用第二種++it1;}return 0;
}

以上的insert方法我們需要注意，還有迭代器的使用方法，運行結果為：

三：map的insert方法返回值

這里我們最需要注意的就是map的insert方法返回值：

返回的是一個pair類，第一個參數是iterator，第二個參數是bool。

這是什么意思呢？這里先說明第二個參數bool：當我們插入一個鍵時，如果當前鍵存在，則說明此鍵已經不能再次插入了，也就是插入失敗，所以測試第二個參數為false；當前鍵不存在，返回true。

第二個參數是iterator，也就是迭代器，經過我們之前的學習(無中生有哈哈)，已經知道了iterator本就是指針，這個指針是什么類型的呢？對，是map中存儲數據節點的類型。你已經知道map中存儲的是pair，那么這個迭代器本質也就是pair的指針。

所以為了測試insert方法，我們需要拿iterator來接收它，因為insert返回的是pair，且第一個參數類型是iterator所以要像下面這樣寫：

int main()
{map<int, int> m;int a[] = { 1, 2, 3 };for (auto e : a){m.insert({ e, e });}map<int, int>::iterator it;it = m.insert({ 10, 1 }).first; //insert不能修改！cout << it->first << endl;cout << it->second << endl;return 0;
}

上面代碼中我們插入了一個不存在的鍵，此時insert方法返回的就是{ iterator, true }，其中iterator是插入10位置的指針，true代表插入成功。所以結果如下：

之后我們再來嘗試插入相同的值，再次插入10這個鍵：

int main()
{map<int, int> m;int a[] = { 1, 2, 3 };for (auto e : a){m.insert({ e, e });}map<int, int>::iterator it;it = m.insert({ 10, 1 }).first; //insert不能修改！//再次插入10 觀察返回的pair中的值//因為iterator是指針 所以使用重載的->cout << "iterator指向的節點為：" << m.insert({10, 3}).first->first << endl;if (m.insert({ 10, 3 }).second)cout << "插入成功" << endl;elsecout << "插入失敗" << endl;cout << "此時10對應的值為：" << m.insert({10, 3}).first->second << endl;return 0;
}

運行結果為：

可以看到，當10再次插入，已經無法插入，但是返回的iterator會指向10，所以對應的值也無法修改，且insert返回pair第二個參數為false；第一次插入返回10的位置，值為true。

那么我們如何改變對應的值呢？剛才不是說能修改對應的值嗎？

四：map的[ ]的使用

這時我們要修改值不能使用insert，而要是用 [ ] ，這個 [ ] 充當著插入，修改，查找的功能(也就是說底層封裝的insert，更加詳細的解釋可以先下一篇用紅黑樹實現map和set)。

int main()
{map<string, string> dict;dict.insert(make_pair("sort", "排序"));//插入 + 修改dict["left"] = "左邊";//修改dict["left"] = "左邊、剩余";//key不存在->插入 <"insert", "">dict["insert"];//key存在  -> 查找cout << dict["left"] << endl;  //使用[]要謹慎return 0;
}