set & multiset 配合自定义结构体使用进行自动集合排序。s 下有迭代器。
//测试样例
9 3
3 4
3 3
struct Node {
int x;
int y;
};
struct cmp{
bool operator()(const Node &a, const Node &b) {
return a.x<b.x||a.x==b.x&&a.y<b.y;
}
};
int main() {
int num;
cin>>num;
++num;
int x,y;
multiset<Node,cmp> s;
while (--num!=0) {
cin>>x>>y;
s.insert({x,y});
}
typeof(s.begin()) c=s.find({3,3});
//上述c的类型是 multiset<Node,cmp>::iterator
cout<<c->x<<' '<<c->y<<endl;
c++;
while (!s.empty()) {
c=s.begin();
cout<<c->x<<' '<<c->y<<endl;
s.erase(c);
}
return 0;
}
STL 容器迭代器 iterator,访问顺序容器和关联容器中的元素。
定义变量 iterator。定义类型包括 iterator、const_iterator、reverse_iterator(rbegin(), rend())、const_reverse_iterator。对反向迭代器进行 ++ 操作时,迭代器会指向容器中的前一个元素。
- s.begin()
使用 s.find() 函数时,正向迭代器会迭代遍历到 s.end()。
容器 | 迭代器功能 |
vector | 随机访问 |
deque(双端队列) | 随机访问 |
list | 双向 |
set/multiset | 双向 |
map/multimap | 双向 |
stack | 不支持迭代器 |
queue | 不支持迭代器 |
priority_queue | 不支持迭代器 |
deque 使用 push_front()、push_back() 在队列头部、尾部增加元素。deque 包括 insert()、erase() 的函数调用。
//另一个小实例 实现自定义结构体排序 指定要求删除指定数据
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
const int N=1e6+5;
struct Node {
int v;
int c;
};
struct cmp {
bool operator()(const Node &a, const Node &b) {
return a.c>b.c||(a.c==b.c&&a.v>=b.v);
}
};
int n;
multiset<Node,cmp> h;
int main() {
scanf("%d",&n);
for (int i=1; i<=n; i++) {
int v,c;
cin>>v>>c;
h.insert({v,c});
}
multiset<Node,cmp>::iterator i=h.begin();
int fv=i++->v;
while (i!=h.end()) {
cout<<"!!"<<i->v<<" "<<i->c<<endl;
if (i!=h.end()) {
cout<<"MOVED TO "<<i->v<<" "<<i->c<<endl;
if ((i->v)>=fv) {
cout<<"TRIED ERASE "<<i->v<<" "<<i->c<<endl;
h.erase(i++);
}
else i++;
}
}
for (multiset<Node,cmp>::iterator i = h.begin(); i!=h.end(); i++) {
cout<<i->v<<" "<<i->c<<endl;
}
return 0;
}
Comments NOTHING