是一个基于红黑树的平衡二叉搜索树，它存储的元素是键值对，其一是检索使用的键，其二是对应的值，其中每个键都是唯一的，且无法修改，对应的值可以修改。 map内部的数据会按照关键字以字母序自动排列。

头文件

#include

map的优势

map 和一维数组相比，主要优势如下：

动态大小：map 可以在运行时动态增长或缩小，而一维数组的大小在编译时就确定了，运行时不能改变。
键值对存储：map 存储的是键值对，可以直接通过键来访问或修改值，这对于需要快速查找、更新或删除元素的场景非常有用。而一维数组只能通过索引访问元素，如果需要通过特定的“键”来访问元素，就需要额外的逻辑来映射键到数组索引。
自动排序：map 中的元素根据键自动排序，这使得对元素进行有序遍历变得非常方便。而一维数组中的元素顺序完全取决于插入时的顺序，如果需要有序，必须手动排序。
高效的查找、插入和删除操作：由于 map 基于红黑树（一种自平衡二叉搜索树），它可以在对数时间内完成查找、插入和删除操作（O(log n)），这对于大量元素的数据集非常有效。而在一维数组中，查找（如果未排序）和删除操作通常需要线性时间（O(n)），即使是在排序数组中使用二分查找，插入和删除操作仍然需要线性时间，因为可能需要移动元素以保持数组的有序性。
灵活的键类型：map 允许使用任何可排序的类型作为键，包括自定义类型（只要为它们定义了比较函数）。而一维数组的索引通常是整数类型，如果需要使用其他类型作为“键”来访问元素，就需要额外的映射逻辑。

总之，map 提供了一种灵活、高效的方式来存储和管理键值对数据，特别适合需要动态数据集、快速查找和有序遍历的场景。而一维数组则更适合固定大小、主要通过索引访问的简单数据集。

构造

map <类型1, 类型2> 标识符;

常用函数

void insert(const value_type& value)	向 map 中插入一个键值对
iterator find(const Key& key)	返回一个指向键为 `key` 的元素的迭代器。如果找不到，则返回 map.end()
size_type erase(const key_type& key)	删除键为 key 的元素，返回删除的元素数量
void clear()	移除 map 中的所有元素
size_type count(const Key& key) const	返回具有给定键 key的元素数量
iterator begin()	返回指向 map 第一个元素的迭代器
iterator end()	返回指向 map 末尾的迭代器
bool empty() const	如果 map 为空，则返回 true
size_type size() const	返回 map 中的元素数量
mapped_type& operator[](const key_type& key)	返回键为 key 的元素的映射值的引用。如果不存在这样的元素，则会插入一个新元素
void swap(map& other)	与另一个 map 交换内容

实例

构造与插入删除

#include<bits/c++.h>
using namespace ;
template <class T1, class T2>

void printmap(const map<T1, T2> & mp) {
	for(auto it = mp.begin(); it != mp.end(); it++) {
		cout << it->first << " " << it->second << endl;
	}
}

int main(){	
	// 1、构造map
	map <int, int> mp;
	cout << "1、构造:\n"; printmap(mp); cout << endl;

	// 2、value_type插入 
	mp.insert(map<int, int>::value_type (300, 3));
	cout << "2、value_type插入:\n"; printmap(mp); 
	
	// 3、insert_pair插入 
	mp.insert(pair<int, int>(100, 3));
	cout << "3、pair插入:\n"; printmap(mp);
	
	// 4、数组插入
	mp[250] = 4; 
	cout << "4、数组插入:\n"; printmap(mp);
	
	// 5、长度函数
	cout << "5、map长度: " << mp.size() << endl; 
	
	// 6、利用迭代器删除 
	auto it = mp.find(250);
    mp.erase(it);
    cout << "6、利用迭代器删除:\n"; printmap(mp);
    
    // 7、利用键删除
	mp.erase(100); 
	cout << "7、利用键删除:\n"; printmap(mp);
	
	return 0;
}

运行结果

map排序

map默认按照键的升序排列，如果我们想按照自己的规则对map进行排序的话，是无法使用sort函数的。那么我们可以选择重载小于号或者将map里的内容放入vector进行排序。

#include<bits/c++.h>
using namespace ;

//cmp函数 按照值从小到大排序 
bool cmp (pair <string, int> p1, pair <string, int> p2) {
	return p1.second < p2.second;
}


int main(){
	// 构造mp 
	map<string, int> mp;
    // 存入数据 
	mp["zhangsan"] = 86;
    mp["lisi"] = 78;
    mp["daming"] = 92;
    mp["erha"] = 88;
    // 将map里的值 装到vector里 
	vector< pair<string, int> > vec(mp.begin(), mp.end());
	// sort排序 
	sort(vec.begin(),vec.end(),cmp);
	// 输出结果查看 
	for(auto it = vec.begin(); it!=vec.end(); it++) {
		cout << it->first << " " << it->second << endl;
	}
	return 0;
}

运行结果

#include<bits/c++.h>
using namespace ;

struct NODE {
	string name;
	int id;
	// 重载 < 排序规则  
	bool operator < (NODE const &a) const {
		if(id != a.id) return id < a.id;
		else {
			return name > a.name;
		}
	}
};

int main(){
	// 构造mp 
	map<NODE, int> mp;
    // 存入数据 
	mp[{"zhangsan", 4}] = 86;
    mp[{"lisi", 2}] = 78;
    mp[{"daming", 1}] = 92;
    mp[{"erha", 3}] = 88;
	// 输出结果查看 
	for(auto it = mp.begin(); it!=mp.end(); it++) {
		cout << it->first.id << " " << it->first.name << " " << it->second << endl;
	}
	return 0;
}

运行结果

unordered_map

unordered_map和map是C++标准库中的两种容器，它们都可以存储键值对，但在内部实现和性能特性上有所不同：

内部实现:
- map基于红黑树实现，它是一种自平衡二叉搜索树。因此，map中的元素总是按照键的顺序排序。
- unordered_map基于哈希表实现。它使用哈希函数将键映射到存储桶中，不保证元素的顺序。
性能:
- map的查找、插入和删除操作的时间复杂度通常是O(log n)，其中n是容器中元素的数量。
- unordered_map的查找、插入和删除操作的平均时间复杂度是O(1)，但在最坏的情况下可能退化到O(n)。因此，unordered_map在元素数量较大且键分布均匀时性能较好。
使用场景:
- 当需要保持元素顺序时，应使用map。
- 当不关心元素顺序，且追求最优的查找、插入和删除性能时，应使用unordered_map。
空间效率:
- 由于unordered_map使用哈希表实现，可能会有额外的空间开销来处理哈希冲突和维护存储桶，而map通常空间效率更高。

总的来说，选择unordered_map还是map取决于具体的应用场景和性能需求。

映射Map -- STL库

头文件

map的优势

构造

常用函数

实例

构造与插入删除

运行结果

map排序

运行结果

运行结果

unordered_map