STL之Set

集合(Set)

集合

集合是由一些不重复的数据组成的。比如{1,2,3}就是一个有1,2,3三个元素的集合,集合有三个特性:

1.确定性

给定一个集合,任给一个元素,该元素或者属于或者不属于该集合,二者必居其一,不允许有模棱两可的情况出现

2.互异性

一个集合中,任何两个元素都认为是不相同的,即每个元素只能出现一次。有时需要对同一元素出现多次的情形进行刻画,可以使用多重集,其中的元素允许出现多次 。

3.无序性

一个集合中,每个元素的地位都是相同的,元素之间是无序的。集合上可以定义序关系,定义了序关系后,元素之间就可以按照序关系排序。但就集合本身的特性而言,元素之间没有必然的序 。

在C++中我们常用的集合是set

引用set

C++中set的实现在一个<set> 的头文件中,在代码开头引入这个头文件,并加上using namespace std

#include <set>
using namespace std;

构造一个集合

构造 set 集合语句为:set <T> s。这样我们就定义了一个名为s的、存储T类型数据的集合,T是集合储存的数据类型。初始的时候s空集合。

插入元素

C++中用insert()函数向集合中插入一个新的元素。 注意如果插入的元素集合中已经存在了,则插入无效,因为集合有“确定性”

#include <set>
#include <string>
using namespace std;
int main() {
    set<string> country;  // {}
    country.insert("China"); // {"China"}
    country.insert("America"); // {"China", "America"}
    country.insert("France"); // {"China", "America", "France"}
    country.insert("China"); // {"China", "America", "France"}
    return 0;
}

删除元素

C++中用erase函数在集合中删除一个已经存在的元素。 注意如果想要删除的元素在集合中不存在,则删除无效

#include <set>
#include <string>
using namespace std;
int main() {
    set<string> country;  // {}
    country.insert("China"); // {"China"}
    country.insert("America"); // {"China", "America"}
    country.insert("France"); // {"China", "America", "France"}
    country.erase("America"); // {"China", "France"}
    country.erase("England"); // {"China", "France"}
    return 0;
}

判断元素是否存在

C++中如果你想知道某个元素是否在集合中出现,你可以直接用count() 函数。如果集合中存在我们要查找的元素则返回 1 ,否则会返回 0。

#include <set>
#include <string>
#include <stdio.h>
using namespace std;
int main() {
    set<string> country;  // {}
    country.insert("China"); // {"China"}
    country.insert("America"); // {"China", "America"}
    country.insert("France"); // {"China", "America", "France"}
    if (country.count("China")) {
        cout << "China belong to country" << endl;
    }
    return 0;
}

遍历元素

C++通过迭代器可以访问j集合中的每个元素,迭代器就好像手指指向set 中的某个元素。通过操作这个手指,我们可以改变它指向的元素,通过* (解引用运算符,不是乘号的意思) 操作可以获取迭代器指向的元素。通过++操作让迭代器指向下一个元素,同样-- 操作让迭代器指向上一个元素。

迭代器的写法比较固定,std <T>::iterator it就定义了一个指向 set<T>这种集合的迭代器it ,T是任意的数据类型。其中::iterator 是固定的写法。

begin函数返回容器中起始元素的迭代器,end 函数返回容器的尾后迭代器。

如果你不了解迭代器,你只需先记住用法。

#include <set>
#include <string>
#include <iostream>
using namespace std;
int main() {
    set<string> country;  // {}
    country.insert("China"); // {"China"}
    country.insert("America"); // {"China", "America"}
    country.insert("France"); // {"China", "America", "France"}
    for (set<string>::iterator it = country.begin(); it != country.end(); it++) {
        cout << *it << endl;
    }
    return 0;
}

注意,在C++中遍历set 是从小到大的,也就是说set 会帮我们排序的。

清空

C++中调用clear()函数就可以清空set,同时会清空set的内存 。

set小结

set中插入、删除、查找某个元素的时间复杂度都是O(logn),并且内部元素有序。

函数 功能 时间复杂度
insert 插入一个元素 O(logn)
erase 删除一个元素 O(logn)
count 统计集合中某个元素的个数 O(logn)
size 获取元素个数 O(1)
clear 清空 O(n)

set和结构体

set经常会和结构体来使用,用set 来储存结构体和vector 有些区别。 因为set 在存储数据时会按照默认的数据类型比较规则进行自动排序,而我们自己定义的结构体,set 不知道此类型的比较方式,因此我们要用一种方式来告诉系统怎么比较这个结构体的大小,其中一种方法为运算符重载,我们需要重新定义小于符号。

下面的代码定义了一个重载了小符号的结构体:

struct Node {
    int x, y;
    bool operator<(const Node &rhs) const {
        if (x == rhs.x) {
            return y < rhs.y;
        } else {
            return x < rhs.x;
        }
    }
};

operator< 表示我们要重载运算符< ,可以看成是一个函数名。rhs 是“right hand side”的简称,有有操作数的意思,这里我们定义为一个const引用。因为该运算符重载在结构体内部,左操作数就当前调用operator <的对象。

特别注意,不要漏掉最后的constconst函数表示不能对其数据成员进行修改操作,并且const对象不能调用非const成员函数,只允许调用const成员函数。

上面的重载规定了排序方式为,优先按照x从小到大排序,如果x相同那么y再按照从小到大排序。经过了<的运算符的重载的结构体,我们就可以比较Node对象的大小了,因此就可以保存在set 了。

上一篇:支付宝-API接口解析-转账到银行


下一篇:Solution - [CEOI2018]Cloud computing