MK
摩柯社区 - 一个极简的技术知识社区
AI 面试

C++ STL 容器 set 的排序原理剖析

2021-03-291.6k 阅读

C++ STL 容器 set 的基本概念

在 C++ 的标准模板库（STL）中，set 是一种关联式容器。它存储的元素具有唯一性，即容器中不会出现重复的元素。set 的主要特点是能够自动对元素进行排序，这使得在查找、插入和删除元素时具有较高的效率。

set 基于红黑树（Red - Black Tree）数据结构实现。红黑树是一种自平衡的二叉搜索树，它保证了在最坏情况下，树的高度为 $O(\log n)$，其中 $n$ 是树中节点的数量。这就为 set 容器的各种操作提供了高效的时间复杂度。

set 的定义与初始化

在使用 set 之前，需要包含 <set> 头文件。以下是几种常见的定义和初始化 set 的方式：

#include <set>
#include <iostream>

int main() {
    // 定义一个空的 set
    std::set<int> s1;

    // 定义并初始化一个 set
    std::set<int> s2 = {1, 3, 5, 7, 9};

    // 通过另一个 set 初始化
    std::set<int> s3(s2);

    // 通过迭代器范围初始化
    std::set<int> s4(s2.begin(), s2.end());

    return 0;
}

set 的排序原理剖析

基于红黑树的排序

如前文所述，set 是基于红黑树实现的。红黑树作为一种二叉搜索树，其节点的左子树所有节点的值小于该节点的值，右子树所有节点的值大于该节点的值。这种特性使得红黑树天然具备排序的能力。

在 set 中插入元素时，新元素会按照二叉搜索树的规则找到合适的插入位置。例如，当向一个 set 中插入元素 x 时，从根节点开始比较：

  1. 如果根节点为空，则 x 成为新的根节点。
  2. 如果 x 小于根节点的值，则继续在根节点的左子树中查找插入位置。
  3. 如果 x 大于根节点的值，则继续在根节点的右子树中查找插入位置。

当找到合适的空位置时，将 x 插入。插入后，红黑树会通过旋转和颜色调整等操作来保持其自平衡特性，以确保树的高度始终保持在 $O(\log n)$。

以下是一个简化的红黑树插入和排序的示例代码（仅为示意，并非完整的红黑树实现）：

// 红黑树节点定义
struct RBNode {
    int value;
    bool isRed;
    RBNode* left;
    RBNode* right;
    RBNode* parent;

    RBNode(int v) : value(v), isRed(true), left(nullptr), right(nullptr), parent(nullptr) {}
};

// 红黑树插入操作（简化版，未包含平衡调整）
void insert(RBNode*& root, int value) {
    RBNode* newNode = new RBNode(value);
    if (root == nullptr) {
        root = newNode;
        return;
    }
    RBNode* current = root;
    while (true) {
        if (value < current->value) {
            if (current->left == nullptr) {
                current->left = newNode;
                newNode->parent = current;
                break;
            }
            current = current->left;
        } else {
            if (current->right == nullptr) {
                current->right = newNode;
                newNode->parent = current;
                break;
            }
            current = current->right;
        }
    }
}

// 中序遍历红黑树（用于验证排序结果）
void inorderTraversal(RBNode* root) {
    if (root == nullptr) return;
    inorderTraversal(root->left);
    std::cout << root->value << " ";
    inorderTraversal(root->right);
}

int main() {
    RBNode* root = nullptr;
    insert(root, 5);
    insert(root, 3);
    insert(root, 7);
    insert(root, 2);
    insert(root, 4);
    insert(root, 6);
    insert(root, 8);

    std::cout << "In - order traversal (sorted): ";
    inorderTraversal(root);
    std::cout << std::endl;

    return 0;
}

自定义比较函数

set 默认使用 std::less<T> 作为比较函数，对于内置类型（如 int、double 等），std::less<T> 实现了从小到大的排序。然而，当存储自定义类型时，就需要提供自定义的比较函数。

自定义比较函数需要满足严格弱序（Strict Weak Ordering）的要求。严格弱序是一种二元关系，它具有以下性质：

  1. 非自反性：对于所有的 a，a < a 为 false。
  2. 传递性：如果 a < b 且 b < c，那么 a < c。
  3. 反对称性：如果 a < b，那么 b < a 为 false。
  4. 可传递的不可比性：如果 a 与 b 不可比（即 !(a < b) 且 !(b < a)），且 b 与 c 不可比，那么 a 与 c 不可比。

下面是一个自定义比较函数的示例，用于对自定义类型 Point 按照到原点的距离进行排序：

#include <set>
#include <iostream>
#include <cmath>

struct Point {
    int x;
    int y;

    Point(int a, int b) : x(a), y(b) {}
};

// 自定义比较函数
struct CompareByDistance {
    bool operator()(const Point& p1, const Point& p2) const {
        double dist1 = std::sqrt(p1.x * p1.x + p1.y * p1.y);
        double dist2 = std::sqrt(p2.x * p2.x + p2.y * p2.y);
        return dist1 < dist2;
    }
};

int main() {
    std::set<Point, CompareByDistance> points;
    points.insert(Point(3, 4));
    points.insert(Point(1, 1));
    points.insert(Point(5, 0));

    for (const auto& p : points) {
        std::cout << "(" << p.x << ", " << p.y << ") ";
    }
    std::cout << std::endl;

    return 0;
}

