C++ STL Map 的创建、删除、插入、更新、遍历
C++ 中map 容器提供一个键值对容器，map 与multimap 差别仅仅在于multimap允许一个键对应多个值。
map的实现是一颗红黑树，因此，map的内部键的数据都是排好序的，查找和删除、插入的效率都是lgN
map的本质其实就是映射，键值（key-value）一一对应。比如身份证号（key）和姓名（value）一一对应,map的定义格式:
std::map <key_type, value_type> 变量;
key 和value 可以是任意类型。
1、创建
#include <map>
int main(int argc, const char * argv[]) {
map<int, int> m; //这里 定义为int ，后面插入数据时key 和value 只能是int 类型。
printf("size:%lu\n",m.size());
cout << "is empty:"<< m.empty() << endl;
}
log:
size:0
is empty:1
2、插入
1) map的变量名[key] = value;
m[nums[i]] = i;// 如果键已经存在，则直接覆盖
2) 使用insert 方法
//如果键已经存在，则插入失败
m.insert(pair<int, int>(nums[i],i));
或者
m.insert(make_pair<int, int>(nums[i],i));
int main(int argc, const char * argv[]) {
map<int, int> m;
printf("size:%lu\n",m.size());
cout << "is empty:"<< m.empty() << endl;
int nums[] = {1,2,3,4,5,6,7,8,9,10};
map<int, int>::iterator it;
for (int i = 0 ; i < 10; i++) {
m.insert(pair<int, int>(nums[i],i));
// m[nums[i]] = i;
}
}
顺便说一下pair
pair是将2个数据组合成一组数据，当需要这样的需求是就可以使用pair，如STL 中的map 就是key 和value 放在一起保存。另一个应用是，当一个函数需要返回2个数据的时候，可以选择pair。pair 的实现是一个结构体，主要的两个成员变量是first、second，因为是使用struct，不是class，所以可以直接使用pair 的成员变量。
pair<int ,double> p1;
p1.first = 1;
p1.second = 2;
cout<<p1.first<<' '<<p1.second<<endl;
//输出结果：1 2
pair<int, double> p1;
p1 = make_pair(1, 1.2);
cout << p1.first << p1.second << endl;
//output: 1 1.2
3、查找和修改
map<int, int>::iterator iter1;
iter1 = m.find(nums[i]);
iter1->second = 1;
或者
int value = m[nums[i]];
m[nums[i]] = 1;
int main(int argc, const char * argv[]) {
map<int, int> m;
printf("size:%lu\n",m.size());
cout << "is empty:"<< m.empty() << endl;
int nums[] = {1,2,3,4,5,6,7,8,9,10};
map<int, int>::iterator it;
for (int i = 0 ; i < 10; i++) {
m.insert(pair<int, int>(nums[i],i));
// m[nums[i]] = i;
}
map<int, int>::iterator iter1;
iter1 = m.find(1);
int num = m[2];
printf("%d\n",num);
}
log:
size:0
is empty:1
1
4、删除
for(int i = 0;i < nums.size();i++) {
iter = m.find(nums[i]);
if(iter != m.end()) {
m.erase(iter);
}
}
5、遍历
//正向遍历
map<int, int>::iterator iter3 = m.begin();
while (iter3 != m.end()) {
printf("%d ",iter3->second);
iter3++;
}
//反向遍历
map<int, int>::reverse_iterator iter2 = m.rbegin();
while (iter2 != m.rend()) {
printf("%d ",iter2->second);
iter2++;
}
//边遍历边删除
map<char, int>::iterator iter;
iter = mMap.begin();
while (iter != mMap.end()) {
if (iter->second > 1) {
iter = mMap.erase(iter);//返回下一个元素指针来获取最新的iterator
}else {
iter++;
}
}
这是另一个算法题
int singleChar(const char* str) {
if (str == NULL) {
return -1;
}
map<char, int> mMap;
for (int i = 0; i < strlen(str); i++) {
map<char, int>::iterator iter;
iter = mMap.find(str[i]);
int count = 0;
if (iter != mMap.end()) {
count = iter->second;
}
count++;
mMap[str[i]] = count;
}
map<char, int>::iterator iter;
iter = mMap.begin();
while (iter != mMap.end()) {
if (iter->second > 1) {
iter = mMap.erase(iter);
}else {
iter++;
}
}
for (int i = 0; i < strlen(str); i++) {
map<char, int>::iterator iter;
iter = mMap.find(str[i]);
if (iter != mMap.end()) {
return i;
}
}
return -1;
}
//目前只想到这个方法
6、排序
map 的排序默认是根据key 从小到大排序。
7、其他方法
m.size();//返回元素数目
m.empty();//判断是否为空
m.clear();//清空所有元素
m.count(nums[i]);//判断某个元素是否存在，由于map 中key 不能重复，因此，返回值要么是0，要么是 1
最后实际应用：
leetcode 136 题
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
class Solution {
public:
int singleNumber(vector<int>& nums) {
map<int,int> m;
map<int,int>::iterator iter;
for(int i = 0;i < nums.size();i++) {
iter = m.find(nums[i]);
if(iter != m.end()) {
m.erase(iter);
}else {
m.insert(pair<int,int>(nums[i],i));
}
}
iter = m.begin();
int ret = 0;
ret = iter->first;
return ret;
}
};
int main(int argc, const char * argv[]) {
map<int, int> m;
int nums[] = {1,2,3,4,5,6,7,8,9,10};
map<int, int>::iterator it;
for (int i = 0 ; i < 10; i++) {
m.insert(pair<int, int>(nums[i],i));
}
vector<int> n = {2,2,1};
Solution *s1 = new Solution();
int ret1 = s1->singleNumber(n);
printf("%d\n",ret1);
printf("\n");
return 0;
}
还是有高手厉害：
异或运算满足以下定律：（离散数学有详解）
交换律： a ^ b ^ c <=> a ^ c ^ b
任何数与0异或 0 ^ n = n
相同的数异或为0 n ^ n = 0
0^0 = 0，
1^0 = 1，
0^1 = 1，
1^1 = 0
根据三条定律，用0与数组中所有元素分别异或，最后会得到没有相同的那个数。
int singleNumber(vector<int>& nums) {
int result = 0;
for(int e : nums)
{
result ^=e;
}
return result;
}
复习一下：
按位与运算（&）
运算规则：
0&0=0;
0&1=0;
1&0=0;
1&1=1;
| 按位或运算（ | ） |
运算规则：
0|0=0；
0|1=1；
1|0=1；
1|1=1；
异或运算符（^）
运算规则：
0^0=0；
0^1=1；
1^0=1；
1^1=0；
取反运算符（~）
运算规则：
~1=0；
~0=1；
使一个数的最低位为零，可以表示为：a&~1。
~1的值为1111111111111110，再按“与”运算，最低位一定为0。因为“~”运算符的优先级比算术运算符、关系运算符、逻辑运算符和其他运算符都高。
复合赋值运算符
位运算符与赋值运算符结合，组成新的复合赋值运算符，它们是：
&= 例：a &=b 相当于a=a& b
|= 例：a |=b 相当于a=a |b
>>= 例：a >>=b 相当于a=a>> b
<<= 例：a<<=b 相当于a=a<< b
^= 例：a ^= b 相当于a=a^ b
参考：
[1]:https://blog.csdn.net/xiaopihaierletian/article/details/78162863