初始化

1
2
3
4
5
set<int > seta; //默认是小于比较器less<int>的set

set<int, greater<int>> setb; //创建一个带大于比较器的set，需包含头文件functional

set<Food*,compare> foodList; //创建一个自定义排序方式的set

特点

  • set 是一个内部自动有序且不含重复元素的容器。
  • set 最主要的作用就是自动去重并按升序排序，适用于需要去重但是又不方便直接开数组的情况。
  • set 中的元素是唯一的，其内部采用“红黑树”实现。

基本使用

image.png

自定义排序

  1. 当set中存储的是对象指针时，不能使用重载operator < 的方式实现，因为重载时需要使用的参数是引用，而不是指针

    1
    2
    3
    4
    5
    6
    7
        friend bool operator < (const Food& ptr1,const Food& ptr2){
            if(ptr1.rating == ptr2.rating){
                return ptr1.foodName < ptr2.foodName;
            }
            return ptr1.rating > ptr2.rating;
        }
    // 无法对装入指针的容器起效

  2. 重载运算符**()**，利用结构体

    1
    2
    3
    4
    5
    6
    7
    8
    struct compare{
        bool operator()(Food* ptr1,Food* ptr2){
            if(ptr1->rating == ptr2->rating){
                return ptr1->foodName < ptr2->foodName;
            }
            return ptr1->rating > ptr2->rating;
        }
    };
    1
    2
    3
    4
    5
    string highestRated(string cuisine) {
        // 初始化set时，需要把比较运算符也作为参数
        set<Food*,compare> foodList = cuisineToFood[cuisine];
        return (*foodList.begin())->foodName;
    }

返回最值

1
2
3
4
5
6
7
8
9
10
set<int>s;
s.insert(1);
s.insert(3);
s.insert(5);
s.insert(2);
s.insert(0);
s.insert(4);
cout<<"s的最小值:"<<*s.begin()<<endl;//第一个数值（最小值）的函数为*s.begin();
cout<<"s的最大值为:"<<*s.rbegin()<<endl;//最后一个数值（最大值）的函数为*s.rbegin();

  • 注：*s.end()返回的是set容器的最后一个元素(应该是s的长度)，而不是s队列中的最后一个元素，就是说返回的不是最大值。

二分查找

s.lower_bound() 返回第一个大于或等于给定关键值的元素
s.upper_bound() 返回第一个大于给定关键值的元素
s.equal_range() 返回一对定位器，分别表示 第一个大于或等于给定关键值的元素 和 第一个大于给定关键值的元素，这个返回值是一个pair类型，如果这一对定位器中哪个返回失败，就会等于s.end()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <set>
using namespace std;

int main(){
    set<int> s;
    s.insert(1);
    s.insert(2);
    s.insert(5);

    cout << "lower_bound & upper_bound test:" << endl;

    cout << "第一个大于或等于3的元素: " << *s.lower_bound(3) << endl;
    cout << "第一个大于或等于2的元素: " <<*s.lower_bound(2) << endl;
    cout << "第一个大于2的元素: " <<*s.upper_bound(2) << endl;

    cout << "equal_range test:" << endl;

    cout << "第一个大于或等于2的元素: " <<  *s.equal_range(2).first << endl;
    cout << "第一个大于2的元素: " << *s.equal_range(2).second << endl;
    return 0;
}