by attack666
set与map
map
内部实现是一棵红黑树
- 定义
key和value分别对应着两种类型
map<key, value> mp;
- 内部函数
直观的理解就是一种加强的数组。
begin()--返回指向第一个元素的迭代器
end()--返回指向最后一个元素的迭代器
find()--返回一个指向被查找到元素的迭代器
size()--集合中元素的数目
clear()--清除所有元素
count()--返回某个值元素的个数
empty()--如果集合为空,返回true
lower_bound()--返回指向大于(或等于)某值的第一个元素的迭代器
upper_bound()--返回大于某个值元素的迭代器
- 迭代器
map<int, int>::iterator mit; //mit = mp.begin(); mp[] = ; mp[] = ; //++ 把当前迭代器后移 //-- 前移 找到比他小的"位置" for(mit = mp.begin(); mit != mp.end(); mit++) { //mit->second = 233; cout << mit->first << ' ' << mit->second << '\n'; } for(auto &x: mp) {//& //x.second = 233; //考虑如果在这儿套一个二分的复杂度 cout << x.first << ' ' << x.second << '\n'; } for(auto x = mp.begin(); x != mp.end(); x++) { cout << x->first << ' ' << x->second << '\n'; }
- unordered_map
#include<tr1/unordered_map>
- cc_hash_table
MingW/4.8.1/include/c++/ext/pb_ds
set
begin();//返回的是第一个元素的迭代器
end();
insert(x);//pair<set<int>::iterator, bool>> second = 0说明已经有该元素/否则成功插入
size();
find(x);//若能找到返回迭代器,否则返回end()
count(x);//出现次数,因为set的性质,所以只有0/1
lower_bound(x);//>=x的iterator
upper_bound(x);//>x的iterator
erase(x);//删除x。
#include<bits/stdc++.h> #include<tr1/unordered_map> using namespace std; set<int> s; //本质上是一个集合 //集合中的元素互不相同 set<int>::iterator sit; int main() { s.insert(); s.insert(); s.insert(); // cout << s.insert(3).second << '\n'; // cout << s.size() << '\n'; // cout << *s.lower_bound(5) << '\n'; // cout << *s.upper_bound(5) << '\n'; // cout << *s.lower_bound(10) << '\n'; s.erase(); cout << *s.begin() << '\n'; cout << *s.end() << '\n'; /* for(auto &x: s) { cout << x << '\n'; } for(sit = s.begin(); sit != s.end(); sit++) { cout << *sit << '\n'; } */ ; }
multiset
多重集合,与set唯一的区别就是支持插入多个相同的数
此时使用.count(x)
函数可以获取到x
的出现次数
同时.size()
函数也会相应改变
非常重要的一点,关于erase函数,如果直接删除某个数,会全部删除,因此我们往往是来删除一个迭代器,这样就可以每次只删除一个
void Erase(int x) { auto it = s.find(x); s.erase(it); }
by刘学长