C++ STL map使用
Map是STL的一个关联容器Associative Container，它提供一对一（key-value，每个key只能在这个map中只出现一次）的数据处理能力。map内部自建一颗红黑树(一种非严格意义上的平衡二叉树)，这棵树具有对数据自动排序的功能，所以在map内所有的数据都是有序的。自动按Key升序排序。
特点是增加和删除节点对迭代器的影响很小，除了那个操作节点，对其他的节点都没有什么影响。对于迭代器来说，可以修改value，而不能修改key。
map在空间上的特性：由于map的每个数据对应红黑树上的一个节点，这个节点在不保存你的数据时，是占用16个字节：一个父节点指针，左右两个孩子指针，还有一个枚举值（标示红黑的，相当于平衡二叉树中的平衡因子）。
#include <map>
using namespace std;
//两个模板参数
//map<索引类型,存储对象类型>
map<int, string> map1;
增
map1.insert(pair<int, string>(2, "item_two"));
map1.insert(map<int, string>::value_type (2, "item_two"));
map1[2]="item_two";
前两种涉及唯一性，重复插入key相同的节点是会失败的；而第三种可以增也可以改（覆盖key值对应的value）。
- 验证是否insert成功
//true 成功 false 失败
pair<map<int, string>::iterator, bool> check_pair;
check_pair = map1.insert(map<int, string>::value_type (2, "item_two"));
遍历
最后一节点map1.end() 实际是空。
-
前向迭代器 后向迭代器
key：it->first
value：it->second -
数组 index from 1
map1[index] -
C++11 auto
见题解
map<int, string>::iterator it;
for(it= map1.begin(); it!= map1.end(); it++)
map<int, string>::reverse_iterator rit;
for(rit= map1.rbegin(); rit!= map1.rend(); rit++)
for(int nindex = 1; nindex <= map1.size(); nindex++)
删
STL容器分顺序容器Sequence Container（包含vector，deque，list容器）和关联容器Associative Container（包含set，multiset，map，multimap容器）。
C++标准库中，Sequence Container的erase函数会返回iterator，但Associative Container不返回iterator。
所以使用map1.erase(it++)而不是直接map1.erase(it)
iterator erase(iterator it);//通过一个条目对象删除
iterator erase(iterator first，iterator last);//删除一个范围
map1.erase(++map1.begin(), map1.end());//剩下第1个节点
size_type erase(const Key&key);//通过关键字删除
int result = map1.erase(); // 删除了会返回1，否则返回0
map1.clear();//就相当于map1.erase(map1.begin(),map1.end());
/**
* 删除map中所有元素为str的数据
reference：https://m.jb51.net/article/116546.htm
*/
void deleteKeyStr(map<int, string *> &map1, const string str) {
map<int, string *>::iterator it;
int i_Total = 0;
for (it = map1.begin(); it != map1.end();) {
if (*(it->second) == str) {
cout << *(it->second) << " ";
//一定要先释放内存的控制
delete it->second;
it->second = NULL;
//再删除迭代
map1.erase(it++);
++i_Total;
} else {
it++;
}
}
}
改
// 方式1：
mapStu1[2] = "Mike";
// 方式2：
map<int, string>::iterator my_Iter;
my_Iter->second = "Zilla";
查 Log2(n) by key
lower_bound(key): 返回map中第一个大于或等于key的迭代器指针
upper_bound(key): 返回map中第一个大于key的迭代器指针
iterator upper_bound (const key_type& k);
const_iterator upper_bound (const key_type& k) const;
iterator lower_bound (const key_type& k);
const_iterator lower_bound (const key_type& k) const;
// 方式1
string str = map1[2];
// 方式2
map<int, string>::iterator my_Iter;
my_Iter = map1.find(3);//find(key)
string str = my_Iter->second;
排序
STL中默认采用小于号来升序排序，key为int、string不需要重载。
-
重载运算符< （对set也适用）
// reference:https://www.cnblogs.com/freebird92/p/3968295.html
struct StudentInfo
{
int nID;
string strName;
bool operator <(const tagStudentInfo &A) const
{
if (nID < A.nID) return true; //先比较nID
if (nID == A.nID) return strName.compare(A.strName) < 0; //nID相同时，再比较strName
return false;
};
我的题解PTA1002
#include <stdio.h>
#include <map>
using namespace std;
int main() {
int a_num, b_num;
int ex;
float co;
map<int, float> res;
while (scanf("%d", &a_num) != EOF) {
res.clear();
map<int, float>::iterator iter;
for (int i = 0; i < a_num; ++i) {
scanf("%d%f", &ex, &co);
res.insert(make_pair(ex, co));
}
scanf("%d", &b_num);
for (int i = 0; i < b_num; ++i) {
scanf("%d%f", &ex, &co);
iter = res.find(ex);
if (iter == res.end())
res.insert(make_pair(ex, co));
else
iter->second += co;
}
for (auto it = res.begin(); it != res.end();) {
if (it->second == 0.0f)
res.erase(it++);
else
it++;
}
printf("%u", res.size());
if (res.empty()) {
printf("\n");
continue;
}
map<int, float>::reverse_iterator rit_next;
for (auto rit = res.rbegin(); rit != res.rend(); rit++) {
rit_next = ++rit;
rit--;
if (rit_next != res.rend())
printf(" %d %.1f", rit->first, rit->second);
else
printf(" %d %.1f\n", rit->first, rit->second);
}
}
return 0;
}
另附灰灰公众号的题解
看了别人的题解。。。我在折腾什么哦?_?
输出格式折腾成这样。。。
原来不需要循环输入输出啊。。。
term数为coefficient不为0的数量
输出判断是不是0就好啊
假装是为了学习map('Д`)ノ⌒
#include <stdio.h>
#include <map>
using namespace std;
int main() {
int a_num, b_num,ex;
float co;
map<int, float> res;
while (scanf("%d", &a_num) != EOF) {
res.clear();
map<int, float>::iterator iter;
for (int i = 0; i < a_num; ++i) {
scanf("%d%f", &ex, &co);
res.insert(make_pair(ex, co));
}
scanf("%d", &b_num);
for (int i = 0; i < b_num; ++i) {
scanf("%d%f", &ex, &co);
iter = res.find(ex);
if (iter == res.end())
res.insert(make_pair(ex, co));
else
iter->second += co;
}
for (auto it = res.begin(); it != res.end();) {
if (it->second == 0.0f)
res.erase(it++);
else
it++;
}
printf("%u", res.size());
for (auto rit = res.rbegin(); rit != res.rend(); rit++) {
printf(" %d %.1f", rit->first, rit->second);
}
printf("\n");
}
return 0;
}
map的基本操作函数：
begin() 返回指向map头部的迭代器
clear(） 删除所有元素
count() 返回指定元素出现的次数
empty() 如果map为空则返回true
end() 返回指向map末尾的迭代器
equal_range() 返回特殊条目的迭代器对
erase() 删除一个元素
find() 查找一个元素
get_allocator() 返回map的配置器
insert() 插入元素
key_comp() 返回比较元素key的函数
lower_bound() 返回键值>=给定元素的第一个位置
max_size() 返回可以容纳的最大元素个数
rbegin() 返回一个指向map尾部的逆向迭代器
rend() 返回一个指向map头部的逆向迭代器
size() 返回map中元素的个数
swap() 交换两个map
upper_bound() 返回键值>给定元素的第一个位置
value_comp() 返回比较元素value的函数