C 关联容器

关联容器和顺序容器的本质区别：关联容器是通过键存取和读取元素、顺序容器通过元素在容器中的位置顺序存储和访问元素

pair类型

：初始化-------在头文件utility中

pair p1;                       创建一个pair对象，两个元素的类型分别是T1,T2类型，采用初值进行初始化

pair p1(v1,v2);             创建一个pair对象，两个元素的类型分别是T1,T2类型，采用v1,v2分别进行初始化

make_pair(v1,v2);                     以v1、v2的只进创建一个pair对象，类型分别是v1、v2的类型

p.first                                      返回p中第一个公有数据成员

p.second                                 返回p中第二个公有数据成员

例子程序

#include<iostream>
#include<string.h>
#include<vector>
#include<map>
#include<utility>
using std::cout;
using std::string;
using std::cin;
using std::endl;
using std::pair;
using std::make_pair;
using std::vector;
using std::map;
int main()
{
    pair<string,int> next_auth;

    vector<pair<string,int> > all;
    vector<pair<string,int> >::iterator iter;

    string first;
    int last;
    while(cin>>first>>last)
        all.push_back(make_pair(first,last));

    cout<<"the element of the vector "<<endl;
    for(iter=all.begin();iter!=all.end();iter++)
        cout<<iter->first<<" "<<iter->second<<endl;
    return 0;
}

结果：

关联容器

对于关联容器不提供front、push_front、pop_front、back、push_back以及pop_back，此外对于关联容器不能通过容器大小来定义，因为这样的话将无法知道键所对应的值什么。对于关联容器有：map、set、multimap、multiset

@ map

：关联数组，通过键来存储和读取

：初始化

           map   m1              创建一个名m的空的map对形象，对其键和值的类型分别为k、v

           map  m(m2)         创建m2的副本m,m与m2的类型必须相同的键值类型和值类型

           map   m(b,e)         创建map类型的对象m，存储迭代器b和e标记范围内所有元素的副本，元素的类型必须转换为pair

：对于map中的键值要求类型一致并且有一个相关的比较函数,在默认情况下可以理解为键类型数据上的“小于”关系。-----严格的“弱”排序

：map定义的类型

          map::key_type            在map中的做索引的键的类型

          map::mapped_type      在map中的键所关联的值的类型

          map::value_type         一个pair类型,它的first元素具有const map::key_type类型，它的second元素则为map::mapped_type 

对map迭代器解引用将产生pair类型它的第一个元素是const类型的，第二个元素的成员可以修改

：给map添加成员

         1>使用下标访问map对象:在map对象查找键值为x的元素如果找到则返回它的值（类型是map::mapped_type），否则插入一个新的对象键值为x,值为map中v的默认初值

         2>使用Insert对map进行插入：

              m .insert(e)                e是一个用在m上的value_type类型的值，如果e.first不在m中则插入一个值为.second的新元素，否则该键值在m中已经存在则保持不变，该

                                               函数返回一个pair新类型，包含一个指向键值为e.first的元素的map迭代器，以及一个bool类型的对象，表示是否插入该元素               

              m.insert(beg,end)       插入beg、end标记范围内的元素，如果该元素的m.first已经存在则不插入否则插入。返回void类型

              m.insert(iter,e)           如果e.first不在m中，则创建新元素，并以迭代器iter为起点搜索新元素的存储位置，否则返回一个迭代器，指向m中具有的给定键的元素。

        3>查找和读取map中的元素：

            m.count(k)                 返回k在m中出现的次数，在map中只是返回0、1

            m.find(k)                    如果k在m中的键值存在则返回相应的迭代器，否则返回超出来末端迭代器

       4>从map中删除元素

           使用erase与顺序容器功能一样

例子程序

#include<iostream>
#include<string.h>
#include<vector>
#include<map>
#include<utility>
using std::cout;
using std::string;
using std::cin;
using std::endl;
using std::pair;
using std::make_pair;
using std::vector;
using std::map;
int main()
{
    pair<string,int> next_auth;

    vector<pair<string,int> > all;
    vector<pair<string,int> >::iterator iter;

    string first;
    int last;
    cout<<"the element of the map "<<endl;
    map<string,int> ok;//对于map中值的存储是根据若排序进行的，因此，ok的begin的对象始终是jk--3/2
    ok["jk"]=3;
    ok["jk"]=2;
    ok["ok"]=4;
    if(!ok.empty()) {
        map<string,int>::iterator map_it=ok.begin();
        cout<<map_it->first<<" "<<map_it->second<<endl;
    }
    string key;
    while(cin>>key)//对于map中所有值得初值是1,如果多次出现相同的string类型的值，则从1开始累加
        ++ok[key];

    ok.insert(map<string,int>::value_type("anna",67));
    ok.insert(make_pair("gyeve",5));

    while(cin>>key)
    {
        pair<map<string,int>::iterator,bool > ret = ok.insert(make_pair(key,1));
        if(!ret.second)
            ++ret.first->second;
    }
    cin>>key;
    cout<<"the avaiable:"<<endl;
    cout<<ok.count(key)<<endl;
    map<string,int>::iterator it=ok.find("gyeve");
    if(it!=ok.end()){
        cout<<it->second<<endl;
        ok.erase(it);
        cout<<ok.count("gyeve")<<endl;
    }
    /*查找map中的值：下标、count、find 其中如果在使用下标查找的过程中没有该值就会添加*/

    return 0;
}