在上述代码中，CompareByDistance 结构体重载了 () 运算符，实现了自定义的比较逻辑。std::set<Point, CompareByDistance> 使用这个自定义比较函数对 Point 对象进行排序。

set 排序相关的操作及其复杂度

插入操作（insert）

set 的插入操作时间复杂度为 $O(\log n)$，其中 $n$ 是 set 中元素的数量。这是因为插入操作首先要在红黑树中查找合适的插入位置，查找过程的时间复杂度为 $O(\log n)$，插入后可能需要进行的平衡调整操作也能在 $O(\log n)$ 时间内完成。

#include <set>
#include <iostream>

int main() {
    std::set<int> s;
    s.insert(5);
    s.insert(3);
    s.insert(7);

    for (int num : s) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

删除操作（erase）

set 的删除操作时间复杂度同样为 $O(\log n)$。删除元素时，首先要在红黑树中找到该元素，这一步的时间复杂度为 $O(\log n)$。找到元素后，删除操作可能会破坏红黑树的平衡，需要进行旋转和颜色调整等操作来恢复平衡，这些操作的时间复杂度也是 $O(\log n)$。

#include <set>
#include <iostream>

int main() {
    std::set<int> s = {1, 3, 5, 7, 9};
    s.erase(5);

    for (int num : s) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

查找操作（find）

set 的查找操作时间复杂度为 $O(\log n)$。由于 set 基于红黑树实现，在红黑树中查找一个元素的过程与插入操作的查找过程类似，都是从根节点开始，根据元素值与节点值的比较，向左或向右子树移动，直到找到目标元素或确定目标元素不存在，整个过程的时间复杂度为 $O(\log n)$。

#include <set>
#include <iostream>

int main() {
    std::set<int> s = {1, 3, 5, 7, 9};
    auto it = s.find(5);
    if (it != s.end()) {
        std::cout << "Element found: " << *it << std::endl;
    } else {
        std::cout << "Element not found" << std::endl;
    }

    return 0;
}

set 与其他容器排序的比较

与 vector 排序的比较

std::vector 是一种序列式容器，它本身并不自动排序。如果需要对 vector 中的元素进行排序，可以使用 std::sort 算法。std::sort 的平均时间复杂度为 $O(n \log n)$，最坏情况下时间复杂度为 $O(n^2)$（对于某些不适合快速排序的特定数据分布）。

与 set 相比，vector 的优点在于它可以存储重复元素，并且在需要随机访问元素时效率较高。然而，在频繁进行插入和删除操作且需要保持元素有序的场景下，set 由于其基于红黑树的自动排序和高效的插入删除操作，通常表现更好。

#include <vector>
#include <algorithm>
#include <iostream>

int main() {
    std::vector<int> v = {5, 3, 7, 1, 9};
    std::sort(v.begin(), v.end());

    for (int num : v) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

与 map 排序的比较

std::map 也是一种关联式容器，它基于红黑树实现，并且按键（key）自动排序。map 与 set 的排序原理类似，都是利用红黑树的特性。不同之处在于，map 存储的是键值对（key - value pairs），而 set 只存储单一元素。

在实际应用中，如果需要根据某个键来存储和查找对应的值，并且要求按键自动排序，那么 map 是更好的选择；如果只需要存储不重复的元素并自动排序，set 则更为合适。

#include <map>
#include <iostream>

int main() {
    std::map<int, std::string> m;
    m[3] = "three";
    m[1] = "one";
    m[2] = "two";

    for (const auto& pair : m) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

实际应用场景中的 set 排序

去重与排序

在处理大量数据时，常常需要对数据进行去重并排序。例如，在统计文本文件中出现的单词，并按字母顺序输出，set 就非常适用。

#include <set>
#include <iostream>
#include <fstream>
#include <sstream>

int main() {
    std::set<std::string> words;
    std::ifstream file("example.txt");
    std::string line;
    while (std::getline(file, line)) {
        std::istringstream iss(line);
        std::string word;
        while (iss >> word) {
            words.insert(word);
        }
    }

    for (const auto& w : words) {
        std::cout << w << std::endl;
    }

    return 0;
}

查找有序数据中的特定元素

在一些需要频繁查找有序数据集中特定元素的场景下，set 可以提供高效的查找性能。例如，在一个有序的学生成绩列表中查找某个特定成绩的学生。

#include <set>
#include <iostream>

struct Student {
    std::string name;
    int score;

    Student(const std::string& n, int s) : name(n), score(s) {}
};

struct CompareByScore {
    bool operator()(const Student& s1, const Student& s2) const {
        return s1.score < s2.score;
    }
};

int main() {
    std::set<Student, CompareByScore> students;
    students.insert(Student("Alice", 85));
    students.insert(Student("Bob", 90));
    students.insert(Student("Charlie", 78));

    auto it = students.find(Student("", 90));
    if (it != students.end()) {
        std::cout << "Student with score 90 found: " << it->name << std::endl;
    } else {
        std::cout << "Student with score 90 not found" << std::endl;
    }

    return 0;
}

通过对 C++ STL 容器 set 的排序原理进行深入剖析，我们了解了其基于红黑树的实现方式、自定义比较函数的应用、相关操作的复杂度以及在实际应用场景中的使用。掌握这些知识，能帮助我们在编程中更加高效地使用 set 容器，优化算法性能。