面试题：C++ set唯一性在不同场景下的应用

Question

假设你正在开发一个系统，需要存储一系列用户ID，要求不能有重复ID。使用C++ 的set实现该功能，并阐述在面临大量数据插入时，如何优化set以保证其唯一性判断的效率，同时考虑如何处理用户ID的动态删除和查询操作以维持唯一性机制不受影响。

Answer 1

使用C++ set实现存储唯一用户ID

#include <iostream>
#include <set>

int main() {
    std::set<int> userIds;

    // 插入用户ID
    userIds.insert(1);
    userIds.insert(2);
    userIds.insert(1); // 重复插入，不会生效

    // 遍历集合
    for (int id : userIds) {
        std::cout << id << std::endl;
    }

    return 0;
}

大量数据插入时的优化

1. 预分配内存：在插入大量数据之前，可以使用reserve方法预分配足够的内存空间，减少插入过程中的动态内存分配次数。

std::set<int> userIds;
userIds.reserve(10000); // 假设预分配10000个元素的空间

2. 批量插入：使用insert的范围插入版本，将多个元素一次性插入集合，减少每次插入时的开销。

std::vector<int> newIds = {3, 4, 5};
userIds.insert(newIds.begin(), newIds.end());

处理动态删除和查询操作

1. 动态删除：使用erase方法删除指定的用户ID，set会自动维持唯一性。

userIds.erase(2); // 删除ID为2的用户

2. 查询操作：使用find方法查询用户ID是否存在，set的查找操作平均时间复杂度为O(log n)。

if (userIds.find(1) != userIds.end()) {
    std::cout << "用户ID 1存在" << std::endl;
} else {
    std::cout << "用户ID 1不存在" << std::endl;
}

通过上述方法，可以有效优化set在大量数据插入时的性能，并保证在动态删除和查询操作中维持唯一性机制不受影响。