2018-07-19-备战CCC-集合Set的使用

前言

佛了，上次写题目因为多加了一个=爆了个段错误找了一下午，
以后提示一个写动态数组如果出现什么段错误的情况把程序里面所有for的=都给我安排了就好了【如果一定要<=的话把循环次数-1看看是不是就可以运行了】

今天来继续自闭，啊呸，继续学习STL中的Set集合【暗示了STL开挂】，
这不就是Dict嘛我读书少你别骗我【事实上Py的基本语法很多好像都和STL的结构一样，发明STL的人一定是一个天才！】

0x01 Why 集合

集合的墙外百科：传送门

集合是数学中的一个基本概念，通俗地理解，集合是由一些不重复的数据组成的。比如 {1,2,3}就是一个有 1,2,3三个元素的集合。

C++ 和 Java 的标准库中的集合支持高效的插入、删除和查询操作，这 3 个操作的时间复杂度都是裸根O(lg n），其中 n是当前集合中元素的个数。如果用数组，虽然插入的时间复杂度是 O(1)，但是删除和查询都是 O(n)，时间效率太低。
【档然啦做开发的时候用户从来就不缺那么一秒两秒——time.sleep(random)】

万幸的是，STL已经给你写好了Set，所以你不需要再使用奇奇怪怪的命令去自己构造一个集合【再写指针就真的写成自闭了】

0x02 make 个 Set

套路安排上了，头文件加上就完事了奥

#include<set>

因为奇怪的std空间属性，记得加上using namespace std，不然等会儿调用的时候::写到你哭，
C++ 中直接构造一个set的语句为：set<T> s。这样我们定义了一个名为s的、储存T类型数据的集合，其中T是集合要储存的数据类型。初始的时候s是空集合。

0x03 insert插入

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"}
    return 0;
}

对应的Python代码？顺便验证了一下去重性：

>>> x=set('abcd')
>>> x
{'b', 'a', 'd', 'c'}
>>> x.insert('f')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'set' object has no attribute 'insert'
>>> x.add('f')
>>> x
{'b', 'd', 'f', 'c', 'a'}
>>> x.add('f')
>>> x
{'b', 'd', 'f', 'c', 'a'}

话说我看到insert就会强迫症的想到Python中的插入方法，于是跑到C++官网上去科普了一下，
等等，这里就犯了一个经典错误：set是一个无序的数据结构
既然无序就不存在说下标的问题，这也是为什么set和map的插入效率比其他所有的数据结构都快。

0x03 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;
}

这个在vector里面已经介绍过了，官网上对于easer是这么介绍的：
erase(iterator) ,删除定位器iterator指向的值
erase(first,second),删除定位器first和second之间的值
erase(key_value),删除键值key_value的值
等等，不是说好的嘛不能有下标？？
注意这里的叫定位器，这里我们又要引出上次被我淡化的定位器概念了：
begin()——返回容器的第一个元素
end()——返回容器的最后一个元素
注意：在使用定位器之前最好先检查函数是否为空
栗子：

#include <iostream>
#include <set>

using namespace std;

int main()
{
    set<int> s;
    set<int>::const_iterator iter;
    set<int>::iterator first;
    set<int>::iterator second;
    for(int i = 1 ; i <= 10 ; ++i)
    {
        s.insert(i);
    }
    //第一种删除
    s.erase(s.begin());
    //第二种删除
    first = s.begin();
    second = s.begin();
    second++;
    second++;
    s.erase(first,second);
    //第三种删除
    s.erase(8);
    cout<<"删除后 set 中元素是 ：";
    for(iter = s.begin() ; iter != s.end() ; ++iter)
    {
        cout<<*iter<<" ";
    }

0x04 count & find 查找

count用来查找set中某个某个键值出现的次数。这个函数在set并不是很实用，因为一个键值在set只可能出现0或1次，这样就变成了判断某一键值是否在set出现过了【bool变量还行】

#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")) {
        printf("China belong to country");
    }
    return 0;
}

find() ，返回给定值值得定位器，如果没找到则返回end()。
又提到迭代器了，一会儿会讲，先记住怎么写就完事咯，毕竟set里面只有这一种迭代方式，

#include <iostream>
#include <set>

using namespace std;

int main()
{
    int a[] = {1,2,3};
    set<int> s(a,a+3);
    set<int>::iterator iter;
    if((iter = s.find(2)) != s.end())
    {
        cout<<*iter<<endl;
    }
    return 0;
}

0x05 iterator 迭代器

这是一个很奇怪的东西，使用自闭的指示器和指针进行迭代【指针里就摇了我吧】
下面就是一个非常典型的迭代器：

#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;
}

看到没有？begin和end安排上了，但是set有一个特别🐮🍺的功能——C++的集合遍历出来是从小到大进行的，也就是说......
他给帮你排序啦，这也太棒了⑧

0x06 clear 清空

和vector一样，set也是只需要使用clear便可以清空所有元素唔【迭代器是指针怎么释放单个？？】

0x07 其他骚操作

max_size()	返回set容器可能包含的元素最大个数
size()	返回当前set容器中的元素个数
rbegin	返回的值和end()相同
rend()	返回的值和rbegin()相同
lower_bound(key_value)	返回第一个大于等于key_value的定位器
upper_bound(key_value)	返回最后一个大于等于key_value的定位器

栗子lower&upper：

#include <iostream>
#include <set>

using namespace std;

int main()
{
    set<int> s;
    s.insert(1);
    s.insert(3);
    s.insert(4);
    cout<<*s.lower_bound(2)<<endl;
    cout<<*s.lower_bound(3)<<endl;
    cout<<*s.upper_bound(3)<<endl;
    return 0;
}

输出:
3
3
4

后记

参考资料：
集合-计蒜客
STL中的set容器的一点总结
std::set::find

拖就完事咯~
【明年二月怕不是要被打】
OIer:写轮子Coder的过来挨打！

最后的最后

破站一个暑假没人来啦，我哭了，你们呢？
谷歌统计不看了，伤心