C++高性能并行编程与优化 - 课件 - 14 C++ 标准库系列课 - 你所不知道的 set 容器

• 语言: 中文（简体）
• 格式: .pptx
• 来源: github.com/archibate

摘要

文档详细介绍了C++标准库中的set容器，包括其与vector的主要区别、set的内部实现机制以及其使用场景。重点比较了set、multiset、unordered_set和unordered_multiset的功能和性能特点，并展示了如何通过迭代器使用lower_bound和upper_bound等函数进行元素查找。同时，文档还探讨了如何将set中的元素转换到vector中，以及set的自定义排序机制。

AI总结

# C++ 高性能并行编程与优化 - 《你所不知道的 set 容器》总结

## 课程概述
本课程主要介绍了 C++ 标准库中的 `set` 容器，重点讨论了其功能、用法以及与其他容器的区别和转换。课程内容涵盖了 `set` 的基本特性、常用函数、与其他容器的比较以及自定义排序功能等。

---

## set 容器的特性
1. **自动排序**：`set` 中的元素会自动按照从小到大的顺序排列。
2. **去重功能**：`set` 会自动去除重复元素，只保留唯一的值。
3. **高效查找**：`set` 提供高效的按值查找功能，时间复杂度为 \(O(\log n)\)。
4. **内存布局**：`set` 内部通过红黑树实现，元素在内存中并非连续存储。

---

## set 与其他容器的区别
1. **与 vector 的区别**：
- `vector` 保持插入顺序且支持随机访问，而 `set` 自动排序且不支持随机访问。
- `vector` 允许重复元素，而 `set` 自动去重。
2. **与 multiset 的区别**：
- `set` 不允许重复元素，而 `multiset` 允许重复。
3. **与 unordered_set 的区别**：
- `set` 元素排序，而 `unordered_set` 无序，基于哈希表实现，查找时间复杂度为 \(O(1)\)。
- `unordered_set` 不支持 `lower_bound` 和 `upper_bound` 等函数。

---

## 常用函数
1. **查找函数**：
- `find(x)`：查找等于 `x` 的元素。
- `lower_bound(x)`：返回第一个大于等于 `x` 的元素的迭代器。
- `upper_bound(x)`：返回第一个大于 `x` 的元素的迭代器。
- `equal_range(x)`：返回所有等于 `x` 的元素的范围。
2. **插入与删除**：
- 支持 `emplace`、`emplace_hint` 和 `try_emplace` 方法。
3. **转换示例**：
- 可将 `set` 中的元素范围（如 `2 ≤ x ≤ 4`）拷贝到 `vector` 中，利用 `vector` 的前向迭代器构造函数。

---

## 自定义排序与注意事项
1. **自定义排序函数**：
- `set` 支持自定义比较函数（`CompT`），如通过 `std::greater` 实现降序排序。
2. **字符串比较注意事项**：
- 避免使用 `set` 存储字符串，因为它会比较指针地址，而非字符串内容。

---

## 性能与优化
- **时间复杂度**：`set` 的 `lower_bound`、`upper_bound` 和 `find` 函数时间复杂度均为 \(O(\log n)\)，而 `unordered_set` 的查找时间复杂度为 \(O(1)\)。
- **并行化与高效去重**：`set` 本身不支持并行化，但后续课程可能会讨论高效去重的替代方案。

---

## 总结
`set` 容器是一个强大且高效的数据结构，适合需要自动排序和高效查找的场景。了解其与其他容器的区别和优化技巧可以帮助开发者更好地利用其功能。后续课程将进一步探讨 STL 算法库、字符串操作、内存管理等内容。