map和set的区别和底层实现是什么？map取值的 find，[]，at方法的区别

1. 基本定义

2. 底层实现

3. 存储内容

4. 常用操作

5. 有序性

二、map 的取值方法：find()，[]，和 at()

1. find()

2. operator[]（[] 操作符）

3. at()

一、map 和 set 的区别

1. 基本定义

• map：一种关联容器，存储的是键值对（key-value pairs），每个键对应唯一的值。键是唯一的，不允许重复。常见的用法是 std::map<Key, Value>.
• set：一种集合容器，存储的是唯一的键（key），不存储值。元素是唯一的，且不可重复。常见的用法是 std::set<Key>.

2. 底层实现

• map 和 set：底层通常使用**红黑树（Red-Black Tree）**实现，红黑树是一种自平衡的二叉查找树，能够保证增删查改操作的时间复杂度为 O(log n)。
  • 在 map 中，红黑树的节点存储键值对，按键排序。
  • 在 set 中，红黑树的节点只存储键，按键排序。
• unordered_map 和 unordered_set：底层使用**哈希表（Hash Table）**实现，通过哈希函数将键映射到不同的桶，增删查改操作的平均时间复杂度为 O(1)，最坏情况下为 O(n)。

3. 存储内容

• map：存储键值对，键唯一，值可以重复或不同。
  • 例如：map<int, string> m; m[1] = "one"; m[2] = "two";
• set：只存储唯一的键，不存储值。
  • 例如：set<int> s; s.insert(1); s.insert(2);

4. 常用操作

• map：可以通过键来查找值（例如 m[key]），插入或删除键值对。
• set：可以插入、删除和查找键（例如 s.insert(key)，s.find(key)）。

5. 有序性

• map 和 set：两者都按照键进行排序（使用比较函数，如 <）。
• unordered_map 和 unordered_set：无序，元素排列顺序由哈希函数决定。

二、map 的取值方法：find()，[]，和 at()

在 map 中，可以使用多种方法来访问存储的值，每种方法的行为略有不同。

1. find()

• 功能：用于查找指定键是否存在。如果存在，返回指向该元素的迭代器；如果不存在，返回 map.end()。
• 用法：

std::map<int, std::string> m = {{1, "one"}, {2, "two"}};
auto it = m.find(1);  // 返回指向键为1的迭代器
if (it != m.end()) {
    std::cout << it->second << std::endl;  // 输出 "one"
}

• 特点：
  • 不会插入新元素，如果键不存在，仅返回 end()。
  • 时间复杂度为 O(log n)。

2. operator[]（[] 操作符）

• 功能：通过键来访问值。如果键存在，返回对应的值；如果键不存在，会创建一个新的键值对，并初始化值（通常为值类型的默认构造值，如 0、空字符串等）。
• 用法：

std::map<int, std::string> m;
m[1] = "one";  // 插入键1的元素，并赋值为"one"
std::cout << m[2];  // 键2不存在，插入键2，值初始化为空字符串

• 特点：
  • 如果键不存在，会创建新元素并初始化，这种行为可能导致意外的元素插入。
  • 适合用于需要修改或赋值的场景。
  • 时间复杂度为 O(log n)。

3. at()

• 功能：通过键来访问值。如果键存在，返回对应的值；如果键不存在，抛出 std::out_of_range 异常。
• 用法：

std::map<int, std::string> m = {{1, "one"}};
std::cout << m.at(1);  // 输出 "one"
std::cout << m.at(2);  // 抛出 std::out_of_range 异常

特点：

• 不会插入新元素，仅在键存在时返回值。
• 适合用于确定键一定存在的场景，否则需要异常处理。
• 时间复杂度为 O(log n)。