一、STL容器简介

STL容器大致分为三类：

1. 顺序容器：vector、deque、list
2. 关联容器（有序）：map、set（基于红黑树）
3. 无序容器（C++11新增）：unordered_map、unordered_set（基于哈希表）

二、map与unordered_map

1. map

• 内部实现：红黑树（平衡二叉搜索树）
• 元素自动按key有序排列：（插入时就按 key 的比较规则 “定位插入”，始终维持有序状态；如 int 的升序、string 的字典序）
• 查找、插入、删除时间复杂度：O(log n)
• 适合需要有序数据的场景

#include<map>
#include<iostream>
using namespace std;

int main(){
	map<int, string> mp;//默认升序
	//map<int, string, greater<int>> mp; // 按key降序排列
	mp[3] = "C";
	mp[1] = "A";
	mp[2] = "B";
	for( auto& p : mp){
		cout<<p.first<<"->"<<p.second<<endl;
	}
}

2. unordered_map

• 内部实现：哈希表
• 元素无序存储
• 查找、插入、删除平均复杂度：O(1)（最坏O(n)）
• 适合对顺序无要求、只关心性能的场景

#include<unordered_map>
#include<iostream>
using namespace std;

int main(){
	unordered_map<int,string> ump;
	ump[3] = "C";
	ump[1] = "A";
	ump[2] = "B";
	
	for(auto& p : ump){
		cout<<p.first<<"->"<<p.second<<endl;
	}
}

三、map vs unordered_map对比

特性	map	unordered_map
底层实现	红黑树	哈希表
是否有序	有序（按key升序）	无序
插入/查找/删除	O(log n)	平均O(1), 最坏 O(n)
内存占用	较小	较大（要维护哈希桶)
迭代器稳定性	稳定	扩容时可能失效
使用场景	需要有序遍历	高性能查找，不关心顺序

四、哈希表的原理（unordered_map)

1. 哈希函数

• 把key转换成哈希值（整数）
• 默认用std::hash，可以自定义

2. 哈希冲突

• 两个key可以映射到同一个桶
• 解决办法：链地址法（拉链），即每个桶一个链表

3. 扩容

• 当负载因子（元素数量 / 桶数量）超过阈值时，哈希表会扩容，rehash.
• 扩容会导致迭代器失效

五、代码演示：性能对比

#include<iostream>
#include<map> //标准map容器
#include<unordered_map> //无序map容器
#include<chrono> //用于时间测量
using namespace std;
using namespace chrono; //// 简化时间相关函数的使用

int main(){
	const int N = 1e6;  // 定义常量N为100万，表示要插入的元素数量
	map<int,int> mp;
	unordered_map<int,int> ump;
	
	//map插入
	auto start = high_resolution_clock::now();
	for(int i = 0; i< N; i++)mp[i] = i;
	auto end = high_resolution_clock::now():
	cout<<"map 插入时间："<<duration_cast<milliseconds>(end-start).count()<<"ms\n";
}
	// unordered_map 插入
    start = high_resolution_clock::now();
    for (int i = 0; i < N; i++) ump[i] = i;
    end = high_resolution_clock::now();
    cout << "unordered_map 插入时间: " << duration_cast<milliseconds>(end - start).count() << "ms\n";

六、注意事项（坑点）

1. unordered_map 无序，不要依赖其顺序遍历
2. unordered_map 迭代器在rehash后失效，而map的迭代器稳定。
3. unordered_map 查找性能依赖于哈希函数，如果哈希函数不好，会退化到O(n).
4. map总是有序，适合做范围查询（如找第一个大于等于某值的key）。
5. 自定义类型作为key时，需要实现：

• (1)operator (用于map)
• (2)std::hash 特化 + operator == 用于unordered_map

6.5自定义类型作为key时的map vs unordered_map代码对比

#include <iostream>
#include <map>
#include <unordered_map>
#include <string>

// 自定义类型：学生
struct Student {
    int id;
    std::string name;

    Student(int i, std::string n) : id(i), name(n) {}
};

// 1. 对于map：需要定义operator<用于排序

/*
map底层的红黑树需要通过比较键的大小来维持结构平衡和有序性。
对于基础类型（如 int、string 等），编译器已经内置了比较规则；
但对于自定义结构体，编译器不知道如何比较两个对象的大小，
因此必须通过重载<运算符来定义比较逻辑（通常是基于结构体的某个或某些成员），
这样map才能正常工作。
*/
bool operator<(const Student& a, const Student& b) {
    // 这里按id排序
    return a.id > b.id;
}

// 2. 对于unordered_map：需要特化std::hash和定义operator==

// 特化std::hash，提供哈希函数

/*
1、unordered_map 底层基于哈希表实现，需要通过哈希函数将键（key）转换为哈希值（一个整数），
以此确定元素在哈希表中的存储位置。对于自定义类型（如 Student），标准库没有默认的哈希函数，
因此需要通过特化 std::hash 来提供。先通过 hash<int>() 计算 id 的哈希值，再通过 hash<std::string>() 计算 name 的哈希值
最后通过 ^（异或）和 << 1（左移 1 位）将两个哈希值组合，生成最终的哈希值

2、为什么要组合多个成员？
    这里同时使用 id 和 name 来计算哈希值，是为了减少哈希冲突的概率。
如果只使用 id，那么当两个学生 id 相同但 name 不同时，会产生相同的哈希值，增加冲突概率。

3、命名空间的特殊性：
    必须将特化版本放在 std 命名空间中，这是 C++ 标准允许的特殊情况（通常不建议向 std 命名空间添加内容），目的是让标准库能够正确找到这个哈希函数。
*/
namespace std {
    template<> struct hash<Student> {
        size_t operator()(const Student& s) const {
            // 简单的哈希实现：结合id和name的哈希值
            return hash<int>()(s.id) ^ (hash<std::string>()(s.name) << 1);
        }
    };
}

// 定义operator==用于哈希碰撞时的比较
bool operator==(const Student& a, const Student& b) {
    // 两个学生被视为相等当且仅当id和name都相同
    return a.id == b.id && a.name == b.name;
}

int main() {
    // 使用map存储Student
    std::map<Student, int> studentScores;
    studentScores[Student(1, "Alice")] = 90;
    studentScores[Student(2, "Bob")] = 85;

    std::cout << "map中的元素：\n";
    for (const auto& pair : studentScores) {
        std::cout << "ID: " << pair.first.id << ", Name: " << pair.first.name
            << ", Score: " << pair.second << "\n";
    }

    // 使用unordered_map存储Student
    std::unordered_map<Student, int> studentAges;
    studentAges[Student(1, "Alice")] = 20;
    studentAges[Student(2, "Bob")] = 21;

    std::cout << "\nunordered_map中的元素：\n";
    for (const auto& pair : studentAges) {
        std::cout << "ID: " << pair.first.id << ", Name: " << pair.first.name
            << ", Age: " << pair.second << "\n";
    }

    return 0;
}

小结

• map: 红黑树，有序，O(log n),内存友好，迭代器稳定
• unordered_map: 哈希表，无序，平均O(1),适合快速查找
• • map 保持了迭代器稳定性，但查询效率略低。
• • unordered_map 追求查询效率，牺牲了迭代器稳定性；