C++实现std::set的示例项目_C/C++

std::set 是 c++ 标准库中的关联容器，它提供了一种存储唯一元素的有序集合。它提供了高效的插入、删除和查找操作，并且能够自动维护元素的有序性和唯一性。

一、底层实现

std::set 的底层原理是基于红黑树（red-black tree）。红黑树是一种自平衡的二叉搜索树，保证了树的平衡性，从而保证了插入、删除和查找操作的时间复杂度为 o(log n)。它满足以下性质：

1、每个节点要么是红色，要么是黑色。
2、根节点是黑色的。（插入的第一个元素）
3、所有叶子节点（nil 节点）都是黑色的。
4、如果一个节点是红色的，则它的两个子节点都是黑色的。
5、对于每个节点，从该节点到其后代叶子节点的简单路径上，黑色节点的数量都相同。

在 std::set 中，每个元素都被插入到红黑树中作为一个节点。当插入一个新元素时，std::set 会根据元素值的大小将其插入到合适的位置，同时保持红黑树的平衡性。在红黑树中查找元素时，根据红黑树的特性，可以通过二分查找的方式高效地定位到目标元素。
由于红黑树是一种高效的自平衡二叉搜索树，因此 std::set 能够提供高效的插入、删除和查找操作，同时保持元素的有序性和唯一性。

二、成员函数

std::set提供了一系列成员函数来操作集合。

insert: 向集合中插入元素。
emplace: 在集合中就地构造元素。
erase: 从集合中删除指定元素。
find: 查找集合中是否存在指定元素。
count: 返回集合中与指定元素相等的元素的数量（通常为0或1）。
clear: 清空集合中的所有元素。
size: 返回集合中元素的数量。
empty: 检查集合是否为空。
swap: 交换两个集合的内容。
begin: 返回指向集合中第一个元素的迭代器。
end: 返回指向集合中最后一个元素之后位置的迭代器。
lower_bound: 返回指向第一个不小于给定键值的元素的迭代器。
upper_bound: 返回指向第一个大于给定键值的元素的迭代器。
equal_range: 返回一个范围，其中包含所有与给定键值相等的元素。
max_size: 返回集合能容纳的最大元素数量。

demo演示：

std::set<int> set1;
set1.insert(1);
set1.insert(2);
set1.insert(3);
set1.insert(4);
std::cout<<set1.size()<<std::endl; // 4
std::cout<<set1.empty()<<std::endl; // 0
std::cout<<*set1.find(2)<<std::endl; // 2
set1.erase(2);
std::cout<<(set1.find(2)==set1.end())<<std::endl; // 1
std::cout<<set1.count(3)<<std::endl; // 1
auto lower = set1.lower_bound(3);
auto upper = set1.upper_bound(3);
std::cout << "lower bound of 3: " << *lower << std::endl; // lower bound of 3: 3
std::cout << "upper bound of 3: " << *upper << std::endl; // upper bound of 4: 4
std::set<int> set2;
set2.swap(set1);
std::cout<<set1.size()<<" "<<set2.size()<<std::endl; // 0 3
std::cout<<set1.max_size()<<std::endl; // 230584300921369395
for (auto it = set2.begin(); it != set2.end(); ++it) {
    std::cout << *it << " "<<std::endl; // 1 3 4
}
auto range = set2.equal_range(3);
std::cout<<*range.first<<std::endl; // 3

三、自定义排序规则

std::set 默认是根据元素的大小进行排序的，采用的是严格弱序（strict weak ordering）的比较方式。这意味着元素必须支持 < 运算符，元素按照升序排列。

可以通过提供自定义的比较函数或者函数对象来实现排序规则。需要两个步骤：
1、 定义比较函数或者函数对象：
比较函数：定义一个函数，接受两个参数，比较它们的大小，并返回 true 或 false，表示它们的顺序关系。
函数对象（functor）：定义一个类，重载 operator()，使得对象可以像函数一样被调用，在其中实现比较逻辑。

2、 传递比较函数或者函数对象给 std::set 构造函数：
在创建 std::set 对象时，通过传递比较函数或者函数对象作为第二个参数，告诉集合如何比较元素的顺序。

#include <iostream>
#include <set>

// 自定义比较函数
bool customcompare(int a, int b) {
    // 实现自定义的比较逻辑，这里以整数的绝对值大小为例
    return abs(a) < abs(b);
}

