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[2] = 1; 
mp[5] = 3;
//++ 把当前迭代器后移
//-- 前移  找到比他小的"位置" 
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

link

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。

关于遍历时使用erase函数的问题

#include<bits/stdc++.h>
#include<tr1/unordered_map>
using namespace std;
set<int> s;
//本质上是一个集合
//集合中的元素互不相同 
set<int>::iterator sit; 
int main() {
    s.insert(2);
    s.insert(5);
    s.insert(7);
//  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(2);
    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';
    }
    */
    return 0;
}

multiset

多重集合，与set唯一的区别就是支持插入多个相同的数

此时使用.count(x)函数可以获取到x的出现次数

同时.size()函数也会相应改变

非常重要的一点，关于erase函数，如果直接删除某个数，会全部删除，因此我们往往是来删除一个迭代器，这样就可以每次只删除一个

void Erase(int x) {
    auto it = s.find(x);
    s.erase(it);
}