STL之unordered_map map multimap 排序嵌套

ゝ一世哀愁。 2021-06-24 14:36 965阅读 0赞

## **一、介绍** ##

无序映射表（Unordered Map）容器是一个存储以键值对组合而成的元素的关联容器。底层数据结构二叉平衡树（红黑树）。  
运行效率方面：unordered\_map最高，hash\_map其次，而map效率最低。需要无序容器时候用unordered\_map，有序容器时候用map，map默认以key的升序排序。

## **二、访问函数** ##

<table> 
 <thead> 
  <tr> 
   <th>函数</th> 
   <th align="left">作用</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>operator[]</td> 
   <td align="left">访问函数</td> 
  </tr> 
  <tr> 
   <td>at</td> 
   <td align="left">访问函数</td> 
  </tr> 
 </tbody> 
</table>

## **二、迭代函数** ##

<table> 
 <thead> 
  <tr> 
   <th>函数</th> 
   <th align="left">作用</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>begin</td> 
   <td align="left">返回指向容器起始位置的迭代器（iterator）</td> 
  </tr> 
  <tr> 
   <td>end</td> 
   <td align="left">返回指向容器末尾位置的迭代器</td> 
  </tr> 
  <tr> 
   <td>cbegin</td> 
   <td align="left">返回指向容器起始位置的常迭代器（const_iterator）</td> 
  </tr> 
  <tr> 
   <td>cend</td> 
   <td align="left">返回指向容器末尾位置的常迭代器</td> 
  </tr> 
 </tbody> 
</table>

for(map<int, string>::iterator it = mapS.begin(); it != mapS.end(); it++)
        Cout<<it->first<<" "<<it->second<<end;  //输出key值和关联值

// 反向遍历
    mymap['x'] = 100;
    mymap['y'] = 200;
    mymap['z'] = 300;
    
      // show content:
      std::map<char,int>::reverse_iterator rit;
      for (rit=mymap.rbegin(); rit!=mymap.rend(); ++rit)
        std::cout << rit->first << " => " << rit->second << '\n';
    
    z => 300
    y => 200
    x => 100

int nSize = mapS.size()
    for(int i = 1; i<= nSize; i++) 
           Cout<<mapS[i]<<end;   //key需为数值

## **三、容量函数** ##

<table> 
 <thead> 
  <tr> 
   <th>函数</th> 
   <th align="left">作用</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>size</td> 
   <td align="left">返回有效元素个数</td> 
  </tr> 
  <tr> 
   <td>max_size</td> 
   <td align="left">返回 unordered_map 支持的最大元素个数</td> 
  </tr> 
  <tr> 
   <td>empty</td> 
   <td align="left">判断是否为空</td> 
  </tr> 
 </tbody> 
</table>

## **四、修改函数** ##

<table> 
 <thead> 
  <tr> 
   <th>函数</th> 
   <th align="left">作用</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>insert</td> 
   <td align="left">插入元素</td> 
  </tr> 
  <tr> 
   <td>erase(it)</td> 
   <td align="left">删除元素。it为遍历<code>map&lt;int, string&gt;::iterator it</code>对象</td> 
  </tr> 
  <tr> 
   <td>swap</td> 
   <td align="left">交换内容，Map中的swap不是一个容器中的元素交换，而是两个容器交换；</td> 
  </tr> 
  <tr> 
   <td>clear</td> 
   <td align="left">清空内容</td> 
  </tr> 
 </tbody> 
</table>

mapS.insert(pair<int, string>(1, “1111”));
    mapS.insert(map<int, string>::value_type (1, “11”));
    mapS.insert(make_pair<int, string>(4,“11”)); 
    mapS["aaaa"] = “aaaaaaa”;

foo['x']=100;
      foo['y']=200;
    
      bar['a']=11;
      bar['b']=22;
      bar['c']=33;
      foo.swap(bar);
    
    foo contains:
    a => 11
    b => 22
    c => 33
    bar contains:
    x => 100
    y => 200

## **四、操作函数** ##

<table> 
 <thead> 
  <tr> 
   <th>函数</th> 
   <th align="left">作用</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>find</td> 
   <td align="left">通过给定主键查找元素，返回位置</td> 
  </tr> 
  <tr> 
   <td>count</td> 
   <td align="left">返回匹配给定主键的元素的个数，可用于判断是否有该key，无法知道所在位置，存在返回1，否在返回0</td> 
  </tr> 
  <tr> 
   <td>equal_range</td> 
   <td align="left">返回值匹配给定搜索值的元素组成的范围</td> 
  </tr> 
 </tbody> 
</table>

