STL之map

目录

map(常用)

map的函数

multimap(几乎不用-时间复杂度不稳定)

mutimap的函数

unordered_map(一般不用)

unordered_map的函数

代码示例

1.map

2、multimap

3、unordered_map

---

map(常用)

map是一种关联容器，用于存储一组键值对(key-value pairs)，其中每个键(key)都是唯一的。

map容器根据键来自动排序，并且可以通过键快速查找对应的值。

map容器使用红黑树（Red-Black Tree）数据结构来实现，具有较快的插入、删除和查找操作的时间复杂度O(logn).

map的定义和结构如下：

template<class Key,class T,class Compare = less<key>,
         class Allocator = allocator<pair<const Key,T>>>
class map;

Key:表示存储在map中的键（key）的类型

T：表示存储在map中的值（value）的类型

Compare：表示用于比较键的函数对象的类型，默认为less，使用键类型的默认比较函数。

Allocator：表示用于分配内存的分配器类型，默认为allocator。

map的函数

函数?????????????????????功能??????? ????????????????????????????????????????? ?? ???? 时间复杂度

insert???????? ?????? 插入元素 ????????????????????????????????????????????????????????O(logn)

erase???????? ?????? 删除元素 ????????????????????????????????????????????????????????O(logn)

find????????? ????? ?? 查找元素 ????????????????????????????????????????????????????????O(logn)

count ?????????????? 统计元素个数 ???????????????????????????????????????????????? O(logn)

size ???????????????? 返回元素个数 ????????????????????????????????????????????????? O(1)

begin ?????????????? 返回指向容器起始位置的迭代器????????????????????? O(1)

end ????????????????? 返回指向容器末尾位置的迭代器????????????????????? O(1)

clear ????? ????????? 清空容器??????????????????????????????????????????????????????? ? O(n)

empty ????? ????????判断容器是否为空 ?????????????????????????? ????????????????O(1)

lower_bound??? 返回指向第一个不小于指定键的元素位置 ? ? ?? O(logn)

upper_bound ? 返回指向第一个不大于指定键的元素位置 ? ? ? ? O(logn)

multimap(几乎不用-时间复杂度不稳定)

multimap是一种关联容器，类似于map，但允许存储多个具有相同的键值对(key-value pairs)。

multimap容器根据键来自动排序，并且可以通过键快速查找对应的值。

map容器使用红黑树（Red-Black Tree）数据结构来实现，具有较快的插入、删除和查找操作的时间复杂度。

map的定义和结构如下：

template<class Key,class T,class Compare = less<key>,
         class Allocator = allocator<pair<const Key,T>>>
class multimap;

Key:表示存储在multimap中的键（key）的类型

T：表示存储在multimap中的值（value）的类型

Compare：表示用于比较键的函数对象的类型，默认为less，使用键类型的默认比较函数。

Allocator：表示用于分配内存的分配器类型，默认为allocator。

mutimap的函数

函数?????????????????????功能??????? ????????????????????????????????????????? ?? ???? 时间复杂度

insert???????? ?????? 插入元素 ????????????????????????????????????????????????????????O(logn)

erase???????? ?????? 删除元素 ????????????????????????????????????????????????????????O(logn)

find????????? ????? ?? 查找元素 ????????????????????????????????????????????????????????O(logn)

count ?????????????? 统计元素个数 ???????????????????????????????????????????????? O(logn)

size ???????????????? 返回元素个数 ????????????????????????????????????????????????? O(1)

begin ?????????????? 返回指向容器起始位置的迭代器????????????????????? O(1)

end ????????????????? 返回指向容器末尾位置的迭代器????????????????????? O(1)

clear ????? ????????? 清空容器??????????????????????????????????????????????????????? ? O(n)

empty ????? ????????判断容器是否为空 ?????????????????????????? ????????????????O(1)

unordered_map(一般不用)

unordered_map是一种关联容器，用于存储一组键值对(key-value pairs)。每一个键（key）都是唯一的。

与map和multimap不同，unordered_map不会根据键来自动排序，而是使用哈希函数将键映射到存储桶中。

这使得unordered_map具有更快的插入、删除和查找操作的时间复杂度，但不保证元素的顺序。

unordered_map的定义和结构如下：

template<class Key,class T,class Hash = hash<key>,
         class KeyEqual = equal_to<key>,
         class Allocator = allocator<pair<const Key,T>>>
class unordered_map;

Key:表示存储在unordered_map中的键（key）的类型

