C++算法与数据结构之map

管理元素集合的STL容器大致分为两类。一类是有顺序的集合，称为序列式容器；另一类是经过排序的集合，称为关联式容器。

序列式容器会将新添加的元素置于特定为位置，这个位置由插入的时间和地点决定，与元素本身的值无关。前面介绍过的vector和list就是很有代表性的序列式容器。

相对地，关联式容器会依据特定的排序标准来决定要添加的元素的位置。STL为用户提供了set、map、multiset、multimap容器。

关联式容器会在管理数据的过程中，自动给元素排序。虽然序列式容器也能进行排序，但是关联式容器的优势在于，开源随时采用二分搜索法，搜索元素的效率极高。

map是以键与值的组合为元素的集合。每个元素拥有一个键和一个值，集合以键作为排序标准。这里的map和python中的dict类似，各元素的键唯一，不存在重复。map可以看作是一种能使用任意类型元素作为下标的关联式容器。

map的用法：

函数名	功能	复杂度
size()	返回map中的元素数	O(1)
clear()	清空map	O(1)
begin()	返回指向map开头的迭代器	O(1)
end()	返回指向map末尾的迭代器	O(1)
insert((key, value))	向map中插入元素(key, value)	O(logn)
erase(key)	删除键值为key的元素	O(logn)
find(key)	搜索与key一致的元素，并且返回指向该元素的迭代器。 若没有与key键值一致的元素，则返回end()	O(logn)

map与set一样，也是通过平衡二叉树来实现的。因此元素的插入、删除、搜索的复杂度都是O(logn)

下面的一串代码演示了map的几种基本用法

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

void print(map<string, int> T)
{
    map<string, int>::iterator it;
    cout<<T.size()<<endl;
    for(it = T.begin(); it!=T.end();it++)
    {
        pair<string, int> item = *it;
        cout<<item.first<<" --> "<<item.second<<endl;

    }
}

int main()
{
    map<string, int>T;
    T["red"] = 32;
    T["blue"] = 688;
    T["yellow"] = 122;

    T["blue"] += 312;

    print(T);

    T.insert(make_pair("zebra", 101010));
    T.insert(make_pair("white", 0));
    T.erase("yellow");

    print(T);

    pair<string, int> target = *T.find("red");
    cout<<target.first<<" --> "<<target.second<<endl;

}

在上面这串代码里面，pair是STL提供的结构体模板，其第一个元素可以用first访问，第二个元素可以用second访问。

map<string, int> T 是一个声明，用于生成关联数组，该关联数组管理以string为键的int元素。

map容器可以像数组一样，用”[ ]”来进行访问，并进行读写操作。当然也可以用迭代器来顺次访问每一对键和值。

利用map，我们可以更方便地实现

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_C

这个题目。当初我们是用散列法来完成这个题目的，现在我们用map来做的话，只需要这样做：

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


int main()
{
    int n;
    cin>>n;
    map<string, bool> m;
    string cmd,ipt;
    for(int i=0;i<n;i++)
    {
        cin>>cmd;
        if(cmd[0]=='i')
        {
            cin>>ipt;
            m[ipt] = true;
        }
        else
        {
            cin>>ipt;
            if(m[ipt])
                cout<<"yes"<<endl;
            else cout<<"no"<<endl;
        }
    }
}

这里就是把key设成字符串，然后值设为一个bool变量。由于bool默认是false的，所以，就可以很方便地实现一个字典的查找功能。