C++ set and map

set

set是什么？集合！

创建和插入

set中的元素有两个特性

set中的元素是互异的。
set中的元素会自动排好序
来看代码

#include<iostream>
#include<set> 

using namespace std;

int main(){
    set <int> s;  
    s.insert(1);
    s.insert(3);
    s.insert(2);
	s.insert(1);
	
    for(auto p = s.begin(); p != s.end(); p++){
        cout << *p << ' ';
    }
	return 0;
}

第二行，使用set前，要先导入set库，即#include<set>

set创建和vector类似，通过set <type> set_name方式进行创建，如代码的第七行。
有一点不同是，set_name后是不带length和val参数的。
即
set <int> s(10);
这种方式不能通过编译。

也很好理解，集合这个东西，应该是要随时加元素和删元素的，为什么要分配空间呢。

但是如果想创建同时初始化集合，使用
set <int> s = {1, 2, 3};
这种方式是阔以的。

想在集合中插入元素，只需要通过
s.insert(val);
就可以~

在上面的代码中，我们先后试图插入了1, 3, 2, 1四个元素，随后通过迭代器输出集合s中的元素。
这段代码运行的结果是
1 2 3
没戳，正如这一节一开始说的那样，集合是有互异性的，并且set中的元素是会被自动排序(默认升序)的。

那怎么让它降序呢？只需在创建set时这么写~
set <int, greater<int>> s
s就会定义成一个默认降序的集合了~

集合大小

使用s.size()就可以~

元素查找

如何查找集合中的元素呢，只需使用
s.find(val)
若集合s中存在val这个元素，会返回val这个元素的==位置==
但如果不存在，会返回s.end()这个位置！而不是NULL

如

1
2
3

    set <int> s = {1, 2, 3};
    cout << (s.find(2) == s.end()) << endl;
    cout << (s.find(4) == s.end()) << endl;

输出的结果是

1
2

0
1

元素删除

只需要通过
s.erase(val)就可以把集合中val这个元素删掉了~
如果s中没有val这个元素，这行运行之后将无事发生。

map

map是什么？键值对！也就是python里的字典——
什么是键值对？也就是一个值映射一个值，其实也就是哈希表

创建和插入

我们来看代码

#include<iostream>
#include<map>

using namespace std;

int main(){
    map <string, int> m;
    m["hello"] = 114514;
    m["world"] = 666666;
    
    cout << "hello : " << m["hello"] << endl;
    cout << "world : " << m["world"] << endl;
    return 0;

}

使用map前，要先导入map库
创建map时，只需使用
map <key, val> m就可以创建一个map了，这里的key和val都不限制类型。
这里的key就是“键”，val就是“值”。

如何添加一个键值对？
只需要使用类似上面代码8，9行的代码。使用m[key] = val进行赋值操作
若map中不存在那个键是key的键值对，就会创建<key, val>这个键值对
如果已经存在一个键就是key的键值对<key, val>了，那么赋值操作就会更改那个val值

访问

如何访问键值对？只需要使用
m[key]就会返回<key, val>键值对中val的值了
上面那段代码的输出是

1 2	hello : 114514 world : 666666

那如果不存在这个键值对呢，程序会自动插入一个键值对<key, val>,并且把val是默认初始化的值（如int初始化成0）
比如这段代码

#include<iostream>
#include<map>

using namespace std;
int main(){
    map <string, int> m;
    m["hello"] = 114514;
    m["world"] = 666666;
    
    cout << "hello : " << m["hello"] << endl;
    cout << "world : " << m["world"] << endl;
    cout << "nihao : " << m["nihao"] << endl;
    return 0;

}

的输出将是

1
2
3

hello : 114514
world : 666666
nihao : 0

查找

有时，我们只是想查找或者访问已经存在的键值对，而不想在访问键值对的同时就把不存在的键值对也加进去。对此，我们只要调用
m.find(key);就可以~
比如

1
2
3

if(m.find("hello") != m.end()){
	cout << "hello : "<< m["hello"]; 
}

再次提醒。STL里的find()函数，若查找失败，返回的都是end()，而不是空指针！

迭代器

在使用map的迭代器时，需要注意要通过

1
2
3

 for(auto p = m.begin(); p != m.end(); p++){
        cout << p -> first << ':' << p -> second << ' ' << ' ';
    }

这种方式。用p -> first来访问“键”，用p -> second来访问“值”。
直接访问*p会编译错误

这里的用法和指针类似，很好理解~

unordered_set and unordered_map

其实就是不会在插入时自动排序的set和map
使用方法完全和set和map相同

由于不会自动排序，所以节约了时间~如果使用set和map时TLE，可以考虑使用这两个unordered_set 和unordered_map。

不过无序，并不代表使用迭代器输出时，输出顺序就是插入顺序——绝大概率是乱序的！

一些底层逻辑

set和map的实现用的是红黑树(一种特殊的二叉查找树)，保证了插入并排序、查找，和删除的时间复杂度都是O(logn)，很快~

推荐一个B站上讲解红黑树的可视化视频

而unordered_set和unordered_map是用哈希表和链表实现的，所以更快，也能解释为什么输出顺序是乱序的~