// 自定义函数对象（functor）
struct customcomparator {
    bool operator()(int a, int b) const {
        // 实现自定义的比较逻辑，这里以整数的平方大小为例
        return (a * a) < (b * b);
    }
};

int main() {
    // 使用自定义比较函数创建 std::set
    std::set<int, decltype(&customcompare)> customset(customcompare);

    // 使用自定义函数对象创建 std::set
    std::set<int, customcomparator> functorset;

    // 插入元素
    customset.insert(5);
    customset.insert(-3);
    customset.insert(2);

    functorset.insert(5);
    functorset.insert(-3);
    functorset.insert(2);

    // 遍历输出结果
    std::cout << "custom compare function set: ";
    for (int num : customset) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    std::cout << "functor set: ";
    for (int num : functorset) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

四、自定义对象排序

当 std::set 中存储的元素是自定义对象时，需要重载 < 运算符，以便 std::set 能够对对象进行比较和排序。重载 < 运算符的目的是定义对象之间的比较规则，以确定它们在集合中的顺序。这样，std::set 就可以使用这些规则来维护集合的有序性。
下面是一个示例，演示了如何定义一个自定义类型的 person 对象，并在 std::set 中使用自定义的比较函数进行排序：

#include <iostream>
#include <set>
#include <string>

// 定义一个自定义的 person 类
class person {
private:
    std::string name;
    int age;

public:
    person(std::string name, int age) : name(name), age(age) {}

    // 重载 < 运算符，用于自定义对象的比较规则
    bool operator<(const person& other) const {
        // 按照年龄进行比较
        return age < other.age;
    }

    // 为了便于输出，重载 << 运算符
    friend std::ostream& operator<<(std::ostream& os, const person& person) {
        os << "name: " << person.name << ", age: " << person.age;
        return os;
    }
};

int main() {
    // 创建一个存储 person 对象的 std::set 容器，并使用自定义的比较函数进行排序
    std::set<person> people;

    // 向集合中插入一些 person 对象
    people.insert(person("alice", 30));
    people.insert(person("bob", 25));
    people.insert(person("charlie", 35));

    // 遍历输出集合中的元素，由于使用了自定义的比较规则，输出时会按照年龄升序排列
    for (const auto& person : people) {
        std::cout << person << std::endl;
    }

    return 0;
}

在这个示例中，person 类具有 name 和 age 两个属性，我们通过重载 < 运算符来定义了对象之间的比较规则，按照年龄进行比较。然后，我们创建了一个 std::set<person> 容器，并向其中插入了几个 person 对象。由于我们使用了自定义的比较函数，因此在输出容器中的元素时，它们会按照年龄的升序排列。

五、性能问题

std::set 在插入、删除和查找等操作上具有稳定且良好的性能特征，适用于需要高效管理有序唯一元素集合的场景。然而，在空间效率方面，它可能不如其他数据结构（如 std::unordered_set）那么优越。因此，在选择数据结构时，需要根据具体的需求权衡其性能特征。

1、 插入和删除操作的性能：
插入和删除操作的时间复杂度为 o(log n)，其中 n 是集合中的元素数量。这是因为红黑树是一种自平衡的二叉搜索树，插入和删除操作会导致树的重新平衡，但是由于红黑树的特性，重新平衡的代价是受控的。
因此，std::set 在插入和删除方面的性能比较稳定，不受集合大小的影响。

2、 查找操作的性能：
查找操作的时间复杂度也是 o(log n)，因为红黑树具有良好的平衡性，可以保证在平均情况下快速地查找元素。
std::set 提供了高效的查找功能，适用于需要快速检索元素的场景。

3、 迭代器的性能：
std::set 的迭代器是双向迭代器，支持前向和后向遍历，其性能与集合大小无关，是常数时间复杂度的操作。
这意味着在遍历 std::set 中的元素时，无论集合大小如何，迭代器的操作都非常高效。

4、 内存占用：
std::set 使用红黑树作为底层数据结构，它是一种高效的平衡二叉搜索树，但是相对于其他数据结构（如哈希表），它可能会占用更多的内存。
红黑树需要维护额外的节点信息以保持平衡，因此在存储相同数量的元素时，std::set 可能会占用更多的内存空间。

到此这篇关于c++实现std::set的示例项目的文章就介绍到这了,更多相关c++ std::set内容请搜索代码网以前的文章或继续浏览下面的相关文章希望大家以后多多支持代码网！