MAP容器

        1）概念：map 是一个容器,它用于储存数据并且能从一个数据集合中取出数据。它的数据组成包含两项,一个是它的数据值,一个是用于排序的关键字。其中关键字是惟一的,它用于将数据自动排序。而每个元素的数据值与关键字无关,可以直接改变。

         

            【重点】内部结构采用RB_TREE(红黑树)。查找复杂度：O(log2N)     

        

              multimap 跟map 特性相同，唯一的区别是允许键值重复！！！

        2）使用

             需加载的头文件:   #include<map>
                                          using namespace std;
            模板原型:
                  template <
                  class Key,                          //关键字的数据类型
                  class Type,                       //数据值的数据类型
                  class Traits = less<Key>, //提 供 比 较 两 个 元 素 的 关 键 字 来 决 定 它 们 在 map容器中的相对位置。它是可选的,它的默认值是 less<key>
                  class Allocator=allocator<pair <const Key, Type> >  //代表存储管理设备。它是可选的,它的默认值为allocator<pair <const Key, Type> >
                   >


        3）map 容器特点:
               (1)是一个相关联的容器,它的大小可以改变,它能根据关键字来提高读取数据能力。
               (2)提供一个双向的定位器来读写取数据。
               (3)已经根据关键字和一个比较函数来排好序。
               (4)每一个元素的关键字都是惟一的。
               (5)是一个模板,它能提供一个一般且独立的数据类型。

        4）有关map最详细的介绍详见资源

              STL MAP详细资源下载

        5）结合map方法给出了一个综合测试代码：

#include <cstdlib>
#include <map>
#include <iostream>
using namespace std;

map <int,char> ctr;

int print_one_item(map <int,char>::const_iterator cp)//用于打印 map 的一个元素
{
        cout<<"("<<cp->first<<" , "<<cp->second<<") ";
        
        return 0;
}

void test_equal_range()//测试equal_range()的功能
{
    //pair第一个迭代器返回第一个大于或等于给定的关键字的元素  
    //pair第二个迭代器返回第一个比给定的关键字大的元素。

    pair <map <int,char>::const_iterator, map <int,char>::const_iterator> p;
    
    p=ctr.equal_range(2);

    if(p.first!=ctr.end())
    {
        cout<<"The first element which key >= 2 is: ";
        //cout<<"("<<p.first->first<<" , "<<p.first->second<<") ";
        print_one_item(p.first); //调用子程序来打印一项
        cout<<endl;
    }
   if(p.second!=ctr.end())
   {
        cout<<"The first element which key > 2 is: ";
        cout<<"("<<p.second->first<<" , "<<p.second->second<<") ";
        cout<<endl;
    }
    
}

void creat_map()
{
      ctr.insert(pair <int,char>(1,'a'));
      ctr.insert(pair <int,char>(2,'b'));
      ctr.insert(pair <int,char>(3,'b'));
      ctr.insert(pair <int,char>(4,'c'));
      ctr.insert(pair <int,char>(5,'d'));
      ctr.insert(pair <int,char>(1,'c'));
}

void erase_map()//删除某一个元素
{
    map <int,char>::iterator cp=ctr.find(2);
    ctr.erase(cp);//删除关键值等于 2 的元素
}

void clear_map()
{
      ctr.clear();//清空 map 容器（删除全部元素）
      if(ctr.empty())//map 容器为空时
        cout<<"The container is empty"<<endl;
      else
        cout<<"The container is not empty"<<endl;
}

int print()//用于打印一个 map 容器
{
        map<int,char>::const_iterator cp;
        for(cp=ctr.begin();cp!=ctr.end();cp++)//让 cp 从 c 的开始到结束打印 cp 对应的值
                print_one_item(cp); //调用子程序来打印一个元素

        return 0;
}

void print_first_element()
{
      map <int,char>::iterator cp;//迭代器
      cp=ctr.begin(); //定位到 ctr 的开始位置
      cout<<"The first element is:"<<cp->second<<endl;//打印出第一个元素
}
void key_compare_map() //key_comp取得一个比较对象的副本以对 map 容器中的元素进行排序。
{
      map <int,int> c;
      map <int, int, less<int> >::key_compare kc = c.key_comp() ;
        if(kc( 1, 2 ))
                cout<<"kc(1,2) is true"<<endl;
        else
                cout<<"kc(1,2) is false"<<endl;

      if(kc( 2, 1 ))
                cout<<"kc(2,1) is true"<<endl;
        else
                cout<<"kc(2,1) is false"<<endl;
}
void lower_bound_map()
{
    map <int,char>::iterator cp;
   /* 返回一个指向第一个关键字的值是大于等于一个给定值的元素的定位器,或者返回指向 map 容
      器的结束的定位器
    */
    cp=ctr.lower_bound(2);//返回第一个 大于等于2的元素的定位器

    if(cp!=ctr.end())
    {
        cout<<"The first element which key >= 2 is: ";
        print_one_item(cp);//调用子程序来打印一项
        cout<<endl;
    }

}

