C++STL之set容器,stlset容器

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>
#include<algorithm>
using namespace std;
int main()
{
set<int>v1;

//insert插入
v1.insert(1);
v1.insert(4);
v1.insert(5);
v1.insert(1);                              //元素1因为已经存在所以set中不会再次插入1
v1.insert(3);
v1.insert(2);

//遍历set,可以发现元素是有序的
set<int>::iterator it;
for(it=v1.begin();it!=v1.end();it++)       //集合v1{1 2 3 4 5}
  cout<<*it<<" ";
cout<<endl;

//使用size()函数可以获得当前元素个数 5
cout<<v1.size()<<endl;

if(v1.find(200)==v1.end())                 //find()函数可以查找元素是否存在
   cout<<"200 isn't in the set v1"<<endl;  //find会挨个查找set,
                                           //当到达set.end()时,就是一个也没找到,返回end()

set<int>v2;

for(int i=3;i<=10;i++)                     //集合v2{3 4 5 6 7 8 9 10}
v2.insert(i);
for(it=v2.begin();it!=v2.end();it++)
   cout<<*it<<" ";
cout<<endl;

set<int>v3;

//获得两个set的并
//v1并v2     ->   集合v3 {1 2 3 4 5 6 7 8 9 10}
set_union(v1.begin(),v1.end(),v2.begin(),v2.end(),inserter(v3,v3.begin()));

v3.clear();                                //注意进行集合操作之前接收结果的set要调用clear()函数清空

//获得两个set的交
//v1交v2     ->   集合v3 {3 4 5}
set_intersection(v1.begin(),v1.end(),v2.begin(),v2.end(),inserter(v3,v3.begin()));

v3.clear();

//获得两个set的差,也就是上集合-下集合,下集合多出来的不管
//v1差v2     ->   集合v3{1 2}
set_difference(v1.begin(),v1.end(),v2.begin(),v2.end(),inserter(v3,v3.begin()));

v3.clear();

//获得两个set的对称差,也就是假设两个集合分别为A和B那么对称差为AUB-A∩B
//v1对称差v2  ->   集合v3{1 2 6 7 8 9 10}
set_symmetric_difference(v1.begin(),v1.end(),v2.begin(),v2.end(),inserter(v3,v3.begin()));
return 0;
}

 