结果：

@set

：大小可变的集合，支持通过键值实现的快速读取。对于单纯想知道一个值是否存在则set容器最适用

：在set容器中value_type不是pair类型，而是与key_value的类型相同，它的键值类型也是唯一的且不能修改

：在set也支持find、count、insert、erase操作

例子程序

#include<set>
#include<vector>
#include<iostream>
#include<string>
using std::cin;
using std::cout;
using std::set;
using std::vector;
int main()
{
    vector<int> vec;
    for(vector<int>::size_type i=0;i<10;i++)
    {
        vec.push_back(i);
        vec.push_back(i);
    }
    set<int> iset(vec.begin(),vec.end());
    cout<<"the len of the vector "<<vec.size()<<std::endl;
    cout<<"the len of the set "<<iset.size()<<std::endl;
    return 0;
}

结果：

@multimap

：支持同一个键多次出现的map类型，multimap不能支持下标操作

@multiset

：支持同一个键值多次出现的set类型

在multimap、multiset 中查找元素------注意对多情况的处理

1>使用find、count操作

-----count将对应键值的数目反馈

-----将与键值第一个匹配的元素的迭代器反馈

代码

#include<map>
#include<iostream>
#include<string>
#include<utility>
using std::cout;
using std::cin;
using std::endl;
using std::string;
using std::multimap;
using std::pair;

typedef multimap<string,string>::iterator author_it;

int main()
{
    string name,book;
    multimap<string,string> author;

    author.insert(std::make_pair(string("Barth"),string("Sot-weed, Factor")));
    author.insert(std::make_pair(string("Barth"),string("Lost in the Funhouse")));
    author.insert(std::make_pair(string("gyeve"),string("old and yonger")));
    author.insert(std::make_pair(string("susan"),string("black and red")));
    author.insert(std::make_pair(string("gyeve"),string("sky girl")));
    author.insert(std::make_pair(string("susan"),string("goods")));
    author.insert(std::make_pair(string("susan"),string("data fame")));

    string key("Barth");
    multimap <string,string>::size_type cnt;
    cnt = author.erase(key);
    cout<<"delete the :"<<key<<" is : "<<cnt<<endl;

    cout<<"find the key form author (count,find)"<<endl;
    cnt = author.count("susan");
    multimap<string,string>::iterator it = author.find("susan");
    for(multimap<string,string>::size_type in=0;in!=cnt;in++,it++)
        cout<<"the key :"<<it->first<<" the value : "<<it->second<<endl;
return 0;
}

结果：

2>使用lower_bound、upper_bound

-----m.lower_bound(k)返回一个迭代器，指向键值不小于k的第一个元素

-----m.upper_bound(k)返回一个迭代器，指向键值不大于k的第一个元素

例子程序

#include<map>
#include<iostream>
#include<string>
#include<utility>
using std::cout;
using std::cin;
using std::endl;
using std::string;
using std::multimap;
using std::pair;

typedef multimap<string,string>::iterator author_it;

int main()
{
    string name,book;
    multimap<string,string> author;

    author.insert(std::make_pair(string("Barth"),string("Sot-weed, Factor")));
    author.insert(std::make_pair(string("Barth"),string("Lost in the Funhouse")));
    author.insert(std::make_pair(string("gyeve"),string("old and yonger")));
    author.insert(std::make_pair(string("susan"),string("black and red")));
    author.insert(std::make_pair(string("gyeve"),string("sky girl")));
    author.insert(std::make_pair(string("susan"),string("goods")));
    author.insert(std::make_pair(string("susan"),string("data fame")));
cout<<"find the key form author (lower_bound,upper_bound)"<<endl;
    author_it beg = author.lower_bound(string("susan"));
    author_it end = author.upper_bound(string("susan"));
    while(beg!=end)
    {
        cout<<"the key :"<<beg->first<<" the value : "<<beg->second<<endl;
        beg++;
    }
return 0;
}

结果：

3>使用equal_range

-----m.equal_range(k)返回一个迭代器的对象，它的first成员等价于m.lower_bound(k)、他的second成语等价于m.upper_bound(k)

例子程序

#include<map>
#include<iostream>
#include<string>
#include<utility>
using std::cout;
using std::cin;
using std::endl;
using std::string;
using std::multimap;
using std::pair;

typedef multimap<string,string>::iterator author_it;

int main()
{
    string name,book;
    multimap<string,string> author;

    author.insert(std::make_pair(string("Barth"),string("Sot-weed, Factor")));
    author.insert(std::make_pair(string("Barth"),string("Lost in the Funhouse")));
    author.insert(std::make_pair(string("gyeve"),string("old and yonger")));
    author.insert(std::make_pair(string("susan"),string("black and red")));
    author.insert(std::make_pair(string("gyeve"),string("sky girl")));
    author.insert(std::make_pair(string("susan"),string("goods")));
    author.insert(std::make_pair(string("susan"),string("data fame")));

    cout<<"find the key form author (equal_range)"<<endl;
    pair< multimap<string,string>::iterator, author_it >  result;
    result = author.equal_range(string("susan"));
    while(result.first!=result.second)
    {
            cout<<"the key :"<<result.first->first<<" the value : "<<result.first->second<<endl;
            result.first++;
    }
    return 0;
}

结果：