c++ stack用法详解

set

set就是集合，STL的set用二叉树实现，集合中的每个元素只出现一次(参照数学中集合的互斥性)，并且是排好序的(默认按键值升序排列)

访问元素的时间复杂度是$O({\log }_{2}n)$

在c++中，set的头文件是#include<set>

set具有迭代器set<int>::iterator i 定义一个迭代器,名为i 可以把迭代器理解为C语言的指针

set常用操作

set<int> q;     //以int型为例 默认按键值升序
set<int,greater<int>> p;  //降序排列 
int x;
q.insert(x);	//将x插入q中
q.erase(x);		//删除q中的x元素,返回0或1,0表示set中不存在x
q.clear();		//清空q
q.empty();		//判断q是否为空，若是返回1，否则返回0
q.size();		//返回q中元素的个数
q.find(x);		//在q中查找x，返回x的迭代器，若x不存在，则返回指向q尾部的迭代器即 q.end()
q.lower_bound(x); //返回一个迭代器，指向第一个键值不小于x的元素
q.upper_bound(x); //返回一个迭代器，指向第一个键值大于x的元素

q.rend();		  //返回第一个元素的的前一个元素迭代器
q.begin();		  //返回指向q中第一个元素的迭代器

q.end();		 //返回指向q最后一个元素下一个位置的迭代器
q.rbegin();		 //返回最后一个元素

set单元素应用

#include<iostream>
#include<set>
using namespace std;
int main()
{
	set<int> q;   //默认按升序排列 
	q.insert(5);
	q.insert(5);
	q.insert(5);
	cout<<"q.size "<<q.size()<<endl;   //输出 1 ,在set插入中相同元素只会存在一个
	
	q.clear(); //清空set
	cout<<"q.size "<<q.size()<<"\n\n";
	
	q.insert(4);
	q.insert(4);
	q.insert(3);
	q.insert(3); 
	q.insert(2);
	q.insert(1);
	
	cout<<"lower_bound "<<*q.lower_bound(3)<<endl;  //返回3 
	cout<<"upper_bound "<<*q.upper_bound(3)<<"\n\n";  //返回4 
	
	set<int>::iterator i;
	for( i=q.begin();i!=q.end();i++)   //set的遍历 
		cout<<*i<<" ";				   //输出1 2 3 4，可见自动按键值排序 
	cout<<endl;
	
	q.erase(4);  //删除q中的 4 
	
	for(i=q.begin();i!=q.end();i++)  //再次遍历set 只输出 1 2 3 
		cout<<*i<<" ";
	cout<<"\n\n"; 
	
	
	set<int,greater<int>> p;  //降序排列 
	p.insert(1);
	p.insert(2);
	p.insert(3);
	p.insert(4);
	p.insert(5);
	for(i=p.begin();i!=p.end();i++)
		cout<<*i<<" ";
	cout<<endl;
	
	return 0;
}

set多元素应用(结构体)

#include<iostream>
#include<set>
using namespace std;
struct node{
	int a,b;
	bool operator< (const node W)const
	{
		return a>W.a;  //按a的值升序 
	}
}t;
int main()
{
	set<node> q;
	t.a=1;
	t.b=2;
	q.insert(t);
	
	t.a=4;
	t.b=2;
	q.insert(t);
	
	t.a=3;
	t.b=5;
	q.insert(t);	
	
	set<node>::iterator i;
	for(i=q.begin();i!=q.end();i++)
	{
		t=*i;
		cout<<t.a<<" "<<t.b<<endl;
	}
	return 0; 
}

例题

题目：HDU - 2094 产生冠军

代码：

#include<iostream>
#include<set>
using namespace std;
int main()
{
	int n;
	string a,b;
	while(cin>>n && n)
	{
		set<string> A,B;
		for(int i=0;i<n;i++)
		{
			cin>>a>>b;
			A.insert(a);
			A.insert(b);
			B.insert(b);
		}
		
		if(A.size()-B.size()==1)
			cout<<"Yes\n";
		else
			cout<<"No\n";
	}
	return 0;
}

---

c++ stack用法详解