map的用法
其实，如果是做算法题目的话，c++是一定需要掌握的语言（对于纯c来讲，也许真正的c大师完全可以纯手撸出来）。现在，自己简单记录下c++中基本的数据结构的用法，今天重点回忆map。
map的基本概念不用解释，就是简单的”key”，”value”嘛，主要看操作。
声明
map<int, int> m; // 声明存储两个整型的key value
map<string, int> m;// decliam a map with string key typo and value int typo
遍历
我认为每一个数据结构都有自己的遍历方式，这是必须掌握的一种机制。使用c++的遍历呢，我们不能忘记iterator。
map<string, int> m;
m["yubo"] = 1;
m["hechun"] = 2;
map<string, int>::iterator iter = m.begin();
while(iter != m.end()){
cout<< iter->first << ":" << iter->second <<endl;
iter++;
}
/* 还可以使用for
map<string, int>::iterator iter = m.begin();
for(; iter != m.end(); iter++)
cout<< iter->first<< ":"<<iter->second<<endl;
*/
使用for需要注意的地方就是，判断条件不能使用”<”（在迭代中）
begin(), end() 默认以key排序
哈哈，非常有意思！起初我还以为map是类似栈式的管理，看来真实贻笑大方了。目前来说，map这个数据结构可以按照key的值自动排序。当然，这个排序你可以使用，也可以不使用；既可以这样排序，也可以那样排序！有意思啊
另外注意的就是，end()指针没有指向元素，如果，特定需要end()的元素，需要提前减1.
map<string, int> m;
m["yubo"] = 1;
m["hechun"] = 2;
map<string, int>::iterator _start, _end;
_start = m.begin();
_end = m.end();
_end--;
cout << _start->first<<endl;
cout << _end->first << endl;
结果先输出”hechun”，再输出”yubo”
擦除
以上面代码为例的话，就是删除遍历指针
m.erase(_start)
查找元素
map<string,int>::iterator itr=m.find(val); //Gives the iterator to the element val if it is found otherwise returns m.end() .
Ex: map<string,int>::iterator itr=m.find("Maps"); //If Maps is not present as the key value then itr==m.end()."")
更新元素
还是使用遍历指针：
访问元素
To get the value stored of the key “MAPS” we can do m[“MAPS”] or we can get the iterator using the find function and then by itr->second we can access the value.
插入键值对
使用 `std::pair<string, int>()，还可以参观这个 article
综合练习
首先输入一个数字，代表后面有几个输入行：
7
1 Jesse 20
1 Jess 12
1 Jess 18
3 Jess
3 Jesse
2 Jess
3 Jess
其中，’1’代表插入姓名和成绩，当然有多个相同，需要自己更新的。’2’代表删除该学生的信息，’3’代表查询该学生的成绩。 Solution:
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
map<std::string, int> m;
int n, type;
cin >> n ; // nums of query
for(int i = 0; i < n;i++){
string name;
int marks;
cin >> type; // the first type on per line
if (type == 1){
cin >> name >> marks; // how to iter and update value
map<string,int>::iterator iter = m.find(name);
if(iter == m.end())
m.insert(std::pair<string, int>(name, marks));
// maybe use
else
iter->second += marks; // update value
}
else if (type == 2){
cin >> name;
m.erase(name);
} else {
cin >> name;
cout << m[name] << endl; //
}
}
return 0;
}
其中，插入元素那里值得注意，上面的方法使用m.insert(std::pair<string, int>(name, marks)),
还可以使用make_pair()的方法, 注意，这里没有 <>.
unordered_map
前面介绍的map是一个唯一键的有序序列，而在unordered_map中键可以以任何顺序存储，所以是无序的。Map是作为平衡的树结构实现的，这就是为什么可以维护元素之间的顺序(通过特定的树遍历)。map操作的时间复杂度为O(Log n)，而对于unordered_map，平均为O(1)。
以下代码如同map的代码一样，没有什么特别的地方。
#include <unordered_map>
#include <iostream>
using namespace std;
int main() {
unordered_map<string, int> umap;
// insert values by using "[]" operator
// 当然 还可以使用make::pair的形式插入进去 umap.insert(make_pair("e", 2.718));
umap["vimer"] = 10;
umap["test"] = 11;
umap["lele"] = 12;
for(const auto &entry : umap){ // 使用引用的方式 省去copy的开销
cout << entry.first <<" " <<entry.second << endl;
}
}
如果value值为其他容易，在插入新值之前，需要先做初始化。如下:
using namespace std;
int main() {
unordered_map<string, vector<int>> keys;
keys["a"] = vector<int>(); // Initialize key with all null vector
keys["a"].push_back(1);
keys["a"].push_back(2);
for (const int &x : keys["a"]){
cout << x << endl;
}
}
或者其他类似的:
drawQueue.insert(std::make_pair(type, std::vector<Object*>()));
// If using C++11, the previous statement can be simplified to:
drawQueue.emplace(type, std::vector<Object*>());
参考这里
下面介绍几个API。
count
这个方法可以看成测试某一个keys是否存在map容器中， 如下:
#include <iostream>
#include <string>
#include <unordered_map>
int main ()
{
std::unordered_map<std::string,double> mymap = {
{"Burger",2.99},
{"Fries",1.99},
{"Soda",1.50} };
for (auto& x: {"Burger","Pizza","Salad","Soda"}) {
if (mymap.count(x)>0)
std::cout << "mymap has " << x << std::endl;
else
std::cout << "mymap has no " << x << std::endl;
}
return 0;
上面的代码摘自c++.com c++实在是太变态了。