T：表示存储在unorder_map中的值（value）的类型

Hash:表示用于计算键的哈希值的函数对象的类型，默认为Hash，使用键类型的默认哈希函数。

KeyEqual：表示用于比较键的函数对象的类型，默认为equal_to，使用键类型的默认比较函数。

Allocator：表示用于分配内存的分配器类型，默认为allocator。

unordered_map的函数

函数?????????????????????功能??????? ????????????????????????????????????? 平均时间复杂度??????? 最坏时间复杂度

insert???????? ?????? 插入元素 ????????????????????????????????????????????? O(1)??????????????????????????????? O(n)

erase???????? ?????? 删除元素 ????????????????????????????????????????????? O(1)????????????????????????????????O(n)

find????????? ????? ?? 查找元素 ????????????????????????????????????????????? O(1)????????????????????????????????O(n)

count ?????????????? 统计元素个数 ?????????????????????????????????????? O(1)????????????????????????????????O(n)

size ???????????????? 返回元素个数 ??????????????????????????????????????? O(1)????????????????????????????????O(1)

clear ????? ????????? 清空容器????????????????????????????????????????????? ? O(1)????????????????????????????????O(1)

empty ????? ????????判断容器是否为空 ?????????????????????????? ????? O(1)????????????????????????????????O(n)

unordered_map拥有极好的平均时间复杂度和极差的最坏时间复杂度，所以他的时间复杂度是不稳定的。

一般情况下我们更愿意使用复杂度稳定的map而不是unordered_map。

代码示例

1.map

#include<iostream>
#include<map>
using namespace std;
int main()
{
	//创建并初始化map
	map<int, string>myMap = { {1,"Apple"},{2,"Banana"},{3,"Orange"} };
	//插入元素
	myMap.insert(make_pair(4, "Grapes"));
	//查找和访问元素
	cout << "value at key 2:" << myMap[2] << endl;
	//遍历并打印map中的元素
	for (const auto& i : myMap)
	{
		cout << "Key:" << i.first << ",value:" << i.second << endl;
	}
	//删除元素
	myMap.erase(3);
	//判断元素是否存在
	if (myMap.count(3) == 0)
	{
		cout << "key 3 not found" << endl;
	}
	//清空map
	myMap.clear();
	//判断map是否为空
	if (myMap.empty())
	{
		cout << "map is empty" << endl;
	}
	return 0;
}

结果：

2、multimap

#include<iostream>
#include<map>
using namespace std;
int main()
{
	//创建并初始化multimap
	multimap<int, string>myMultiMap = { {1,"Apple"},{2,"Banana"},{2,"Orange"} };
	//插入元素
	myMultiMap.insert(make_pair(3, "Grapes"));
	//查找和访问元素
	auto range = myMultiMap.equal_range(2);
	for (auto it = range.first; it != range.second; ++it)
	{
		cout << "key:" << it->first << ",value:" << it->second << endl;
	}
	//遍历并打印multimap中的元素
	for (const auto& i : myMultiMap)
	{
		cout << "Key:" << i.first << ",value:" << i.second << endl;
	}
	//删除元素
	myMultiMap.erase(2);
	//判断元素是否存在
	if (myMultiMap.count(2) == 0)
	{
		cout << "key 2 not found" << endl;
	}
	//清空map
	myMultiMap.clear();
	//判断map是否为空
	if (myMultiMap.empty())
	{
		cout << "myMultiMap is empty" << endl;
	}
	return 0;
}

结果：

3、unordered_map

#include<iostream>
#include<unordered_map>
using namespace std;
int main()
{
	//创建并初始化unordered_map
	unordered_map<string,int>myMap = { {"Apple",3},{"Banana",5},{"Orange",2} };
	//插入元素
	myMap.insert(make_pair("Grapes",4));
	//查找和访问元素
	cout << "value for key 'Banana':" << myMap["Banana"] << endl;
	//遍历并打印unordered_map中的元素
	for (const auto& i : myMap)
	{
		cout << "Key:" << i.first << ",value:" << i.second << endl;
	}
	//删除元素
	myMap.erase("Orange");
	//判断元素是否存在
	if (myMap.count("Orange") == 0)
	{
		cout << "key 'Orange' not found" << endl;
	}
	//清空map
	myMap.clear();
	//判断map是否为空
	if (myMap.empty())
	{
		cout << "unordered_map is empty" << endl;
	}
	return 0;
}

结果：