基础:
set 是关联容器, set 中每个元素的值都是唯一的, 系统能够根据元素的值自动进行排序. set 中数元素的值并不能直接被改变. STL 中还有一些标准关联容器 multiset,map 和 multimap 等, 这些关联容器内部均是采用红黑树实现的.
set 特点:
1,map 和 set 的插入删除效率比其他序列容器高.
原因: set 中所有元素都是以节点的方式来存储的, 其节点结构和链表类似, 指向父节点和子节点. 所以, 在插入和删除时不需要做内存拷贝和内存移动, 故而提高了效率.
2, 每次 insert 之后, 以前保存的 iterator 不会失效.
原因: 迭代器 iterator 在 set 中就相当于指向节点的指针, 只要内存不变, 那这个 iterator 就不会失效. 相对于 vector 来说, 每一次的删除和插入之后, 指针都有可能失效, 调用 push_back 在尾部插入的时候情况也是如此. 因为为了保证内部数据的连续存放, iterator 指向的那块内存在插入和删除的过程中可能已经被其他内存覆盖或者内存已经被释放掉了. 即使是 push_back 的时候, 容器内部空间可能不够, 需要一块新的更大的内存, 只能把以前的内存释放掉, 申请更大的内存, 复制已有的数据元素都新的内存中, 最后把需要插入的元素放到最后, 那么以前的内存指针自然就不可用了. 特别是在和 find,erase 等操作一起使用的时候, 一定要注意: 不要使用失效的 iterator.
3,
使用方法:
例题:
ACM-ICPC 2018 徐州赛区网络预赛 G Trace https://nanti.jisuanke.com/t/31459
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- struct point{
- int x,y;
- bool operator <(const point & _point)const{
- return x < _point.x;
- }
- }tot[50005];
- set<point> M;
- int n,a,b;
- int main()
- {
- scanf("%d",&n);
- for(int i=1;i<=n;i++)
- {
- scanf("%d%d",&tot[i].x,&tot[i].y);
- }
- M.clear();
- ll ans = 0;
- ans += tot[n].x;ans += tot[n].y;
- M.insert(tot[n]);
- for(int i=n-1;i>=1;i--)
- {
- if(M.lower_bound(tot[i])==M.end()){
- set<point>::iterator it = M.end();
- it--;
- point temp = *(it);
- ans += tot[i].y;
- ans += tot[i].x - temp.x;
- }
- else if(M.lower_bound(tot[i])==M.begin()){
- point temp = *M.begin();
- ans += tot[i].x;
- ans += tot[i].y - temp.y;
- }
- else{
- set<point>::iterator it = (M.lower_bound(tot[i]));
- point temp1 = *it;
- it--;
- point temp = *it;
- ans += tot[i].y - temp1.y;
- ans += tot[i].x - temp.x;
- }
- M.insert(tot[i]);
- }
- cout<<ans<<endl;
- }
来源: http://www.bubuko.com/infodetail-2768561.html