vps建站教程专业网站建设定制公司

vps建站教程,专业网站建设定制公司,河北中石化建设网站,江门移动网站建设多少钱1. 核心概念#xff1a;什么是 set#xff1f; std::set是C标准模板库(STL)中的一种关联式容器。它的核心特性可以概括为以下三点#xff1a; 唯一性#xff1a;容器内的所有元素都是唯一的#xff0c;不允许重复。 有序性#xff1a;元素在容器中总是按照特定的严格弱…1. 核心概念什么是 setstd::set是C标准模板库(STL)中的一种关联式容器。它的核心特性可以概括为以下三点唯一性容器内的所有元素都是唯一的不允许重复。有序性元素在容器中总是按照特定的严格弱序规则进行排序默认是升序。关键特性元素的value就是key。你无法直接修改set中的元素因为这可能破坏其有序性。2. 底层实现红黑树这是理解set所有特性的关键。set通常被实现为一颗红黑树这是一种高效的自平衡二叉搜索树。二叉搜索树保证了元素的有序存储使得查找、插入、删除的平均时间复杂度可以达到O(log n)。自平衡红黑树防止在最坏情况下例如插入有序序列退化成链表操作复杂度O(n)通过旋转和变色规则保持树的相对平衡保证了最坏情况下的操作复杂度也是O(log n)。3. 基本用法与代码示例cpp#include iostream #include set using namespace std; int main() { // 1. 初始化 setint mySet {5, 2, 8, 2, 1}; // 重复的2只会保留一个 // 此时 mySet 内容为: {1, 2, 5, 8} (已排序) // 2. 插入元素 mySet.insert(3); // 插入 3 auto ret mySet.insert(5); // 再次尝试插入5 if (!ret.second) { cout Insertion failed. Element 5 already exists. endl; } // 3. 遍历总是有序输出 cout Set elements: ; for (int num : mySet) { cout num ; // 输出: 1 2 3 5 8 } cout endl; // 4. 查找与计数 auto it mySet.find(3); if (it ! mySet.end()) { cout Found: *it endl; } cout Count of 2: mySet.count(2) endl; // 输出1 (存在) cout Count of 9: mySet.count(9) endl; // 输出0 (不存在) // 5. 删除元素 mySet.erase(2); // 通过值删除 auto it_to_erase mySet.find(5); if (it_to_erase ! mySet.end()) { mySet.erase(it_to_erase); // 通过迭代器删除 } // 6. 常用操作 cout Size: mySet.size() endl; cout Is empty? (mySet.empty() ? Yes : No) endl; mySet.clear(); // 清空所有元素 return 0; }4. 进阶特性与重要成员自定义排序规则你可以通过提供自定义的比较函数或函数对象来改变元素的排序方式。cpp// 示例1使用greaterint使set降序排列 setint, greaterint descendingSet {5, 2, 8, 1}; // 内容为: {8, 5, 2, 1} // 示例2自定义结构体排序 struct Person { string name; int age; }; // 定义比较仿函数按年龄升序排序 struct CompareByAge { bool operator()(const Person a, const Person b) const { return a.age b.age; } }; setPerson, CompareByAge personSet;关键迭代器与方法除了begin()和end()set提供了一些特有的迭代器方法这对于有序数据的操作非常高效lower_bound(key)返回第一个 key的元素的迭代器。upper_bound(key)返回第一个 key的元素的迭代器。equal_range(key)返回一个pair表示等于key的元素范围对于set这个范围最多包含一个元素。cppsetint s {10, 20, 30, 40, 50}; auto low s.lower_bound(25); // 指向30 (第一个 25 的元素) auto up s.upper_bound(35); // 指向40 (第一个 35 的元素) s.erase(low, up); // 删除区间 [30, 40)即删除30 // 此时 s {10, 20, 40, 50}5. 核心特点总结与对比特性std::setstd::vectorstd::unordered_set元素顺序严格有序根据比较规则插入顺序无序根据哈希值重复元素不允许允许不允许底层实现红黑树平衡BST动态数组哈希表平均时间复杂度查找/插入/删除:O(log n)查找: O(n) 尾部插入: O(1)查找/插入/删除:O(1)关键用途需要自动排序且去重的场景随机访问、尾部操作频繁仅需快速查找去重不关心顺序6. 典型应用场景自动去重与排序比如需要维护一个不重复的单词列表并随时按字母顺序输出。快速存在性检查在O(log n)时间内判断一个元素是否存在且需要数据有序。范围查询利用lower_bound/upper_bound高效查询某个分数区间的学生或某个价格区间的商品。7. 需要特别注意的要点不可直接修改元素set的迭代器是const的即使是非常量迭代器。因为直接修改可能破坏红黑树的有序性。必须先删除旧元素再插入新元素。内存开销相比vector或unordered_set红黑树的每个节点都需要额外的指针指向父节点和左右子节点以及颜色标记内存开销更大。迭代器稳定性除了被删除的元素set的迭代器在插入操作后通常保持有效因为红黑树是节点式容器。理解set的关键在于牢牢抓住其“有序”和“唯一”这两个核心并时刻意识到其底层是一棵红黑树。它在需要有序访问、范围查询的场景下无可替代但在只要求快速查找、不关心顺序时unordered_set通常是更优选择。