C++STL容器之set容器
STL新手入门点击:STL新手入门向1.set介绍set是C++标准库中的一种关联容器。所谓关联容器就是通过键(key)来读取和修改元素。与map关联容器不同,它只是单纯键的集合。set集合容器实现了红黑树(Red-Black Tree)的平衡二叉检索树的数据结构,在插入元素时,它会自动调整二叉树的排列,把该元素放到适当的位置,以确保每个树根节点的键值大于左子树所有节点的键值,而小于右...
STL新手入门点击:STL新手入门向
1.set介绍
set是C++标准库中的一种关联容器。所谓关联容器就是通过键(key)来读取和修改元素。与map关联容器不同,它只是单纯键的集合。
set集合容器实现了红黑树(Red-Black Tree)的平衡二叉检索树的数据结构,在插入元素时,它会自动调整二叉树的排列,把该元素放到适当的位置,以确保每个树根节点的键值大于左子树所有节点的键值,而小于右子树所有节点的键值;另外,还确保根节点左子树的高度与右子树的高度相等,这样,二叉树的高度最小,从而检索速度最快。要注意的是,它不会重复插入相同键值的元素,而采取忽略处理。
2.set的使用
set模版类的定义在头文件<set
>中
set的基本操作:
s.begin() // 返回指向第一个元素的迭代器
s.clear() // 清除所有元素
s.count() // 返回某个值元素的个数
s.empty() // 如果集合为空,返回true(真)
s.end() // 返回指向最后一个元素之后的迭代器,不是最后一个元素
s.equal_range() // 返回集合中与给定值相等的上下限的两个迭代器
s.erase() // 删除集合中的元素
s.find() // 返回一个指向被查找到元素的迭代器
s.get_allocator() // 返回集合的分配器
s.insert() // 在集合中插入元素
s.lower_bound() // 返回指向大于(或等于)某值的第一个元素的迭代器
s.key_comp() // 返回一个用于元素间值比较的函数
s.max_size() // 返回集合能容纳的元素的最大限值
s.rbegin() // 返回指向集合中最后一个元素的反向迭代器
s.rend() // 返回指向集合中第一个元素的反向迭代器
s.size() // 集合中元素的数目
s.swap() // 交换两个集合变量
s.upper_bound() // 返回大于某个值元素的迭代器
s.value_comp() // 返回一个用于比较元素间的值的函数
2.1创建set集合对象
#include<iostream>
#include<set>
using namespace std;
set<int>s
2.2元素的插入
s.insert(1);
s.insert(2);
s.insert(3);
2.3元素的遍历
#include<iostream>
#include<set>
using namespace std;
set<int>s;
int main()
{
s.insert(1);
s.insert(2);
s.insert(3);
set<int>::iterator it;
for(it=s.begin();it!=s.end();it++)
{
cout<<*it<<" ";
}
cout<<endl;
}
2.4元素的查找
#include<set>
using namespace std;
set<int>s;
int main()
{
s.insert(1);
s.insert(2);
s.insert(3);
if(s.find(3)!=s.end())
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
if(s.count(3))
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
find()查找元素返回给定值的迭代器,如果没找到则返回 end()。
count() 用来查找 set 中某个某个键值出现的次数。这个函数在 set 并不是很实用,
因为一个键值在 set 只可能出现 0 或 1 次,这样就变成了判断某一键值是否在 set 出现过了
2.5删除元素,容器中元素的个数,清空容器,判空
#include<iostream>
#include<set>
using namespace std;
set<int>s;
int main()
{
s.insert(1);
s.insert(2);
s.insert(3);
s.erase(3);//删除元素
cout<<s.size()<<endl;//容器中元素的个数
s.clear();//清空容器
if(s.empty())//判空,集合为空,返回true(真)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
2.6排序
法1
//非结构元素
#include<iostream>
#include<set>
using namespace std;
set<int,greater<int> >s;//注意空格
//set<int,less<int> >s;用不到set默认从小到大排序
int main()
{
s.insert(1);
s.insert(3);
s.insert(5);
s.insert(2);
s.insert(4);
set<int>::iterator it=s.begin();
while(it!=s.end())
{
cout<<*it<<" ";
it++;
}
cout<<endl;
}
法2
//非结构体元素
#include <set>
#include <iostream>
using namespace std;
struct myComp
{
bool operator()(const int &a,const int &b)
{
return a>b;//降序
//return a<b;//升序
}
};
int main(int argc, char* argv[])
{
set<int,myComp> s;
s.insert(8);
s.insert(1);
s.insert(12);
s.insert(6);
s.insert(8);
set<int,myComp>::iterator it;
for(it=s.begin();it!=s.end();it++)
{
cout<<*it<<" ";
}
cout<<endl;
return 0;
}
法3
//结构体元素
/*set的insert方法没有insert(a,cmp)这种重载,所以如果要把结构体插入set中,我们就要重载'<'运算符。
set方法在插入的时候也是从小到大的,那么我们重载一下<运算符让它从大到小排序*/
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
struct node
{
int a;
char b;
//重载"<"操作符,自定义排序规则 (为什么要重载<号呢?看stl_function.h源码)
bool operator < (const node &x) const
{
if(x.a==a)
return b<x.b;//当a值相等按b值从小到大排序
return a>x.a;//当a值不等时按a值从大到小排序
}
};
set<node>s;
int main()
{
set<node>::iterator it;
node w={1,'d'};
node x={1,'c'};
node y={3,'a'};
node z={2,'b'};
s.insert(w);
s.insert(x);
s.insert(y);
s.insert(z);
for(it=s.begin();it!=s.end();it++)
{
cout<<(*it).a<<" "<<(*it).b<<endl;
}
}
multiset
在<set
>头文件中,还定义了另一个非常实用的模版类multiset(多重集合)。多重集合与集合的区别在于集合中不能存在相同元素,而多重集合中可以存在。
定义multiset对象的示例代码如下:
multiset<int> s;
multiset<double> ss;
更多推荐
所有评论(0)