c++

C++ set函数在算法设计中的应用技巧

小樊
82
2024-09-10 19:59:32
栏目: 编程语言

在C++中,set是一个关联容器,它包含一组唯一的元素,并按照特定的排序规则进行存储。set在算法设计中的应用主要体现在以下几个方面:

  1. 去重:由于set中的元素都是唯一的,因此可以使用set来实现去重操作。将一个容器中的元素插入到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;
}
  1. 查找:set提供了高效的查找操作,可以在O(log n)的时间复杂度内完成查找。如果需要在一个有序的序列中查找某个元素,可以使用set来实现。
#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;
}
  1. 区间查询:set还支持区间查询,可以在O(log n)的时间复杂度内找到某个区间内的所有元素。例如,可以使用lower_boundupper_bound函数来查找一个区间内的所有元素。
#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;
}
  1. 最大/最小值: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;
}
  1. 排序: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在算法设计中的应用非常广泛,可以帮助我们实现去重、查找、区间查询、最大/最小值查询和排序等功能。

0
看了该问题的人还看了