set和muliset
set就是数学上的集合——每个元素最多只能出现一次。
【关于set】
set是关联式容器。set作为一个容器也是用来存储同一数据类型的数据类型,并且能从一个数据集合中取出数据,在set中每个元素的值都唯一,而且系统能根据元素的值自动进行排序。应该注意的是set中数元素的值不能直接被改变。C++ STL中标准关联容器set, multiset, map, multimap内部采用的就是一种非常高效的平衡检索二叉树:红黑树,也称为RB树(Red-Black Tree)。RB树的统计性能要好于一般平衡二叉树,所以被STL选择作为了关联容器的内部结构。
【关联型容器概述】
在学习序列式容器时,我们知道,容器中元素的顺序都是由程序决定的,程序可以随意指定新元素的插入位置,而对于关联型容器,它的所有元素都是经过排序的,关联型容器都是有序的。它的每一个元素都有一个键(key),容器中的元素是按照键的取值升序排列的。
关联型容器内部实现为一个二叉树,在二叉树中,每个元素都有一个父节点和两个子节点。左子树的所有元素都比自己小,右子树的所有元素都比自己大。
A
/ \
B C
/ \ / \
D E F G
关联型容器内部结构都是以这种一叉树结构实现, 这也使得它可以高效地查找容器中的每一个元素,但却不能实现任意位置的操作。
标准库提供了四种关联型容器: set(集合)、multiset(多重集合)、map(映射)、multimap(多重映射),其中set与multiset 包含在头文件set中,map与multimap包含在头文件map中。
set与muliset的区别在于是否允许有重复元素,其他用法都很相似,因此将这两种容器放在一起进行讲解, 接下来我们就分 别讲解集合对象的创建及其常用的操作方法。
【set、muliset中常用的方法】
1、创建对象。
set与muliset中都重载了不同的构造函数,因此可以以不同的方式定义集合,set 集合的定义方式如下所示:
set<T> s; //创建一个空的set集合,默认升序排列
set<T, op> s; //创建一个空的set集合,按op规则排序
set<T> s(begin, end) ; //创建一个集合,用[begin, end]区间为其 初始化
set<T,op> s (begin, end) ; //创建集合,用[begin, end]区间为其初始化并按op规则排序
set<T> s(s1) ; //创建一个空的set集合,用另一个集合s1初始化
set集合提供了五种重载构造函数,接下来我们分别用这五种方式定义不同的集合,代码
如下所示:
set<char> s1;
set<int, greater<int>()> s2;
set<float> s3(begin, end) ;
set<string,greater<string>()> s4 (begin, end) ;
set<int> s5(s2) ;
注:
geater<T>从大到小
less<T> 从小到大
上述代码分别用不同的方式定义了char、int等类型的集合,其中集合s2与s4中greater<T>则是排序规则,意指从大到小的顺序排列,如果没有排序规则,则默认规则是less<T>,意为从小到大排序,这是STL中定义的函数对象( functor),包含在头文件functional中
与set集合一样,multiet也重载了这五种构造函数,接下来用这五种方式分别定史不同的multiset集合对象,代码如下所示:
multiset <char> ms1 ;
multiset <int, greater<int> ()> ms2;
multiset <float>ms3 (begin, end) ;
multiset <string, greater<string>()> ms4 (begin, end) ;
multiset <int> ms5(s2) ;
上述代码分别用五种不同的方式定义了五个multiset 集合对象,其定义中的参数与set集合一样,这里就不再赘述。
2、集合的大小,元素的查找和统计。
s.size(); //返回容器中元素的数目
s.max_size(); //返回容器中可容纳的最大元素数量
s.empty(); //判断容器是否为空
上述函数 调用中的s指集合容器,如无特殊说明,则s既可以是set容器也可以是multiset容器,即两个容器都提供了这样的函数。
s.find(); //查找函数
s.count(); //统计个数的函数
find( )函数的功能是返回key元素的位置,返回值是迭代器类型。count( )函数的功能是返回元素elem的个数,对于set集合来说,要么是0要么是1,而对于multiset来说,值可能大于1。
3、获取头尾部元素。
s.begin(); //返回容器中收元素的位置
s.end(); //返回容器中最后一个元素字后的迭代器
4、插入和删除元素。
s.insert(elem); //在容器中插入元素elem
s.insert(pos, elem); //在pos位置插入元素elem
s.insert(begin, end); //在容器中插入[begin,end]区间的值
对于set容器来说,第一种形式的insert( )调用的返回值是pair<iterator, bool>对象,其第一个参数iterator 是迭代器,指示元素插入的位置;第二个参数bool类型的值代表元素是否插入成功。
这是因为set容器中不允许存在重复的元素,如果要插入一个容器中已存在的元素,则插入操作会失败,而pair中的bool值就是标识插入是否成功,而multiset不存在这样的情况,因此multiset返回的是-个 iterator。
set与multiset提供的erase( )函数也有几种实现形式,其函数调用形式如下所示:
s.erase (pos) ; //删除pos位置上的元素
s.erase (begin, end) ; //删除[begin, end) 区间上的元素
s.erase (elem) ; / /删除元素elem
调用erase()函数可以删除某一个位置 上的元素,可以删除指定的元素,也可以删除指定范围的元素。
5、其他
equal_range() 返回一对定位器,分别表示第一个大于或等于给定关键值的元素和 第一个大于给定关键值的元素,这个返回值是一个pair类型,如果这一对定位器中哪个返回失败,就会等于end()的值。具体这个有什么用途我还没遇到过~~~
find() ,返回给定值值得定位器,如果没找到则返回end()。
lower_bound(key_value) ,返回第一个大于等于key_value的定位器
upper_bound(key_value),返回最后一个大于等于key_value的定位器
【示例代码】
#include <iostream>
#include <set>
#include <functional>
using namespace std;
int main()
{
set<int, greater<int>> s; //创建一个set容器,元素按降序排列
multiset<char> ms; //创建一个multiset容器
cout << "s能容纳的最大元素数量" << s.max_size() << endl;
cout << "ms能容纳的最大元素数量" << ms.max_size() << endl;
//向s中插入元素
pair<set<int>::iterator, bool> ps;
ps = s.insert();
if (ps.second == true)
cout << "insert success" << endl;
s.insert();
s.insert();
s.insert();
//向ms中插入元素
ms.insert('a');
ms.insert('z');
ms.insert('T');
ms.insert('u');
ms.insert('u');
//输出两个容器中的元素
set<int>::iterator its; //创建s容器的迭代器,用于获取元素
cout << "s容器中元素:";
for (its = s.begin(); its != s.end(); its++)
cout << *its << " ";
cout << endl;
multiset<char>::iterator itms; //创建ms容器的迭代器
cout << "ms容器中元素:";
for (itms = ms.begin(); itms != ms.end(); itms++)
cout << *itms << " ";
cout << endl; //查找两个容器中头尾元素
cout << "s头元素: " << *s.begin() << endl;
cout << "ms尾元素: " << *(--ms.end()) << endl;
//查找ms容器中u元素出现的次数
cout << "ms容器中u元素出现的次数:" << ms.count('u') << endl;
system("pause");
return ;
}
运行结果如下
样例中创建了一个set容器s和一个multiset容器ms,其中容器s中的元素是按降序排列,代码9~ 10行调用max_ size( )函数分别算出两个容器的最大容量,代码12~24行分别调用insert( )函数向两个容器中插入元素,其中ms容器中插入了重复的元素u,代码26~35行分别创建相应的迭代器输出容器中的元素,由图8-14可知,s中的元素按降序排列,ms中的元素按升序排列。代码37~ 38行分别调用begin()与end( )函数输出s的头元素和ms的尾元素,由运行结果可知,两个元素输出成功。代码41行调用count( )函数输出ms容器中u元素的个数,由运行结果可知,ms容器中u元素有两个。
最后我们用一到题来体会set的用处。
【问题描述】输入一个文本,找出所有不同的单词(连续的字母序列),按字典序从小到大输出。单词不区分大小写。
【样例输入】
Adventures in Disneyland
Two blondes were going to Disneyland when they came to a fork in the
road. The sign read: "Disneyland Left."
So they went home.
【样例输出】
a
adventures
blondes
came
disneyland
fork
going
home
in
left
read
road
sign
so
the
they
to
two
went
were
when
【代码如下】
#include<iostream>
#include<string>
#include<set>
#include<sstream>//stringstream要包含的头文件
using namespace std;
set<string> dict;//string 集合 int main()
{ string s, buf;
while (cin >> s)
{
for (int i = ; i < s.length(); i++)
if (isalpha(s[i]))//是否是字母
s[i] = tolower(s[i]);//变成小写
else
s[i] = ' ';
stringstream ss(s);
//stringstream是字符串流。
//它将流与存储在内存中的string对象绑定起来。
//在多种数据类型之间实现自动格式化。
while (ss >> buf)
dict.insert(buf);//插入元素
}
for (set<string>::iterator it = dict.begin(); it != dict.end(); ++it)//循环输出
cout << *it << "\n"; system("pause");
return ;
}
最新文章
- 利用gulp解决前后端分离的header/footer引入问题
- python socket
- WinForm 窗体应用程序(初步)之一
- Android Studio 快捷键 for mac
- c# 多语言实现 与 InitializeCulture
- 014. asp.net实现记住密码的功能
- 收集一下Windows7系统啊
- 教程-DelphiXE7如何调用Java Class,JAR等文件?
- Cordova+angularjs+ionic+vs2015开发(二)
- Spread 之自定义对角线cellType源码: DiagonalCellType
- python日志记录-logging模块
- 用showModalDialog写的简单弹出框传参与反参
- Hibernate三大类查询总结
- 对lua表中数据按一定格式处理,循环
- vimgrep 搜索总结
- javaFX的控制台实现
- Keras运行速度越来越慢的问题
- Django的settings配置
- Python select IO多路复用
- prometheus的agent 二次开发代码参考