C++ set函數(shù)在算法設(shè)計中的應用技巧

在C++中，set是一個關(guān)聯(lián)容器，它包含一組唯一的元素，并按照特定的排序規(guī)則進行存儲。set在算法設(shè)計中的應用主要體現(xiàn)在以下幾個方面：

1. 去重：由于set中的元素都是唯一的，因此可以使用set來實現(xiàn)去重操作。將一個容器中的元素插入到set中，然后再從set中取出元素，這樣就可以得到一個去重后的序列。

#include<iostream>
#include<vector>
#include <set>
using namespace std;

int main() {
    vector<int> nums = {1, 2, 3, 4, 4, 5, 6, 6, 7};
    set<int> s(nums.begin(), nums.end());
    for (int num : s) {
        cout<< num << " ";
    }
    return 0;
}

2. 查找：set提供了高效的查找操作，可以在O(log n)的時間復雜度內(nèi)完成查找。如果需要在一個有序的序列中查找某個元素，可以使用set來實現(xiàn)。

#include<iostream>
#include <set>
using namespace std;

int main() {
    set<int> s = {1, 2, 3, 4, 5, 6, 7};
    int target = 4;
    if (s.find(target) != s.end()) {
        cout << "Found "<< target<< endl;
    } else {
        cout << "Not found"<< endl;
    }
    return 0;
}

3. 區(qū)間查詢：set還支持區(qū)間查詢，可以在O(log n)的時間復雜度內(nèi)找到某個區(qū)間內(nèi)的所有元素。例如，可以使用lower_bound和upper_bound函數(shù)來查找一個區(qū)間內(nèi)的所有元素。

#include<iostream>
#include <set>
using namespace std;

int main() {
    set<int> s = {1, 2, 3, 4, 5, 6, 7};
    int lower = 3, upper = 6;
    auto it_low = s.lower_bound(lower);
    auto it_up = s.upper_bound(upper);
    for (auto it = it_low; it != it_up; ++it) {
        cout << *it << " ";
    }
    return 0;
}

4. 最大/最小值：set中的第一個元素是最小值，最后一個元素是最大值?？梢酝ㄟ^*s.begin()和*s.rbegin()來獲取最小值和最大值。

#include<iostream>
#include <set>
using namespace std;

int main() {
    set<int> s = {1, 2, 3, 4, 5, 6, 7};
    cout << "Min: " << *s.begin()<< endl;
    cout << "Max: " << *s.rbegin()<< endl;
    return 0;
}

5. 排序：set會自動對其中的元素進行排序。如果需要對一個序列進行排序，可以將其插入到set中，然后再從set中取出元素，這樣就可以得到一個有序的序列。

#include<iostream>
#include<vector>
#include <set>
using namespace std;

int main() {
    vector<int> nums = {7, 3, 1, 6, 4, 2, 5};
    set<int> s(nums.begin(), nums.end());
    for (int num : s) {
        cout<< num << " ";
    }
    return 0;
}

總之，set在算法設(shè)計中的應用非常廣泛，可以幫助我們實現(xiàn)去重、查找、區(qū)間查詢、最大/最小值查詢和排序等功能。