一、什么是 map？

map 容器，又稱鍵值對容器，即該容器的底層是以紅黑樹變體實現(xiàn)的，是典型的關(guān)聯(lián)式容器。這意味著，map 容器中的元素可以分散存儲在內(nèi)存空間里，而不是必須存儲在一整塊連續(xù)的內(nèi)存空間中。跟任意其它類型容器一樣，它能夠存放各種類型的對象。

二、容器特性

1.存儲結(jié)構(gòu)

map是由多個節(jié)點(二叉樹中的紅黑樹變體)組成的。

2.鍵值對

map是一個鍵值對序列，即(key,value)——封裝在結(jié)構(gòu)體pair中，它提供基于key的快速檢索能力，不能在指定位置插入，但支持at(pos)和[]操作。如：map[key]=value；

multimap與map的區(qū)別：map中的key只能唯一，每個key只能出現(xiàn)一次；而multimap中同一key可以出現(xiàn)多次。

3.雙向迭代器

不支持隨機(jī)訪問迭代器，只能從容器中第一個元素或最后一個元素開始遍歷容器，直到找到該位置。

三、基本函數(shù)實現(xiàn)

1，構(gòu)造函數(shù)

• map();創(chuàng)建一個空map
• map(const map&);復(fù)制構(gòu)造函數(shù)
• map(begin,end);復(fù)制[begin,end)區(qū)間內(nèi)的元素，到另一個map中

2.map插入

• pair insert(const T& x); //往容器插入元素，返回pair

  在map中插入元素的三種方式：

  假設(shè) map mapStu;

  一、通過pair的方式插入對象

  mapStu.insert( pair(3,"小張") );

  二、通過pair的方式插入對象

  mapStu.inset(make_pair(-1, “校長-1”));

  三、通過value_type的方式插入對象

  mapStu.insert( map::value_type(1,"小李") );

  四、通過索引(key)的方式插入值

  mapStu[3] = “小劉";

  mapStu.at(4) = “小王"；

  • 注意：使用key的方式插入，當(dāng)key存在時會直接修改key對應(yīng)的值，當(dāng)key不存在時會新建一個然后插入

3.map刪除

• iterator erase(iterator it);刪除鍵值對中迭代器指向元素
• iterator erase(iterator first,iterator last);刪除鍵值對中[first,last)中元素
• size_type erase(const key_type& key); 刪除指定的元素
• void clear();清空鍵值對中所有元素

4.查找函數(shù)

• iterator map.find(key); 查找鍵key是否存在，若存在，返回該鍵的元素的迭代器；若不存在，返回map.end();

• size_type map.count(keyElem); //返回容器中key為keyElem的對組個數(shù)。對map來說，要么是0，要么是1。對multimap來說，值可能大于1。

• pair map.equal_range(keyElem); //返回容器中key與keyElem相等的上下限的兩個迭代器。上限是閉區(qū)間，下限是開區(qū)間，如[beg,end)。

  以上函數(shù)返回兩個迭代器，而這兩個迭代器被封裝在pair中。

5.判斷函數(shù)

• bool empty() const;判斷容器中是否有元素，若無元素，則返回 true；反之，返回 false。

6.大小函數(shù)

• int size() const;返回鍵值對中元素的個數(shù)
• int max_size() const;返回最大可允許的map元素數(shù)量值

7.其他函數(shù)

• void swap(map&);交換兩個同類型容器的數(shù)據(jù)

四、基本用法

#include 
#include
using namespace std;
int main()
{
  //保存學(xué)生學(xué)號和姓名
  map<int,string> s;
  for (int i = 0; i < 10; i++)
  {
    string ch = "ABCDEFGHIJ";
    string name= "maye";
    //注意pair的類型參數(shù)，需要和map的一致
    s.insert(pair<int,string>(i,name+ch[i]));
  }
  s.insert(make_pair(111, "C語言PLUS"));
  s.insert(map<int, string>::value_type(222, "法外狂徒"));
  s[333] = "頑石";


  cout << "學(xué)號：" <<" "<< "姓名：" << endl;
  for (map<int, string>::iterator it = s.begin(); it != s.end(); it++)
  {
    cout << it->first << "      " << it->second << endl;
  }
  //cout << "\\nmap size():" << s.size() << endl;


  //查找指定的key值，返回指向的迭代器，沒有找到返回end()迭代器，所以再輸出之前需要判斷是否找到
  map<int, string>::iterator it1 = s.find(6);
  if (it1 != s.end())
  {
    cout << it1->first << " " << it1->second << endl;
  }
  //如果map中有等于4的key，則返回指向4的迭代器，如果沒有返回第一個大于4的元素的迭代器，沒有找到返回end()迭代器
  it1 = s.lower_bound(4);
  if (it1 != s.end())
  {
    cout << it1->first << " " << it1->second << endl;
  }
  //如果map中有大于4的key，返回第一個大于4的元素的迭代器，沒有找到返回end()迭代器
  it1 = s.upper_bound(4);
  if (it1 != s.end())
  {
    cout << it1->first << " " << it1->second << endl;
  }
  cout << "------------------我是 C語言Plus 華麗分割線" << endl;
  //定義對組，接受equal_range()的返回值
  pair