前言
map 是有序的鍵值對容器，元素的鍵是唯一的，值允許重複。用比較函數 Compare 排序鍵。搜尋、移除和插入操作擁有對數複雜度，即O(logn)。底層實作為紅黑樹。
Map定義
需要包含模闆類頭檔案，需要關鍵字和存儲對象兩個模闆參數。
這樣就定義了一個用int作為索引，并擁有相關聯的指向string的指針.
#include <map>
using namespace std;
void init() {
map<int, string> m1;//空對象
//自帶初值
map<int, string> m2(
{
{1, "A"},
{3, "C"},
{2, "B"}
}
);
//預設按照索引less遞增輸出為
// 1 A
// 2 B
// 3 C
map<int, string,greater<int>> m3(
{
{1, "A"},
{3, "C"},
{2, "B"}
}
);
// 3 C
// 2 B
// 1 A
}
有時候為了使用友善，可以對模闆類以及指針定義成為更簡單的名字。
typedef map<int,string> istrmap;
typedef map<int,string>::iterator IT;
istrmap map1;
IT iter
Map正常操作
成員函數
C++中文線上手冊：https://zh.cppreference.com/
增加元素
總共有三種插入方式。
void add1() {
map<int, string> m(
{
{1, "A"},
{3, "C"},
{2, "B"}
}
);
// 當索引是不存在的值，成功插入；當索引已經存在，則不進行操作
//調用make_pair函數模闆，好處是構造對象不需要參數，用起來更友善
m.insert(pair<int, string>(24, "Z"));
m.insert(map<int, string>::value_type(23, "Y"));
m.insert(make_pair(1, "Z"));
// 索引是原先沒有的，直接插入；索引已經存在直接修改
m[22] = "X";
m[3] = "X";
// 當索引是不存在的值，成功插入；當索引已經存在，則不進行操作
m.emplace(pair<int, string>(21, "W"));
m.emplace(pair<int, string>(1, "W"));
map<int, string>::iterator iter;
for (iter = m.begin(); iter != m.end(); iter++) {
cout << iter->first << ' ' << iter->second << endl;
}
}
//1 A
// 2 B
// 3 X
// 21 W
// 22 X
// 23 Y
// 24 Z
以上三種用法，雖然都可以實作資料的插入，但是它們是有差別的:
用insert函數和emplace函數插入資料，在資料的插入上涉及到集合的唯一性這個概念，即當map中有這個關鍵字時，insert操作是插入資料不了的。
用索引[]方式就不同了，它可以覆寫對應的值。
周遊元素
強烈建議使用疊代器周遊集合！
void search1() {
map<int, string> m(
{
{1, "A"},
{3, "C"},
{2, "B"}
}
);
map<int, string>::iterator iter;
for (iter = m.begin(); iter != m.end(); iter++) {
cout << iter->first << ' ' << iter->second << endl;
}
}
//1 A
// 2 B
// 3 C
下面介紹一個反面例子，看看直接使用索引去周遊而産生的結果。
void search2() {
map<int, string> m(
{
{1, "A"},
{3, "C"},
{5, "B"}
}
);
cout << "周遊前元素的個數：" << m.size() << endl;
for (int i = 0; i < m.size(); i++) {
cout << i << ' ' << m[i] << endl;
}
cout << "周遊後元素的個數：" << m.size();
}
//周遊前元素的個數：3
// 0
// 1 A
// 2
// 3 C
// 4
// 5 B
// 周遊後元素的個數：6
很明顯，因為沒有判定是否存在而是直接無腦使用，原意是周遊一遍集合，結果卻是修改了集合！
删除元素
直接删除元素
可以清空，也可以用疊代器删除指定範圍元素或者單個元素。
但是在周遊的時候要注意，使用疊代器删除元素後，疊代器可能會變成類似野指針的存在！
/*
* 删除有兩種方式，
* clear是直接清空
* erase是删除指定疊代器範圍内的數字
* 也可以用來删除指定的單個元素
* */
void del1() {
map<int, string> m(
{
{1, "A"},
{2, "B"},
{3, "C"}
}
);
//清空
m.clear();//{}
if (m.empty()) {//判斷Vector為空則傳回true
m.insert(pair<int, string>(4, "D"));
m.insert(pair<int, string>(5, "E"));
m.insert(pair<int, string>(6, "F"));
//用疊代器删除單個元素，注意指針被删除後就失效了
map<int, string>::iterator iter = m.begin();
m.erase(iter);//所剩元素{5,E},{6,F}，此時的iter仍然是{4,D}
cout << "錯誤的疊代器内容：" << iter->first << ' ' << iter->second << endl;
//删除一個範圍， 隻保留最後一個
m.erase(m.begin(), ++m.end()); //{6,F}
//通過關鍵字索引的資料存在就删除，并傳回1；如果關鍵字索引的資料不存在就不操作，并傳回0
m.erase(2);
}
map<int, string>::iterator iter;
for (iter = m.begin(); iter != m.end(); iter++) {
cout << iter->first << ' ' << iter->second << endl;
}
}
周遊集合并删除元素
如果想要周遊整個map，并删除所有滿足指定數值的應該如下：
/*
* 周遊集合以删除指定條件的元素
* */
void del2() {
map<int, string> m(
{
{1, "A"},
{2, "B"},
{3, "C"}
}
);
map<int, string>::iterator iter;
// 删除元素後，期望iter指針是繼續指向{3,C}的，
// 但是經過iter++後，竟然又到了上一個元素！
// 很明顯，删除元素後的疊代器變成了類似野指針的存在！
// for (iter = m.begin(); iter != m.end(); iter++) {
// if (iter->first == 2 || iter->second == "B") {
// m.erase(iter);
// }
// cout << iter->first << ' ' << iter->second << endl;
// }
//結果是：
// 1 A
// 2 B
// 1 A
// 3 C
// 正确做法應該是先複制出來一個臨時疊代器
// 接着将原來的疊代器後移一位指向正常的元素
// 最後用臨時疊代器删除指定元素！
// 第二步和第三步不能反了，否則也會影響到原來正常的疊代器！
for (iter = m.begin(); iter != m.end();) {
if (iter->first == 2) {
map<int, string>::iterator iterTemp = iter;
++iter;
m.erase(iterTemp);
} else {
cout << iter->first << ' ' << iter->second << endl;
++iter;
}
}
// 結果是
// 1 A
// 3 C
}
用疊代器删除元素，先是斷言确定疊代器不是尾疊代器，接着将目前疊代器複制到一個新對象，最後傳回的就是這個新的疊代器對象。調用_M_erase_aux方法删除疊代器指向的元素，并且節點數目減一。
void _M_erase_aux(const_iterator __position)
{
_Link_type __y =
static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
(const_cast<_Base_ptr>(__position._M_node),
this->_M_impl._M_header));
_M_drop_node(__y);
--_M_impl._M_node_count;
}
查找函數
count統計元素個數
count函數是用來統計一個元素在目前容器内的個數。由于Map的特性，是以隻能傳回1或者0。
/*
* 用count函數尋找元素，
* */
void find1(set<int> s ){
if (s.count(4) == 1) {
cout << "元素4存在"<<endl;
}
if (s.count(8) == 0) {
cout << "元素8不存在";
}
}
追查源碼，我發現他是用的find方法，将結果跟尾疊代器比較，如果不等于尾疊代器就是找到了，傳回1；反之就是沒找到，傳回0。
find(const _Key& __k) const
{
const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
return (__j == end()
|| _M_impl._M_key_compare(__k,
_S_key(__j._M_node))) ? end() : __j;
}
find擷取元素疊代器
/*
* 用find函數尋找元素，
* */
void find2(set<int> s ){
if (s.find(4)!= s.end() ) {
cout << "元素4存在"<<endl;
}else{
cout << "元素4不存在";
}
if (s.find(8)!= s.end() ) {
cout << "元素8存在"<<endl;
}else{
cout << "元素8不存在";
}
}
而底層是調用的不帶const标的find函數，函數體是一樣的！而其中的核心邏輯就是用_M_lower_bound函數查找來确定位置。
_M_lower_bound(_Link_type __x, _Base_ptr __y, const _Key &__k){
while (__x != 0) {
if (!_M_impl._M_key_compare(_S_key(__x), __k))
__y = __x, __x = _S_left(__x);
else
__x = _S_right(__x);
}
return iterator(__y);
}
比較函數
key排序
map中預設就是使用key排序的，自動按照key的大小，增序存儲，這也是作為key的類型必須能夠進行 < 運算比
較的原因。
首先看一眼map模闆的定義，重點看下第三個參數：class Compare = less<Key> 。
template < class Key， class T， class Compare = less<Key>，
class Allocator = allocator<pair<const Key，T> > > class map;
與less相對的還有greater，都是STL裡面的一個函數對象，那麼什麼是函數對象呢？
函數對象：即調用操作符的類，其對象常稱為函數對象（function object），它們是行為類似函數的對象。表現出一個函數的特征，就是通過“對象名+(參數清單)”的方式使用一個 類，其實質是對operator()操作符的重載。
具體的例子可以去看另一篇文章：Cpp淺析系列-STL之set，這裡就不贅述了。
value排序
邏輯上是先轉為vector數組，接着将數組用指定的規則重新排序得到排序好的結果。至于是否用排序好的數組去轉換為map對象則是看要求了。
bool Special(pair<string, int> a, pair<string, int> b) {
return a.second < b.second;//從小到大排序
}
void specialCompare() {
// 初始map集合
map<string, int> m;
m["a"] = 2;
m["b"] = 3;
m["c"] = 1;
// 轉為vector集合
vector<pair<string, int> > demo(m.begin(), m.end());
for (auto it = demo.begin(); it != demo.end(); ++it) {
cout << (*it).first << " " << (*it).second << endl;
}
cout << endl;
// 排序後檢視效果
sort(demo.begin(), demo.end(), Special);
for (auto it = demo.begin(); it != demo.end(); ++it) {
cout << (*it).first << " " << (*it).second << endl;
}
cout << endl;
// 轉換為新的map集合，差別就是前後類型反了。
map<int, string> m2;
for (vector<pair<string, int> >::iterator it = demo.begin(); it != demo.end(); ++it){
m2[(*it).second]=(*it).first;
}
map<int, string>::iterator iter;
for (iter = m2.begin(); iter != m2.end(); iter++) {
cout << iter->first << ' ' << iter->second << endl;
}
}
//a 2
// b 3
// c 1
//
// c 1
// a 2
// b 3
//
// 1 c
// 2 a
// 3 b
感謝
C++中的STL中map用法詳解
C++ STL中Map的按Key排序和按Value排序
感謝現在努力的自己。