std::set 是 C++ 標(biāo)準(zhǔn)庫(kù)中的關(guān)聯(lián)容器，它提供了一種存儲(chǔ)唯一元素的有序集合。它提供了高效的插入、刪除和查找操作，并且能夠自動(dòng)維護(hù)元素的有序性和唯一性。

一、底層實(shí)現(xiàn)

std::set 的底層原理是基于紅黑樹(shù)（Red-Black Tree）。紅黑樹(shù)是一種自平衡的二叉搜索樹(shù)，保證了樹(shù)的平衡性，從而保證了插入、刪除和查找操作的時(shí)間復(fù)雜度為 O(log n)。它滿足以下性質(zhì)：

1、 每個(gè)節(jié)點(diǎn)要么是紅色，要么是黑色。
2、 根節(jié)點(diǎn)是黑色的。（插入的第一個(gè)元素）
3、 所有葉子節(jié)點(diǎn)（NIL 節(jié)點(diǎn)）都是黑色的。
4、 如果一個(gè)節(jié)點(diǎn)是紅色的，則它的兩個(gè)子節(jié)點(diǎn)都是黑色的。
5、 對(duì)于每個(gè)節(jié)點(diǎn)，從該節(jié)點(diǎn)到其后代葉子節(jié)點(diǎn)的簡(jiǎn)單路徑上，黑色節(jié)點(diǎn)的數(shù)量都相同。

在 std::set 中，每個(gè)元素都被 插入到紅黑樹(shù)中作為一個(gè)節(jié)點(diǎn)。當(dāng)插入一個(gè)新元素時(shí)，std::set 會(huì)根據(jù)元素值的大小將其插入到合適的位置，同時(shí)保持紅黑樹(shù)的平衡性。在紅黑樹(shù)中查找元素時(shí)，根據(jù)紅黑樹(shù)的特性，可以通過(guò)二分查找的方式高效地定位到目標(biāo)元素。
由于紅黑樹(shù)是一種高效的自平衡二叉搜索樹(shù)，因此 std::set 能夠提供高效的插入、刪除和查找操作，同時(shí)保持元素的有序性和唯一性。

二、成員函數(shù)

std::set提供了一系列成員函數(shù)來(lái)操作集合。

• insert: 向集合中插入元素。
• emplace: 在集合中就地構(gòu)造元素。
• erase: 從集合中刪除指定元素。
• find: 查找集合中是否存在指定元素。
• count: 返回集合中與指定元素相等的元素的數(shù)量（通常為0或1）。
• clear: 清空集合中的所有元素。
• size: 返回集合中元素的數(shù)量。
• empty: 檢查集合是否為空。
• swap: 交換兩個(gè)集合的內(nèi)容。
• begin: 返回指向集合中第一個(gè)元素的迭代器。
• end: 返回指向集合中最后一個(gè)元素之后位置的迭代器。
• lower_bound: 返回指向第一個(gè)不小于給定鍵值的元素的迭代器。
• upper_bound: 返回指向第一個(gè)大于給定鍵值的元素的迭代器。
• equal_range: 返回一個(gè)范圍，其中包含所有與給定鍵值相等的元素。
• max_size: 返回集合能容納的最大元素?cái)?shù)量。

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

三、自定義排序規(guī)則

std::set 默認(rèn)是根據(jù)元素的大小進(jìn)行排序的，采用的是嚴(yán)格弱序（Strict Weak Ordering）的比較方式。這意味著元素必須支持 < 運(yùn)算符，元素按照升序排列。

可以通過(guò)提供自定義的比較函數(shù)或者函數(shù)對(duì)象來(lái)實(shí)現(xiàn)排序規(guī)則。需要兩個(gè)步驟：
1、 定義比較函數(shù)或者函數(shù)對(duì)象：
比較函數(shù)：定義一個(gè)函數(shù)，接受兩個(gè)參數(shù)，比較它們的大小，并返回 true 或 false，表示它們的順序關(guān)系。
函數(shù)對(duì)象（Functor）：定義一個(gè)類，重載 operator()，使得對(duì)象可以像函數(shù)一樣被調(diào)用，在其中實(shí)現(xiàn)比較邏輯。

2、 傳遞比較函數(shù)或者函數(shù)對(duì)象給 std::set 構(gòu)造函數(shù)：
在創(chuàng)建 std::set 對(duì)象時(shí)，通過(guò)傳遞比較函數(shù)或者函數(shù)對(duì)象作為第二個(gè)參數(shù)，告訴集合如何比較元素的順序。

#include <iostream>
#include <set>

// 自定義比較函數(shù)
bool customCompare(int a, int b) {
    // 實(shí)現(xiàn)自定義的比較邏輯，這里以整數(shù)的絕對(duì)值大小為例
    return abs(a) < abs(b);
}

// 自定義函數(shù)對(duì)象（Functor）
struct CustomComparator {
    bool operator()(int a, int b) const {
        // 實(shí)現(xiàn)自定義的比較邏輯，這里以整數(shù)的平方大小為例
        return (a * a) < (b * b);
    }
};

