C++ 第四阶段 STL 容器 - 第五讲:详解 std::set 与 std::unordered_set

发布于:2025-07-01 ⋅ 阅读:(21) ⋅ 点赞:(0)

目录

📌 一、std::set 与 std::unordered_set 概述

📌 二、std::set 详解

1. 核心特性

2. 常用函数解析

3. 自定义比较函数

📌 三、std::unordered_set 详解

1. 核心特性

2. 常用函数解析

3. 自定义哈希与比较函数

📌 四、性能对比与优化建议

1. 性能对比表

2. 优化建议

📌 五、常见陷阱与解决方案

1. 修改 std::set 中的元素

2. std::unordered_set 的 rehash

3. 自定义类型的哈希冲突

📌 六、典型应用场景

1. 去重场景

2. 快速查找

3. 有序集合操作

🧠 总结

C++从入门到入土学习导航_c++学习进程-CSDN博客


📌 一、std::set 与 std::unordered_set 概述

std::setstd::unordered_set 是 C++ STL 中的 集合容器,用于存储唯一的元素集合。它们的核心区别在于:

特性 std::set std::unordered_set
底层实现 红黑树(自动排序) 哈希表(无序)
元素顺序 升序排列 无序
查找复杂度 O(log n) 平均 O(1)(最坏 O(n))
内存占用 较高(红黑树节点指针) 较低(哈希桶)
适用场景 需要有序集合 快速查找/插入/删除

📌 二、std::set 详解

1. 核心特性

  • 唯一性:所有元素唯一。
  • 自动排序:元素按升序排列(默认使用 < 运算符)。
  • 双向迭代器:支持顺序遍历。
  • 动态内存管理:自动调整红黑树结构。

2. 常用函数解析

#include <set>
#include <iostream>

int main() {
    // 1. 初始化
    std::set<int> s1;
    std::set<int> s2 = {1, 3, 2};
    std::set<int> s3(s2.begin(), s2.end());

    // 2. 插入与删除
    s1.insert(5);  // 插入单个元素
    s1.insert({6, 7, 8});  // 插入多个元素
    s1.erase(5);  // 删除指定值
    s1.erase(s1.begin());  // 删除指定迭代器位置

    // 3. 查找与访问
    auto it = s1.find(3);
    if (it != s1.end()) {
        std::cout << "Found: " << *it << "\n";
    }

    // 4. 遍历
    for (const auto& val : s1) {
        std::cout << val << " ";  // 输出有序元素
    }

    // 5. 特殊操作(仅 set 支持)
    auto lb = s1.lower_bound(4);  // >=4 的第一个元素
    auto ub = s1.upper_bound(4);  // >4 的第一个元素
    return 0;
}

3. 自定义比较函数

struct CompareDesc {
    bool operator()(int a, int b) const {
        return a > b;  // 降序排列
    }
};

std::set<int, CompareDesc> s = {3, 1, 2};
for (const auto& val : s) {
    std::cout << val << " ";  // 输出 3 2 1
}

📌 三、std::unordered_set 详解

1. 核心特性

  • 唯一性:所有元素唯一。
  • 无序性:元素存储顺序由哈希值决定。
  • 快速查找:平均时间复杂度为 O(1)。
  • 哈希冲突:通过链表或开放寻址法解决。

2. 常用函数解析

#include <unordered_set>
#include <iostream>

int main() {
    // 1. 初始化
    std::unordered_set<int> us1;
    std::unordered_set<int> us2 = {1, 3, 2};
    std::unordered_set<int> us3(us2.begin(), us2.end());

    // 2. 插入与删除
    us1.insert(5);
    us1.insert({6, 7, 8});
    us1.erase(5);
    us1.erase(us1.begin());  // 删除指定迭代器位置

    // 3. 查找与访问
    if (us1.find(3) != us1.end()) {
        std::cout << "Found\n";
    }

    // 4. 遍历
    for (const auto& val : us1) {
        std::cout << val << " ";  // 输出无序元素
    }

    // 5. 性能优化
    us1.reserve(100);  // 预分配桶空间
    us1.max_load_factor(0.75);  // 设置最大负载因子
    return 0;
}

3. 自定义哈希与比较函数

struct Key {
    int a, b;
    bool operator==(const Key& other) const {
        return a == other.a && b == other.b;
    }
};

struct KeyHash {
    std::size_t operator()(const Key& k) const {
        return std::hash<int>()(k.a) ^ (std::hash<int>()(k.b) << 1);
    }
};

std::unordered_set<Key, KeyHash> mySet;
mySet.insert({1, 2});

📌 四、性能对比与优化建议

1. 性能对比表

操作 std::set std::unordered_set
查找 O(log n) O(1)(平均)
插入 O(log n) O(1)(平均)
删除 O(log n) O(1)(平均)
遍历 O(n) O(n)
内存占用

2. 优化建议

  • std::set
    • 适用于需要有序集合的场景。
    • 避免频繁插入/删除导致的树结构调整。
    • 使用 lower_bound/upper_bound 提高性能。
  • std::unordered_set
    • 适用于快速查找/插入/删除的场景。
    • 预分配桶空间(reserve())减少 rehash 次数。
    • 调整负载因子(max_load_factor())优化内存使用。
    • 自定义高效的哈希函数和比较器。

📌 五、常见陷阱与解决方案

1. 修改 std::set 中的元素

  • 问题std::set 中的元素不可直接修改,否则会破坏排序。
  • 解决方案:删除旧元素并插入新元素。
std::set<int> s = {1, 2, 3};
s.erase(2);
s.insert(4);

2. std::unordered_set 的 rehash

  • 问题:插入元素可能导致 rehash,迭代器失效。
  • 解决方案:避免在遍历时直接修改容器,或使用临时容器。
for (auto it = us.begin(); it != us.end(); ) {
    if (*it % 2 == 0) {
        it = us.erase(it);  // 安全删除
    } else {
        ++it;
    }
}

3. 自定义类型的哈希冲突

  • 问题:自定义类型未定义哈希函数或比较器。
  • 解决方案:重载 operator== 和自定义哈希函数。
struct Key {
    int a, b;
    bool operator==(const Key& other) const {
        return a == other.a && b == other.b;
    }
};

struct KeyHash {
    std::size_t operator()(const Key& k) const {
        return std::hash<int>()(k.a) ^ (std::hash<int>()(k.b) << 1);
    }
};

std::unordered_set<Key, KeyHash> mySet;

📌 六、典型应用场景

1. 去重场景

  • 适用场景:统计唯一元素数量。
std::unordered_set<std::string> uniqueWords;
std::string text = "hello world hello";
std::istringstream iss(text);
std::string word;
while (iss >> word) {
    uniqueWords.insert(word);
}
std::cout << "Unique words: " << uniqueWords.size() << "\n";

2. 快速查找

  • 适用场景:验证元素是否存在。
std::set<int> blacklist = {1001, 1002, 1003};
if (blacklist.find(1001) != blacklist.end()) {
    std::cout << "Blocked!\n";
}

3. 有序集合操作

  • 适用场景:需要按顺序处理元素。
std::set<int> sortedData = {5, 1, 3};
for (int val : sortedData) {
    std::cout << val << " ";  // 输出 1 3 5
}

🧠 总结

容器 优点 缺点 适用场景
std::set 有序、稳定迭代器 插入/删除较慢 需要排序、范围查询
std::unordered_set 查找/插入快 无序、迭代器可能失效 快速查找、去重

网站公告

今日签到

点亮在社区的每一天
去签到