前言

STL的set是一个二叉排序树，也称为集合，其在STL内部实现是红黑树，能够将元素默认从小到大 排序或者是字典序 排序。如果声明的元素类型不是基本数据类型而是自定义的类要给它一个比较器，类似于sort的compare。

使用细节

  • 比较器仿函数传进来的类要加const修饰符，而这就是使得类中要调用的成员方法也要修饰const。（const对象只能访问const方法）。
  • set中的二分查找方法upper_bound、lower_bound 方法查的是第一个使得比较器返回为true的迭代器。
  • 也可以像优先队列容器那样，在类中直接重载<运算符，或者重载>运算符，在set声明的泛型中用greater。

测试代码

#include <iostream>
#include <algorithm>
#include <set>
#include <string>
using namespace std;

class MyCompare1 { //比较的仿函数
public:
	bool operator() (const int A, const int B) {
		return A > B;
	}
};

class Person {
private:
	int age;
	string name;
public:
	Person():age(0),name("NULL"){}  //string不可初始化为NULL，否则会抛异常
	Person(int age, string name):age(age),name(name){}
	
	string getName () const{
		return name;
	}
	int getAge () const{
		return age;
	}
	
	void setName (string name) {
		this->name = name;
	}
	
	void setAge (int age) {
		this->age = age;
	}
};

class MyCompare2 {
public:
	bool operator () (const Person& A, const Person& B) {
		int x = A.getAge();
		int y = B.getAge();
		return x > y;
	} //年龄从大到小
};

int main() {
	set<int,less<int> > s1; //默认使用less比较算子，除了使用 compare也可以重载 运算符，通过less或greater，参考priority_queue
	s1.insert(5);
	s1.insert(4);
	s1.insert(6);
	s1.insert(1);
	s1.insert(3);
	for (set<int>::iterator it = s1.begin(); it != s1.end(); it++) {
		cout << *it << endl;
	} //set默认升序排序
	
	if(s1.find(2) == s1.end()) {
		cout << "not elem1" <<endl;
	}//查找不到相应元素时返回end迭代器
	
	cout << "----------------------------" << endl;
	
	set<Person,MyCompare2 > s2;
	s2.insert(Person(19, "lilei"));
	s2.insert(Person());
	s2.insert(Person(22, "hanmeimie"));
	s2.insert(Person(12, "xiaogang"));
	s2.insert(Person(33, "lq"));
	for (set<Person>::iterator it = s2.begin(); it != s2.end(); it++) {
		cout << (*it).getName() << " " << (*it).getAge() << endl;
	} //set默认升序排序

	if(s2.find(Person(19,"lilei")) == s2.end()) {
		cout << "not elem2" <<endl;
	}//查找不到相应元素时返回end迭代器

	cout << "-----------------------------" << endl;
	cout << ">= : " << s2.lower_bound(Person(22,"lili"))->getName() << endl;
	cout << "> : " << s2.upper_bound(Person(22,"lili"))->getName() << endl;
	
	return 0;
}