void compare_map()
{
    map <int,char> ctr1,ctr2;
        int i;
        for(i=0;i<3;i++)
        {
                ctr1.insert(pair <int,char>(i,'a'+i));
                ctr2.insert(pair <int,char>(i,'A'+i));
        }
        if(ctr1!=ctr2)//当 ctr1 与 ct2 不同时
                cout<<"They are not equal"<<endl;
        else//当 ctr1 与 ctr2 相同时
                cout<<"They are equal"<<endl;

}
void comp_map()//两个 map 容器的大小比较是基于第一个不相同的元素的大小比较。
{              //两个 map 容器相等,当且仅当它们的元素个数相等且同一个位置上的值相等
    map <int,char> ctr1,ctr2;
    int i;
    for(i=0;i<3;i++)//下面给 ctr1 和 ctr2 赋值
    {
        ctr1.insert(pair <int,char>(i,i));
        ctr2.insert(pair <int,char>(i,i+1));
    }
    if(ctr1<ctr2)      
        cout<<"ctr1<ctr2"<<endl;
    else
        cout<<"ctr1>=ctr2"<<endl;       
}

void reverse_map()//打印 反向 map  rbegin() rend()跟 reverse_iterator同时使用
{
    map <int,char>::reverse_iterator rcp;
    for(rcp=ctr.rbegin();rcp!=ctr.rend();rcp++)
      cout<<"("<<rcp->first<<" , "<<rcp->second<<") ";

}

void swap_map()
{
    
    map <int,int> ctr1, ctr2;
    map <int,int>::const_iterator cp;
    int i;

    for(i=0;i<3;i++)//下面先给 ctr1 和 ctr2 赋值
    {
        ctr1.insert(pair <int,int>(i,i));
        ctr2.insert(pair <int,int>(i,i+10));
    }
    cout<<"Before exchange with ctr2 the ctr1 is:";
   

    for(cp=ctr1.begin();cp!=ctr1.end();cp++)//让 cp 从 c 的开始到结束打印 cp 对应的值
             cout<<"("<<cp->first<<" , "<<cp->second<<") ";
    
    cout<<endl;
    cout<<"After exchange with ctr2 the ctr1 is:";
    ctr1.swap(ctr2);//让 ctr1 的内容与 ctr2 交换
     for(cp=ctr1.begin();cp!=ctr1.end();cp++)//让 cp 从 c 的开始到结束打印 cp 对应的值
             cout<<"("<<cp->first<<" , "<<cp->second<<") ";
    cout<<endl;
}
int main()
{
          
      creat_map();
      int i;
      
      cout<<"1，测试begin()"<<endl;
      cout<<"2，测试count()求某关键字个数"<<endl;
      cout<<"3，测试test_equal_range()"<<endl;
      cout<<"4，测试erase()"<<endl;
      cout<<"5，测试key_compare_map()"<<endl;
      cout<<"6，测试lower_bound_map()"<<endl;
      cout<<"7，测试map size和 max_size(最大可能长度)"<<endl;
      cout<<"8，测试符号 [] 的作用"<<endl;
      cout<<"9，测试符号 ！= 的作用"<<endl;
      cout<<"10,测试符号 <  的作用"<<endl;
      cout<<"11,打印反向map"<<endl;
      cout<<"12,交换两个map 的值"<<endl;
      while(1)
      {       
      cin>>i;
      
      switch(i)
      {
          case 1: print_first_element(); break;
          case 2: int j;
                  j=ctr.count(1);//求出关键字为 1 的元素的个数(由于map 容器的关键字是惟一的,故它只能取 0 或者 1)
                  cout<<"The number of key 1 is: "<<j<<endl;break;
          case 3: test_equal_range(); break;
          case 4: erase_map();break;
          case 5: key_compare_map();break;
          case 6: lower_bound_map();break;
          case 7: cout<<"the size of ctr is:"<<ctr.size()<<endl;
                  cout<<"the max_size of ctr is:"<<ctr.max_size()<<endl;break;
          case 8: cout<<"before change map is:"<<endl;
                  print();
                  ctr[1]='W';//将关键字为 1的对应值变为 W
                  ctr[7];    //添加一个关键字为7 值为0的项
                  cout<<"\nafter change map is:"<<endl;
                  print();break;
                  
          case 9:compare_map();break;
          case 10:comp_map();break;
          case 11:reverse_map();break;
          case 12:swap_map(); break;
      }

      }
      map <int,char>::iterator end;//迭代器
      end=ctr.end();               //这里定位到Map 中最后一个元素后面位置，所以什么都不打印
      //end--;//这定位到最后一个元素 d  除去了重复关键字 c   
      cout<<"The last element is:"<<end->second<<endl;

      
      clear_map();

      
      return 0;
}

 再看一个map数据结构的应用（统计每个字符串出现的个数）

#include <iostream>
#include <map>
using namespace std;
int main()
{
	map <string ,int> M;
	map <string ,int>::iterator j;
	string t[5]={"abc","dd","abc","dd","dd"};
	
	for(int i=0;i<5;++i)
		M[t[i]]++;//默认是表示第二个值  而不是键
	
	for(j=M.begin();j!=M.end();++j)
		cout<<"<"<<j->first<<" ,"<<j->second<<">"<<endl;
	
	
	return 0;
}