pair类型
定义和初始化
有以下三种方法，
头文件#include<utility>
pair<T1, T2> p;
pair<T1, T2> p(v1, v2);
make_pair(v1, v2)
pair操作
p.first
p.second
#include <stdio.h>
#include <string.h>
#include <string>
#include <utility>
using namespace std;
int main(){
pair<int, string> p1(0, "Hello");
printf("%d, %s\n", p1.first, p1.second.c_str());
pair<int, string> p2 = make_pair(1, "World");
printf("%d, %s\n", p2.first, p2.second.c_str());
return 0;
}
class Solution {
public:
int firstUniqChar(string s) {
unordered_map<char, pair<int, int>> m;
int idx = s.size();
for (int i = 0; i < s.size(); i++) {
m[s[i]].first++;
m[s[i]].second = i;
}
for (auto &p : m) {
if (p.second.first == 1) idx = min(idx, p.second.second);
}
return idx == s.size() ? -1 : idx;
}
};
map对象的定义和初始化
map是键-值对的组合，有以下的一些定义的方法：
map<k, v> m;
map<k, v> m(m2);
map<k, v> m(b, e);
上述第一种方法定义了一个名为m的空的map对象；第二种方法创建了m2的副本m；第三种方法创建了map对象m，并且存储迭代器b和e范围内的所有元素的副本。
map的value_type是存储元素的键以及值的pair类型，键为const。
map对象的一些基本操作
map中元素的插入
在map中元素有两种插入方法：
- 使用下标
- 使用insert函数
在map中使用下标访问不存在的元素将导致在map容器中添加一个新的元素, insert函数的插入方法主要有如下：
m.insert(e)
m.insert(beg, end)
m.insert(iter, e)
上述的e一个value_type类型的值。beg和end标记的是迭代器的开始和结束。
两种插入方法如下面的例子所示：
#include <stdio.h>
#include <map>
using namespace std;
int main(){
map<int, int> mp;
for (int i = 0; i < 10; i ++){
mp[i] = i;
}
for (int i = 10; i < 20; i++){
mp.insert(make_pair(i, i));
}
map<int, int>::iterator it;
for (it = mp.begin(); it != mp.end(); it++){
printf("%d-->%d\n", it->first, it->second);
}
return 0;
}
map中元素的查找和读取
注意：上述采用下标的方法读取map中元素时，若map中不存在该元素，则会在map中插入。
因此，若只是查找该元素是否存在，可以使用函数count(k)，该函数返回的是k出现的次数(只有0和1)；若是想取得key对应的值，可以使用函数find(k)，该函数返回的是指向该元素的迭代器。
上述的两个函数的使用如下所示：
#include <stdio.h>
#include <map>
using namespace std;
int main(){
map<int, int> mp;
for (int i = 0; i < 20; i++){
mp.insert(make_pair(i, i));
}
if (mp.count(0)){
printf("yes!\n");
}else{
printf("no!\n");
}
map<int, int>::iterator it_find;
it_find = mp.find(0);
if (it_find != mp.end()){
it_find->second = 20;
}else{
printf("no!\n");
}
map<int, int>::iterator it;
for (it = mp.begin(); it != mp.end(); it++){
printf("%d->%d\n", it->first, it->second);
}
return 0;
}
从map中删除元素
从map中删除元素的函数是erase()，该函数有如下的三种形式：
m.erase(k)
m.erase(p)
m.erase(b, e)
第一种方法删除的是m中键为k的元素，返回的是删除的元素的个数；第二种方法删除的是迭代器p指向的元素，返回的是void；第三种方法删除的是迭代器b和迭代器e范围内的元素，返回void。
#include <stdio.h>
#include <map>
using namespace std;
int main(){
map<int, int> mp;
for (int i = 0; i < 20; i++){
mp.insert(make_pair(i, i));
}
mp.erase(0);
mp.erase(mp.begin());
map<int, int>::iterator it;
for (it = mp.begin(); it != mp.end(); it++){
printf("%d->%d\n", it->first, it->second);
}
return 0;
}
注意迭代器失效问题，因为mp.erase(iter) 之后，iter 的结构已经改变了，此时 for 循环张的 iter++ 可能会出现问题。因此推荐下面的改法：
for (map<int, int>::iterator iter = mp.begin(); iter != mp.end(); ) {
if (iter->first == 1) mp.erase(iter++); // NOTE it is SAFE!
else iter->second++;
}
这里的删除时安全的，因为iter在删除前已经会先进行缓存一下，再传给erase去删除。因此 iter++ 是在原先的 iter 基础上进行的。这种方式也是 C++ 文档中推荐的方式。