map<int,string >::iterator it;
    it=mapS.find("key"); //没找到返回map.end()
    if(it!=mapS.end())
        mapS.erase(it);

## **五、其他** ##

**根据key值排序：**

template <class T> struct greater : binary_function <T,T,bool> {
      bool operator() (const T& x, const T& y) const
        {
       return x>y;}
    };
    map<string, int, greater<string> > name_map;

struct CmpByKeyLength {
      bool operator()(const string& k1, const string& k2) {
        return k1.length() < k2.length();
      }
    };
    map<string, int, CmpByKeyLength> name_map;

**根据value值排序：**

struct CmpByValue {
      bool operator()(const PAIR& lhs, const PAIR& rhs) {
        return lhs.second < rhs.second;
      }
    };
    vector<PAIR> name_score_vec(name_score_map.begin(), name_score_map.end());  
    //需要将其转成vector排序，不如直接使用vector。
      sort(name_score_vec.begin(), name_score_vec.end(), CmpByValue());

**嵌套map及遍历：**

map<int,map<int,string> >::iterator multitr; //嵌套
    map<int,string>::iterator intertr;
    for(multitr=multiMap.begin();multitr!=multiMap.end();multitr++)
    {
            for(intertr= multitr ->second.begin(); intertr != multitr ->second.end(); intertr ++)
                 cout<< multitr ->first<<" "<<intertr->first<<" ("<< intertr -> second <<")"<<endl;
    }

## **六、multimap** ##

multimap允许重复键值的存在，当同一个键对应多个值是可以使用。由于一对多关系，取消的\[\]的取值方法。  
**插入方法：**

std::multimap<char,int> mymultimap;
    mymultimap.insert(std::make_pair('a',10)); //需要以pair方式插入

**取值方法：**  
利用lower\_bound和upper\_bound方法取值。lower\_bound(k) 查找第一个与键 k 关联的值，而 upper\_bound(k) 是查找第一个键值比 k 大的元素。

#include <iostream>
    #include <map>
    int main ()
    {
      std::multimap<char,int> mymultimap;
      std::multimap<char,int>::iterator it,itlow,itup;
      mymultimap.insert(std::make_pair('a',10));
      mymultimap.insert(std::make_pair('b',121));
      mymultimap.insert(std::make_pair('c',1001));
      mymultimap.insert(std::make_pair('c',2002));
      mymultimap.insert(std::make_pair('d',11011));
      mymultimap.insert(std::make_pair('e',44));
      itlow = mymultimap.lower_bound ('b');  // itlow points to b
      itup = mymultimap.upper_bound ('d');   // itup points to e (not d)
      // print range [itlow,itup):
      for (it=itlow; it!=itup; ++it)
        std::cout << (*it).first << " => " << (*it).second << '\n';
      return 0;
    }

利用equal\_range方法，该函数查找所有与 k 关联的值。返回迭代指针的 pair，它标记开始和结束范围。

#include <iostream>
    #include <map>
    
    int main ()
    {
      std::multimap<char,int> mymm;
    
      mymm.insert(std::pair<char,int>('a',10));
      mymm.insert(std::pair<char,int>('b',20));
      mymm.insert(std::pair<char,int>('b',30));
      mymm.insert(std::pair<char,int>('b',40));
      mymm.insert(std::pair<char,int>('c',50));
      mymm.insert(std::pair<char,int>('c',60));
      mymm.insert(std::pair<char,int>('d',60));
    
      std::cout << "mymm contains:\n";
      for (char ch='a'; ch<='d'; ch++)
      {
        std::pair <std::multimap<char,int>::iterator, std::multimap<char,int>::iterator> ret;
        ret = mymm.equal_range(ch);
        std::cout << ch << " =>";
        for (std::multimap<char,int>::iterator it=ret.first; it!=ret.second; ++it)
          std::cout << ' ' << it->second;
        std::cout << '\n';
      }
    
      return 0;
    }

**遍历：**

multimap<int,int> a;
    a.insert(pair<int,int>(1,a));
    a.insert(pair<int,int>(1,b));
    a.insert(pair<int,int>(1,c));
    a.insert(pair<int,int>(2,d));
    a.insert(pair<int,int>(2,e));
    
    multimap<int,int>::iterator p_map;
    pair<multimap<int,int>::iterator, multimap<int,int>::iterator> ret;
    
    for(p_map = a.begin() ; p_map != a.end();)
    {
        cout<<p_map->first<<" =>";
        ret = a.equal_range(p_map->first);
        for(p_map = ret.first; p_map != ret.second; ++p_map)
            cout<<""<< (*p_map).second;
        cout<<endl;
    }