目录
一、有序关联容器map
1、map介绍
(1)map和set类似，但是map是(key, value)对，而set只有key（可以理解为key就是value）
(2)map是映射的意思，此处是key到value的一对一映射。不要理解成地图（根据地图查位置）,一般用key去查value
(3)map的用法和特征与set非常类似，学会set了再学map就容易多了
2、pair
(1)pair即对，也就是(key, value)对，本质是有2个元素的结构体
(2)std::pair是STL的标准pair封装
(3)pair中2个元素类型可以不同，也就是说key和value的类型可以不同，也可以相同
(4)pair中2个元素名字是固定的，key叫first，而value叫second
(5)map中存的元素都是一个一个的pair，访问map的key和value要先从map找到pair，再去first和second
参考学习：https://zh.cppreference.com/w/cpp/utility/pair
3、map的构造函数详解
(1)直接参考cppreference中构造函数页面的sample即可，链接如下：
https://zh.cppreference.com/w/cpp/container/map/map
#include <iostream>
#include <map>
#include <iomanip>
#include <string>
//using namespace std;
template <typename Map>
void print_map(Map& m)
{
std::cout << '{';
for(auto& p : m)
std::cout << p.first << ':' << p.second << ' ';
std::cout << "}\n";
}
struct Point{double x,y;};
struct PointCmp{
bool operator()(const Point& lhs, const Point& rhs) const{
return lhs.x < rhs.x;
}
};//定义一个函数对象
int main(int argc, char *argv[])
{
//1、默认构造函数
std::map<std::string, int> map1;
map1["something"] = 69;//向位图中添加元素
map1["anything"] = 199;
map1["everything"] = 50;
std::cout << "map1 = ";print_map(map1);
//2、范围构造函数
std::map<std::string, int> iter(map1.find("anything"),map1.end());
std::cout << "\niter = ";print_map(iter);
std::cout << "map1 = ";print_map(map1);
//3、复制（拷贝构造函数）
std::map<std::string, int> copied(map1);
std::cout << "\ncopied = ";print_map(copied);
std::cout << "map1 = ";print_map(map1);
//4、移动构造函数
std::map<std::string, int> moved(std::move(map1));
std::cout << "\nmoved = ";print_map(moved);
std::cout << "map1 = ";print_map(map1);
//5、initializer_list 构造函数
std::map<std::string, int> init{
{"this", 100},
{"can", 100},
{"be", 100},
{"const", 100},
};
std::cout << "\ninit = ";print_map(init);
// 定制关键类选项 1 ：
// 使用比较 struct
std::map<Point, double, PointCmp> mag = {
{ {5, -12}, 13 },
{ {3, 4}, 5 },
{ {-8, -15}, 17 }
};
for(auto p : mag)
std::cout << "The magnitude of (" << p.first.x
<< ", " << p.first.y << ") is "
<< p.second << '\n';
// 定制关键类选项 2 ：
// 使用比较 lambda
// 此 lambda 按照其模比较点，注意其中模取自局部变量 mag
auto cmpLambda = [&mag](const Point &lhs, const Point &rhs) { return mag[lhs] < mag[rhs]; };
// 你亦可使用不依赖局部变量的 lambda ，像这样：
// auto cmpLambda = [](const Point &lhs, const Point &rhs) { return lhs.y < rhs.y; };
std::map<Point, double, decltype(cmpLambda)> magy(cmpLambda);
// 各种插入元素的方式：
magy.insert(std::pair<Point, double>({5, -12}, 13));
magy.insert({ {3, 4}, 5});
magy.insert({Point{-8.0, -15.0}, 17});
std::cout << '\n';
for(auto p : magy)
std::cout << "The magnitude of (" << p.first.x
<< ", " << p.first.y << ") is "
<< p.second << '\n';
return 0;
}
4、其他方法
(1)与set非常类似，详见：https://zh.cppreference.com/w/cpp/container/map
(2)extract是修改map的key值的唯一方法,map和set中的key是不可以重复的，但map的value可以重复，而由于set的key和value是一个东西，所以set的value也不可以重复。
(3)map中的排序是根据key进行的，所以一般都不修改key，修改后需要再次排序
二、multi_set和multi_map
1、multi_版本的差异
(1)set和map中每个容器内所有元素的key都是unique(独一无二)的，不能重复
(2)如果需要容器中同一个key有多个元素(也可理解为有多个相同的key)，则需要使用multi_版本的set和map
(3)除此区别外，multi_版本和普通版本没有任何差异，所有方法也完全一样
(4)工作中用哪个，取决于实际需求。
2、multi_set实战演示
学习参考：https://zh.cppreference.com/w/cpp/container/multiset
3、multi_map实战演示
学习参考：https://zh.cppreference.com/w/cpp/container/multimap
#include <iostream>
#include <set>
#include <map>
using namespace std;
int main(void)
{
multimap<int, string> m1;
m1.insert({0, "linux"});
m1.insert({1, "android"});
m1.insert({2, "windows"});
m1.insert({1, "macos"});
m1.insert({2, "harmonyos"});
cout << "size = " << m1.size() << endl;
for (auto val : m1)
{
cout << "{" << val.first << ", " << val.second << "}" << endl;
}
/*
multiset<string> s1;
s1.insert("horse"); // 按照key去排序
s1.insert("cat");
s1.insert("cat");
s1.insert("cat");
s1.insert("dog");
cout << "size = " << s1.size() << boolalpha << ", empty = " << s1.empty() << endl;
for (auto val : s1)
{
cout << val << " ";
}
cout << endl;
*/
return 0;
}
三、无序关联容器
1、无序关联容器和有序关联容器的相同点
(1)也属于关联容器，有set和map两种，set只有key，map有(key, value)对
(2)也有带不带multi_的版本，差异和上节讲的一样
(3)操作方法很多都是重合的，名字和作用也都一样
2、无序关联容器和有序关联容器的差异点
(1)有序内部用红黑树实现，无序内部用哈希函数实现
(2)有序插入元素时会内部自动排序，无序插入时不排序，按照哈希规则直接映射存放
3、无序关联容器初步使用
(1)unordered_set和unordered_map
参考学习：
https://zh.cppreference.com/w/cpp/container/unordered_set
https://zh.cppreference.com/w/cpp/container/unordered_map
四、哈希函数和桶
1、什么是哈希函数(一类函数)
(1)哈希表是一种典型数据结构，又被称为是散列表，英文hashmap
(2)STL中的哈希表hashmap就是unordered_map
(3)哈希函数是可以用来实现哈希表的函数，是一类而不是一个
(4)哈希表的本质是k-v结构，也就是给定key可以找到一个位置来对应value
2、哈希冲突及其解决
参考学习：https://blog.csdn.net/WX_East/article/details/56005664?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-1.control&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-1.control
五、unordered_map中桶相关的方法
#include <iostream>
#include <unordered_map>
using namespace std;
int main(void)
{
unordered_map<int, string> m1;
for (int i=0; i<100; i++)
{
m1.insert({i, "abc"});
cout << "{" << i << ", " << "abc" << "}, ";
cout << "element size = " << m1.size() << ", bucket size = " << m1.bucket_count() << endl;
}
return 0;
}
注：本文章参考了《朱老师物联网大讲堂》课程笔记，并结合了自己的实际开发经历以及网上他人的技术文章，综合整理得到。如有侵权，联系删除！水平有限，欢迎各位在评论区交流