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的，所以，就可以很方便地实现一个字典的查找功能。
腾讯云开发者
