std : : map

一.为啥map不能自定义比较器，set可以？

std::map 和 std::set 的不同之处在于它们的数据结构和用途。

1. std::map：std::map 是一个关联容器，它是一个键-值对集合，其中键是唯一的，且键的排序是固定的。键是用于查找值的，因此对于 std::map 来说，键的排序非常重要。std::map 使用红黑树（Red-Black Tree）作为底层数据结构，这是一种自平衡二叉搜索树，可以保持键的有序性。因此，std::map 内置了自然的键排序，不需要提供自定义比较器。

2. std::set：std::set 也是一个关联容器，它存储唯一元素的集合，但它不是键-值对集合，只包含键（元素）。与 std::map 类似，std::set 也使用红黑树来维护元素的有序性。在 std::set 中，元素的值就是用于排序的键，因此可以提供自定义比较器来改变元素的排序规则。

总之，std::map 和 std::set 的不同在于它们的用途和数据结构。std::map 是键-值对的关联容器，它的排序是基于键的。而 std::set 是一个元素集合的关联容器，可以通过自定义比较器来改变元素的排序规则。如果您需要自定义排序规则并且不需要键-值对的关联性，那么 std::set 或 std::multiset 可能更适合您的需求。如果需要键-值对的关联性并且希望按键进行排序，那么 std::map 或 std::multimap 是更合适的选择。

set的比较器（降序）

#include<iostream>
#include<set>
#include<algorithm>
using namespace std;
struct cmp {
   bool operator()(const pair<int, int>&a, const pair<int, int>&b) const {
        if (a.first == b.first) return a.second>b.second;
        return a.first > b.first;
    }
};
 
int main() {
    set<pair<int, int>,cmp>set;
    set.insert({2,3});
    set.insert({5,9});
    set.insert({5,6});
    set.insert({2,4});
    for (const auto& pair : set) {
        cout << pair.first << " " << pair.second << "\t\t";
   }
    return 0;
}

注意：

• 在 C++ 中，在成员函数的声明中末尾添加 const 修饰符表示该成员函数是一个常量成员函数。这意味着在这个函数内部，不允许修改对象的非静态成员变量，即使该函数是在一个非常量对象上调用的。

可以加static吗？

• 使用运算符重载（operator）的话不能用static，会报错。

二.map、set是怎么实现的，红黑树是怎么能够同时实现这两种容器？ 为什么使用红黑树？

1. 他们的底层都是以红黑树的结构实现，因此插入删除等操作都在O(logn)时间内完成，因此可以完成高效的插入删除；

2. 在这里我们定义了一个模版参数，如果它是key那么它就是set，如果它是map，那么它就是map；底层是红黑树，实现map的红黑树的节点数据类型是key+value，而实现set的节点数据类型是value

3. 因为map和set要求是自动排序的，红黑树能够实现这一功能，而且时间复杂度比较低。

三.map插入方式有哪几种？

1.用insert函数插入pair数据

mapStudent.insert(pair<int, string>(1, "student_one")); 

2.用insert函数插入value_type数据

mapStudent.insert(map<int, string>::value_type (1, "student_one"));

3.在insert函数中使用make_pair()函数

mapStudent.insert(make_pair(1, "student_one")); 

4.用数组方式插入数据

mapStudent[1] = "student_one"; 

四.map为什么没有reserve？

std::map 是 C++ 标准模板库（STL）中的关联容器之一，它使用红黑树来实现键值对的有序存储。在 std::map 中，元素会按照键的自然顺序进行排序，并且不能重复。

std::map 没有提供 reserve() 方法的原因是，与其它容器（如 std::vector、std::unordered_map 等）不同，std::map 的内部数据结构是基于红黑树实现的，它并没有连续分配内存的需求。因此，在创建一个空的 std::map 时，并不需要保留一定的容量。

reserve() 方法通常用于容器预先分配一定的存储空间。而对于 std::map 来说，由于其内部的红黑树结构不需要连续的存储空间，因此不存在重新分配和拷贝的问题，也就没有必要提供 reserve() 方法。

如果你想在创建 std::map 时指定初始大小，可以通过传递一个已有容器作为构造函数的参数来实现：

std::map myMap(existingContainer.begin(), existingContainer.end());

总之，std::map 不提供 reserve() 方法是因为其内部数据结构的特点决定了它不需要连续的存储空间，因此不需要在创建时保留一定的容量。

五.map什么时候迭代器失效？

1.插入元素：如果在迭代过程中向std::map中插入新的键值对，则所有之前的迭代器都会失效，因为插入操作可能导致内部数据结构重新组织，改变树的结构。

std::map<int, std::string> myMap;
std::map<int, std::string>::iterator it = myMap.begin();
 
myMap[1] = "One"; // 这里插入新元素
// 现在迭代器 it 可能已经失效

2.删除元素：如果在迭代过程中删除了元素，则指向被删除元素的迭代器也会失效。

std::map<int, std::string> myMap;
myMap[1] = "One";
myMap[2] = "Two";
std::map<int, std::string>::iterator it = myMap.begin();
 
myMap.erase(1); // 删除元素
// 现在迭代器 it 可能已经失效

3.改变键的值：如果在迭代过程中修改了std::map中已存在的键的值，迭代器通常会保持有效，因为它们仍然指向相同的键，但是请小心，这可能会改变键的排序位置。

std::map<int, std::string> myMap;
myMap[1] = "One";
std::map<int, std::string>::iterator it = myMap.begin();
 
it->second = "NewOne"; // 修改键值
// 迭代器 it 仍然有效，但排序位置可能已经改变