面试题：C++ set唯一性实现原理及底层优化

C++ STL 中 set 保证元素唯一性的底层实现逻辑

STL 中的 set 通常基于红黑树实现。红黑树是一种自平衡的二叉搜索树，它具有以下性质：

每个节点要么是红色，要么是黑色。
根节点是黑色。
每个叶节点（NIL 节点，空节点）是黑色。
如果一个节点是红色的，则它的两个子节点都是黑色。
从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

set 利用红黑树的这些性质来保证元素的有序性和唯一性。在插入元素时，set 首先会在红黑树中查找该元素是否已存在。如果不存在，则按照二叉搜索树的规则将新元素插入到合适的位置，并通过一系列的旋转和颜色调整操作来维护红黑树的性质。

例如，插入操作的简化伪代码如下：

template <typename Key, typename Compare, typename Allocator>
void set<Key, Compare, Allocator>::insert(const Key& value) {
    node* new_node = create_node(value);
    node* current = root;
    node* parent = nullptr;

    while (current != nullptr) {
        parent = current;
        if (compare(value, current->value)) {
            current = current->left;
        } else if (compare(current->value, value)) {
            current = current->right;
        } else {
            // 元素已存在，不插入
            destroy_node(new_node);
            return;
        }
    }

    new_node->parent = parent;
    if (parent == nullptr) {
        root = new_node;
    } else if (compare(value, parent->value)) {
        parent->left = new_node;
    } else {
        parent->right = new_node;
    }

    insert_fixup(new_node);
}

insert_fixup 函数负责在插入新节点后通过旋转和颜色调整来维护红黑树的性质。

在高并发环境下对 set 进行线程安全的封装

设计思路

互斥锁保护：使用互斥锁（如 std::mutex）来保护 set 的关键操作，如插入、删除和查找。在进入这些操作前锁定互斥锁，操作完成后解锁。
RAII 机制：利用 RAII（Resource Acquisition Is Initialization）机制，通过 std::lock_guard 或 std::unique_lock 来自动管理锁的生命周期，避免手动锁定和解锁可能导致的错误。
封装接口：将 set 封装在一个类中，并提供线程安全的接口方法，隐藏 set 的内部实现细节。

关键代码片段

#include <set>
#include <mutex>
#include <memory>

template <typename Key, typename Compare = std::less<Key>, typename Allocator = std::allocator<Key>>
class ThreadSafeSet {
public:
    void insert(const Key& value) {
        std::lock_guard<std::mutex> lock(mutex_);
        set_.insert(value);
    }

    bool contains(const Key& value) const {
        std::lock_guard<std::mutex> lock(mutex_);
        return set_.find(value) != set_.end();
    }

    void erase(const Key& value) {
        std::lock_guard<std::mutex> lock(mutex_);
        set_.erase(value);
    }

private:
    std::set<Key, Compare, Allocator> set_;
    mutable std::mutex mutex_;
};

在上述代码中，ThreadSafeSet 类封装了一个 std::set，并使用 std::mutex 来保护对 set 的操作。std::lock_guard 在构造时自动锁定互斥锁，在析构时自动解锁，确保了线程安全。

星途面试题库

面试题：C++ set唯一性实现原理及底层优化

知识考点

面试题答案

C++ STL 中 set 保证元素唯一性的底层实现逻辑

在高并发环境下对 set 进行线程安全的封装

设计思路

关键代码片段