STL容器-map P3613【深基15.例2】寄包柜 普及-

题目来源：洛谷题库

map例题

P3613【深基15.例2】寄包柜 普及-
题意

根据数据插入/查询

思路

map键值对可以根据柜子编号查找物品，但是柜子又有很多个，考虑数组或者map数组或者vector

数据约束

暂无

参考代码

#include <bits/stdc++.h>
#include <map>
using namespace std;
const int N = 100005;
int main() {//错误示范，主要是内存开销大导致溢出而出错，如果N小就没问题 
//    map<int,int> m[N];
//   int n,q;//q表示询问次数 
//   int op,i,j,k;//操作数、柜子i,格子j 
//   cin>>n>>q;
//   while(q--){
//   	cin>>op;
//   	if(op==1){
//   		cin>>i>>j>>k;
//   		m[i][j]=k; 
//	   }else{
//	   	cin>>i>>j;
//	   	cout<<m[i][j]<<endl;
//	   }//方法一：直接给键值对的内容留一定的空间，占用不同的地址即可map<int,int> m;int n,q;//q表示询问次数 int op,i,j,k;//操作数、柜子i,格子j cin>>n>>q;while(q--){cin>>op;if(op==1){cin>>i>>j>>k;m[i*N+j]=k; }else{cin>>i>>j;cout<<m[i*N+j]<<endl;}}//方法二：vecot<map>vector<map<int, int>> m(N);  // 使用 vector 动态分配 map 数组int n, q;int op, i, j, k;cin >> n >> q;while (q--) {cin >> op;if (op == 1) {cin >> i >> j >> k;m[i][j] = k;  // 更新柜子 i 中的格子 j 的值} else {cin >> i >> j;cout << m[i][j] << endl;  // 输出柜子 i 中格子 j 的值}}return 0;
}

map知识点

map

特点：

• 有序存储：根据键（key）对元素自动排序。
• 键值对存储：每个元素都是一个键值对（key-value），你可以通过键来查找值。
• 查找/插入高效 O(log n)：通过键可以非常快速地查找对应的值。

例子：
想象你在一个图书馆找书，书架上的书按照编号顺序排列。如果你知道书的编号，你可以直接找到书的位置。图书馆工作人员能根据书名快速帮你找到对应的编号（键），从而查找书籍（值）。

在C++中，map（也称为关联容器或红黑树）是一种关联容器，它按照键值对（关键字和值）存储元素，容器元素是按照关键字排序，并且不允许有多个元素的关键字相同。通过键进行快速查找、插入和删除。

使用注意：

• 第一个可以称为关键字(key)，每个关键字只能在map中出现一次，第二个可能称为该关键字的值(value) ; 例如: map<string,int> a;可以将字符串映射为整数，map<double,int>a;可以将双精度浮点数映射为整数。
• multimap允许存储相同键的元素
• map中的元素是一对数据︰<关键字,数值>，这个概念在STL中有专门的数据结构叫pair，有一个相关函数make_pair和两个成员名first,second。可以直接类似Pair修改map的值
• 不能修改map容器的关键字。map是按照关键字排序，当关键修改，容器不会重新调整排序，于是容器的有序性会被破坏，再再容器上进行查找等操作是会得到错误结果
• map 是一个基于红黑树（或其他平衡树）的数据结构，每个 map 会为每个键值对分配内存。因此，map 的内存占用不仅仅是存储键值对的数据，还包含树结构的指针等开销。具体的内存占用取决于 map 中存储的元素数量和每个元素的大小。 map<int,int> m[N];可能单个数据就占16个字节 所以一般不用而是用vector<map<int, int>> m(N)代替

map的常用用法

1、创建map实例：

//这里的KeyType是唯一的标识符类型，ValueType是存储的数据类型。
map<KeyType, ValueType> myMap;

2、插入元素：

如果键已存在，新值会覆盖旧值。

//方法一
myMap.insert({key, value});
//方法二-类似于数组，只是map的下表是键而非自增整数
myMap[key] = value;
//方法三：直接 插入pair即可
myMap.insert(make_pair("wsad",6));
myMap.insert(pair<string,int>("jkluio",10086));

3、查找元素：

find()返回指定关键字的位置迭代器，指向键对应的元素,如不存在迭代器会指向map.end()。

map<type1,type2>::iterator it = myMap.find(key);
if (it != myMap.end()) {cout << "Value: " << it->second << endl;
}

4、遍历map：

//迭代器
map<string, int>::iterator it;
for(it=mp.begin();it!=mp.end();it++){cout<<it->first<<" "<<it->second<<endl;}

这会遍历整个map，打印出所有的键值对。

5、删除元素

如果键存在，元素会被删除；如果使用迭代器删除，必须确保迭代器指向map中的元素。

map<string, string> dictionary;    // 创建一个 map，键是 string，值是 string// 插入一些键值对dictionary["apple"] = "A fruit that is red, green, or yellow.";dictionary["banana"] = "A yellow fruit that is long and curved.";dictionary["cat"] = "A small domesticated carnivorous mammal.";// 查找并输出键 "apple" 对应的值map<string, string>::iterator it = dictionary.find("apple");if (it != dictionary.end()) {cout << "Found: " << it->first << " -> " << it->second << endl;} else {cout << "apple: Not found!" << endl;}// 检查某个键是否存在并删除它if (dictionary.find("banana") != dictionary.end()) {cout << "Deleting banana..." << endl;dictionary.erase("banana");} else {cout << "banana: Not found, cannot delete!" << endl;}// 再次查找并输出剩下的元素cout << "\nRemaining items in the dictionary:" << endl;for (map<string, string>::iterator it = dictionary.begin(); it != dictionary.end(); ++it) {cout << it->first << ": " << it->second << endl;}

例题：

​