分类：
set集合容器：实现了红黑树的平衡二叉检索树的数据结构，插入元素时，它会自动调整二叉树的排列，把元素放到适当的位置，以保证每个子树根节点键值大于左子树所有节点的键值，小于右子树所有节点的键值；另外，还得保证根节点左子树的高度与右子树高度相等。
平衡二叉检索树使用中序遍历算法，检索效率高于vector、deque和list等容器，另外使用中序遍历可将键值按照从小到大遍历出来。
构造set集合主要目的是为了快速检索，不可直接去修改键值。
常用操作：
1.元素插入：insert()
2.中序遍历：类似vector遍历（用迭代器）
3.反向遍历：利用反向迭代器reverse_iterator。
例：
set<int> s;
……
set<int>::reverse_iterator rit;
for(rit=s.rbegin();rit!=s.rend();rit++)
4.元素删除：与插入一样，可以高效的删除，并自动调整使红黑树平衡。
set<int> s;
s.erase(2); //删除键值为2的元素
s.clear();
5.元素检索：find()，若找到，返回该键值迭代器的位置，否则，返回最后一个元素后面一个位置。
set<int> s;
set<int>::iterator it;
it=s.find(5); //查找键值为5的元素
if(it!=s.end()) //找到
cout<<*it<<endl;
else //未找到
cout<<“未找到”;
6.自定义比较函数
(1)元素不是结构体：
例：
//自定义比较函数myComp,重载“（）”操作符
struct myComp
{
bool operator()(const your_type &a,const your_type &b)
[
return a.data-b.data>0;
}
}
set<int,myComp>s;
……
set<int,myComp>::iterator it;
(2)如果元素是结构体，可以直接将比较函数写在结构体内。
例：
struct Info
{
string name;
float score;
//重载“<”操作符，自定义排序规则
bool operator < (const Info &a) const
{
//按score从大到小排列
return a.score<score;
}
}
set<Info> s;
……
set<Info>::iterator it;
转）STL中set用法详解
|
set是STL中一种标准关联容器（vector,list,string,deque都是序列容器，而set，multiset，map，multimap是标准关联容器），它底层使用平衡的搜索树——红黑树实现，插入删除操作时仅仅需要指针操作节点即可完成，不涉及到内存移动和拷贝，所以效率比较高。set，顾名思义是“集合”的意思，在set中元素都是唯一的，而且默认情况下会对元素自动进行升序排列，支持集合的交(set_intersection),差(set_difference) 并(set_union)，对称差(set_symmetric_difference) 等一些集合上的操作，如果需要集合中的元素允许重复那么可以使用multiset #include<set> #include<iterator> #include<iostream> using namespace std; int main() { set<int>eg1; //插入 eg1.insert(1); eg1.insert(100); eg1.insert(5); eg1.insert(1);//元素1因为已经存在所以set中不会再次插入1 eg1.insert(10); eg1.insert(9); //遍历set，可以发现元素是有序的 set<int>::iterator set_iter=eg1.begin(); cout<<“Set named eg1:”<<endl; for(;set_iter!=eg1.end();set_iter++) cout<<*set_iter<<” “; cout<<endl; //使用size()函数可以获得当前元素个数 cout<<“Now there are “<<eg1.size()<<” elements in the set eg1″<<endl; if(eg1.find(200)==eg1.end())//find()函数可以查找元素是否存在 cout<<“200 isn’t in the set eg1″<<endl; set<int>eg2; for(int i=6;i<15;i++) eg2.insert(i); cout<<“Set named eg2:”<<endl; for(set_iter=eg2.begin();set_iter!=eg2.end();set_iter++) cout<<*set_iter<<” “; cout<<endl; //获得两个set的并 set<int>eg3; cout<<“Union:”; set_union(eg1.begin(),eg1.end(),eg2.begin(),eg2.end(),insert_iterator<set<int> >(eg3,eg3.begin()));//注意第五个参数的形式 copy(eg3.begin(),eg3.end(),ostream_iterator<int>(cout,” “)); cout<<endl; //获得两个set的交，注意进行集合操作之前接收结果的set要调用clear()函数清空一下 eg3.clear(); set_intersection(eg1.begin(),eg1.end(),eg2.begin(),eg2.end(),insert_iterator<set<int> >(eg3,eg3.begin())); cout<<“Intersection:”; copy(eg3.begin(),eg3.end(),ostream_iterator<int>(cout,” “)); cout<<endl; //获得两个set的差 eg3.clear(); set_difference(eg1.begin(),eg1.end(),eg2.begin(),eg2.end(),insert_iterator<set<int> >(eg3,eg3.begin())); cout<<“Difference:”; copy(eg3.begin(),eg3.end(),ostream_iterator<int>(cout,” “)); cout<<endl; //获得两个set的对称差，也就是假设两个集合分别为A和B那么对称差为AUB-A∩B eg3.clear(); set_symmetric_difference(eg1.begin(),eg1.end(),eg2.begin(),eg2.end(),insert_iterator<set<int> >(eg3,eg3.begin())); copy(eg3.begin(),eg3.end(),ostream_iterator<int>(cout,” “)); cout<<endl;
|