int main() {
    // 使用自定義比較函數(shù)創(chuàng)建 std::set
    std::set<int, decltype(&customCompare)> customSet(customCompare);

    // 使用自定義函數(shù)對(duì)象創(chuàng)建 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);

    // 遍歷輸出結(jié)果
    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;
}

四、自定義對(duì)象排序

當(dāng) std::set 中存儲(chǔ)的元素是自定義對(duì)象時(shí)，需要重載 < 運(yùn)算符，以便 std::set 能夠?qū)?duì)象進(jìn)行比較和排序。重載 < 運(yùn)算符的目的是定義對(duì)象之間的比較規(guī)則，以確定它們?cè)诩现械捻樞?。這樣，std::set 就可以使用這些規(guī)則來(lái)維護(hù)集合的有序性。
下面是一個(gè)示例，演示了如何定義一個(gè)自定義類型的 Person 對(duì)象，并在 std::set 中使用自定義的比較函數(shù)進(jìn)行排序：

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

// 定義一個(gè)自定義的 Person 類
class Person {
private:
    std::string name;
    int age;

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

    // 重載 < 運(yùn)算符，用于自定義對(duì)象的比較規(guī)則
    bool operator<(const Person& other) const {
        // 按照年齡進(jìn)行比較
        return age < other.age;
    }

    // 為了便于輸出，重載 << 運(yùn)算符
    friend std::ostream& operator<<(std::ostream& os, const Person& person) {
        os << "Name: " << person.name << ", Age: " << person.age;
        return os;
    }
};

int main() {
    // 創(chuàng)建一個(gè)存儲(chǔ) Person 對(duì)象的 std::set 容器，并使用自定義的比較函數(shù)進(jìn)行排序
    std::set<Person> people;

    // 向集合中插入一些 Person 對(duì)象
    people.insert(Person("Alice", 30));
    people.insert(Person("Bob", 25));
    people.insert(Person("Charlie", 35));

    // 遍歷輸出集合中的元素，由于使用了自定義的比較規(guī)則，輸出時(shí)會(huì)按照年齡升序排列
    for (const auto& person : people) {
        std::cout << person << std::endl;
    }

    return 0;
}

在這個(gè)示例中，Person 類具有 name 和 age 兩個(gè)屬性，我們通過(guò)重載 < 運(yùn)算符來(lái)定義了對(duì)象之間的比較規(guī)則，按照年齡進(jìn)行比較。然后，我們創(chuàng)建了一個(gè) std::set<Person> 容器，并向其中插入了幾個(gè) Person 對(duì)象。由于我們使用了自定義的比較函數(shù)，因此在輸出容器中的元素時(shí)，它們會(huì)按照年齡的升序排列。

五、性能問(wèn)題

std::set 在插入、刪除和查找等操作上具有穩(wěn)定且良好的性能特征，適用于需要高效管理有序唯一元素集合的場(chǎng)景。然而，在空間效率方面，它可能不如其他數(shù)據(jù)結(jié)構(gòu)（如 std::unordered_set）那么優(yōu)越。因此，在選擇數(shù)據(jù)結(jié)構(gòu)時(shí)，需要根據(jù)具體的需求權(quán)衡其性能特征。

1、 插入和刪除操作的性能：
插入和刪除操作的時(shí)間復(fù)雜度為 O(log n)，其中 n 是集合中的元素?cái)?shù)量。這是因?yàn)榧t黑樹(shù)是一種自平衡的二叉搜索樹(shù)，插入和刪除操作會(huì)導(dǎo)致樹(shù)的重新平衡，但是由于紅黑樹(shù)的特性，重新平衡的代價(jià)是受控的。
因此，std::set 在插入和刪除方面的性能比較穩(wěn)定，不受集合大小的影響。

2、 查找操作的性能：
查找操作的時(shí)間復(fù)雜度也是 O(log n)，因?yàn)榧t黑樹(shù)具有良好的平衡性，可以保證在平均情況下快速地查找元素。
std::set 提供了高效的查找功能，適用于需要快速檢索元素的場(chǎng)景。

3、 迭代器的性能：
std::set 的迭代器是雙向迭代器，支持前向和后向遍歷，其性能與集合大小無(wú)關(guān)，是常數(shù)時(shí)間復(fù)雜度的操作。
這意味著在遍歷 std::set 中的元素時(shí)，無(wú)論集合大小如何，迭代器的操作都非常高效。

4、 內(nèi)存占用：
std::set 使用紅黑樹(shù)作為底層數(shù)據(jù)結(jié)構(gòu)，它是一種高效的平衡二叉搜索樹(shù)，但是相對(duì)于其他數(shù)據(jù)結(jié)構(gòu)（如哈希表），它可能會(huì)占用更多的內(nèi)存。
紅黑樹(shù)需要維護(hù)額外的節(jié)點(diǎn)信息以保持平衡，因此在存儲(chǔ)相同數(shù)量的元素時(shí)，std::set 可能會(huì)占用更多的內(nèi)存空間。

到此這篇關(guān)于C++實(shí)現(xiàn)std::set的示例項(xiàng)目的文章就介紹到這了,更多相關(guān)C++ std::set內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論