algorithm 库里一些 STL 容器

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;
}