set是STL中风流倜傥种规范提到容器(vector,list,string,deque都是系列容器,而set,multiset,map,multimap是标准提到容器卡塔尔,它…

C++
STL可分为容器(containers)、迭代器(iterators)、空间配置器(allocator)、配接器(adapters)、算法(algorithms)、仿函数(functors)多少个部分。

通用算法:比较、交换、查找、遍历、复制、修改、移除、反转、排序、合并。

C++11 STL容器分类

==================================================

一、顺序容器:

vector:可变大小数组;

deque:双端队列;

list:双向链表;

forward_list:单向链表;

array:固定大小数组;

string:与vector雷同的器皿,但特别用于保存字符。

==================================================

二、关联容器:

最首要字有序保留成分:(底层完毕为红黑树

map:事关数组;保存关键字-值对;

set:重大字即值,即只保留关键字的器皿;

multimap:关键字可再度的map;

multiset:珍视字可另行的set;

==================================================

无序集合:

unordered_map:用哈希函数组织的map;

unordered_set:用哈希函数社团的set;

unordered_multimap:哈希集团的map;关键字能够另行出现;

unordered_multiset:哈希公司的set;关键字可以重复现身。

==================================================

三、其他项:

stack(栈)

valarray:好像vector,也是叁个模板类,其重大被用来对一文山会海成分实行高效的数字总计

bitset:二进制容器, 贮存的时 bit 位成分, 每一人只占二个 bit 位, 取值
0 或许 1, 能够像整形元素相通按位与或非, 何况大大优化了时光和空中复杂度.

常用容器简要介绍

(1) vector

里面数据结构:数组。

随机拜会每种成分,所须要的时刻为常量。

必发88官网,在最终扩张或删除成分所需时间与成分数目非亲非故,在当中或开始扩充或删除成分所需时间随成分数目呈线性别变化化。

可动态扩张或裁减成分,内部存款和储蓄器管理活动完毕,但工程师可以应用reserve()成员函数来治本内部存款和储蓄器。

vector的迭代器在内部存款和储蓄珍视新分配时将失效(它所指向的因素在该操作的前后不再相符卡塔 尔(英语:State of Qatar)。当把当先capacity()-size()个要素插入vector中时,内部存款和储蓄器会重新分配,全数的迭代器都将失效;不然,指向当前因素今后的别的因素的迭代器都将失效。当删除成分时,指向被去除成分之后的别的因素的迭代器都将失效。

(2)deque

当中数据结构:数组。

随意寻访各类成分,所必要的时间为常量。

在先导和最终增新币素所需时间与元素数目毫不相关,在个中扩张或删除成分所需时间随成分数目呈线性别变化化。

可动态扩展或裁减成分,内部存款和储蓄器管理活动完毕,不提供用于内部存款和储蓄器管理的成员函数。

追加别的因素都将使deque的迭代器失效。在deque的上游删除成分将使迭代器失效。在deque的头或尾删除成分时,唯有指向该因素的迭代器失效。

(3)list

内部数据结构:双向环状链表。

不能够自由拜望多少个成分。

可双向遍历。

在开头、末尾和西路任哪里方扩张或删除成分所需时日都为常量。

可动态扩充或收缩成分,内部存储器管理活动完毕。

扩展其余因素都不会使迭代器失效。删除元素时,除了指向当前被去除成分的迭代器外,此外迭代器都不会失灵。

(4)slist

内部数据结构:单向链表。

不足双向遍历,只好在此以前到后地遍历。

其余的特色同list相仿。

(5)stack

适配器,它能够将随机等级次序的体系容器转变为一个库房,平日接受deque作为支撑的行列容器。

要素只好后进先出(LIFO卡塔 尔(阿拉伯语:قطر‎。

不可能遍历整个stack。

(6)queue

适配器,它能够将随机等级次序的行列容器转换为叁个行列,日常选拔deque作为支撑的队列容器。

要素只可以先进先出(FIFO卡塔 尔(英语:State of Qatar)。

不可能遍历整个queue。

(7)priority_queue

适配器,它能够将随便档期的顺序的行列容器调换为一个优先级队列,平时选拔vector作为底层存款和储蓄形式。

只可以访谈第一个成分,不能够遍历整个priority_queue。

首先个要素始终是优先级最高的七个成分。

(8)set

键和值相等。

键唯一。

要素私下认可按升序排列。

风度翩翩经迭代器所针没错因素被剔除,则该迭代器失效。其余任何扩展、删除成分的操作都不会使迭代器失效。

(9)multiset

键能够不唯后生可畏。

其余特点与set雷同。

(10)hash_set

与set绝相比较,它里面包车型客车成分不必然是通过排序的,而是依照所用的hash函数分派的,它能提供越来越快的搜求速度(当然跟hash函数有关卡塔 尔(阿拉伯语:قطر‎。

任何特点与set相同。

(11)hash_multiset

键能够不唯生龙活虎。

其它特点与hash_set相同。

(12)map

键唯一。

要素暗中认可开关的升序排列。

如若迭代器所针没有错成分被去除,则该迭代器失效。此外任何扩展、删除成分的操作都不会使迭代器失效。

(13)multimap

键能够不唯大器晚成。

此外特点与map雷同。

(14)hash_map

与map相相比较,它里面包车型地铁要素不自然是按钮值排序的,而是根据所用的hash函数分派的,它能提供更加快的查找速度(当然也跟hash函数有关卡塔 尔(阿拉伯语:قطر‎。

别的特点与map相像。

(15)hash_multimap

键能够不唯风流倜傥。

任何特点与hash_map相同。

容器相比较

必发88官网 1

各容器特点相比以致选取

必发88官网 2

小结

在骨子里运用进程中,应该依靠遵循以下准绳:

1、借使须要急迅的随机存取,无所谓插入和删除的成效,使用vector;

2、若是急需大批量的插入和删除成分,不爱戴随机存取的频率,使用list;

3、假如急需随机存取,何况关怀两端数据的插入和删除成效,使用deque;

4、借使筹算存款和储蓄数据字典,况兼供给方便地根据key找到value,大器晚成对意气风发的景况使用map,黄金时代对多的情景使用multimap;

5、假如筹划寻觅三个成分是还是不是留存于某集合中,唯一设有的意况使用set,不唯后生可畏设有的情状接收multiset。

相关文章