文档章节

STL学习记录(八)Sets、Multisets

YourFirst
 YourFirst
发布于 2015/10/06 17:06
字数 1673
阅读 12
收藏 0

STL关联容器Set、Multiset

Set、Multiset简介

Set和Multiset会依据一定的排序准则自动的将容器里面的元素进行排序。这也就表明关联容器与顺序容器的一个最大不同就是元素的顺序与元素插入容器的先后无关。set、multiset的不同在于前者不允许容器内部有相同的元素,而后者则是允许的。因为容器对元素进行自动排序,这就表明set、multiset中的元素类型必须是可以进行比较的,或者说其中的元素有自己的比较准则。使用这两个容器的时候都要包含头文件< set >
容器的类模板定义如下:

namespace std {
    template <typename T,
            typename Compare = less<T>,
            typename Allocator = allocator<T> >
            class set;
    template <typename T,
            typename Compare = less<T>,
            typename Allocator = allocator<T> >
            class multiset;
}

改模板中的第二个参数定义了元素的排序策略,默认情况下采用 < ,第三个参数定义了内存模型,默认情况下为c++标准库的allocator模型
Set和Multiset的实现就像数据中的二叉平衡树,并且该二叉树还是排序树。从这个数据结构中我们就可以了解到它们最大的一个优势:在搜索特定值的元素时会比一般的线性搜索时间会短很多,尤其是在数据量非常大的时候更为明显。但是自动排序功能也给Set和Multiset造成了一个很大的限制:不能去更改容器里元素的值。因为元素的位置是在元素进入容器时根据元素的值确定的,你改变了元素的值将使得该元素在一个不正确的位置上。因此你要改变某个元素的值,可以采用:先删除该元素,然后插入新元素(从这个角度来看的话,可以“认为”容器的元素都是const类型的)。

容器的内部结构图
内部结构说明图
常用类:

操作 说明
c.size( ) 返回c里面元素的个数
c.empty( ) 判断c是否为空
c.max_size( ) 返回c的最大的容量
c.key_comp( ) 返回比较策略
c.value_comp( ) 返回元素值得比较策略(与上面操作相同)
c1.swap(c2) 交换c1、c2中的数据
swap(c1,c2) 交换c1c2中的数据


迭代器类:

操作 说明
c.begin( ) 返回c的第一个元素的双向迭代器
c.end( ) 返回c的最后一个元素之后位置的双向迭代器
c.cbegin( ) 返回c的第一个元素的const型双向迭代器
c.cend( ) 返回c的最后一个元素之后位置的const型双向迭代器
c.rbegin( ) 返回c逆序的第的第一个元素的反向迭代器
c.rend( ) 返回c逆序的最后一个元素的反向迭代器
c.crbegin( ) 返回c逆序的第一个元素的const型反向迭代器
c.crend( ) 返回c逆序的最后一个元素的const型反向迭代器


插入、移除元素:

操作 说明
c.clear( ) 删除c中的所有元素
c.erase(val) 删除元素值为val的所有元素,并返回删除的个数
c.erase(pos) 删除位于pos的元素,并返回下一个元素的位置
c.erase(beg,end) 删除位于[beg,end)之间的元素,并返回下一个元素的位置
c.emplace(args… 将用参数args…初始化的元素插入到c中并返回该元素的位置c++11
c.emplace_hint(pos,args…) 将参数args…初始化的元素插入到c中并返回该元素的位置(pos指明了从哪里开始搜索该位置)
c.insert(pos,vaL) pos之前插入vaL的拷贝并返回该元素的位置(pos指明了从哪里开始搜索该位置)
c,insert(vaL) 插入vaL的一个拷贝,并返回新插入元素的位置
c.insert(beg,end) 将[beg,end)之间的元素插入到c中不返回任何东西)
c.insert({*x1,x2,}* 将列表{*x1,x2,}*中所有元素的拷贝插入到cz中(不返回任何东西)


需要注意的是插入函数insert()和emplace( )的返回类型的差别:

//set中的接口:
pair<iterator,booL> insert(const value_type& val);
iterator            insert(const_iterator posHint, const value_type& val);

template<typename... Args>
pair<iterator,booL>  empalce(Args&&... args);
template<typename... Args>
iterator             emplace_hint(const_iterator posHint,Args&&... args);

//multiset中的接口:
iterator            insert(const value_type& val);
iterator            insert(const_iterator posHint, const value_type& val);

template<typename... Args>
iterator             empalce(Args&&... args);
template<typename... Args>
iterator             emplace_hint(const_iterator posHint,Args&&... args);

这里返回类型的差别是因为multiset允许有重复值而set不允许。因此set插入一个元素的时候可能会失败,所以set返回的类型使用了pair结构。pair结构中第一个参数返回的是新插入元素的位置或者已有元素的位置,第二个参数返回的是是否插入成功(标明了第一个参数是新插入元素的位置还是已有元素的位置)

一些特殊的搜索操作:

操作 说明
c.count(val) 返回元素值为val的元素个数
c.find(val) 返回第一个元素值为val的元素的位置
c.lower_bound(val) 返回第一个val插入c中时的可能位置,也就是第一个>=val元素的位置
c.upper_bound(val) 返回最后一个val插入c中时的可能位置,也就是第一个>val元素的位置
c.equal_range(val) 返回所有元素值为val的元素的位置范围


代码示例1:

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

int main( )
{
    set<int> c;
    c.insert(1);
    c.insert(2);
    c.insert(4);
    c.insert(5);
    c.insert(6);

    cout<<"lower_bound(3): "<<*c.lower_bound(3) <<endl;
    cout<<"upper_bound(3): "<<*c.upper_bound(3) <<endl;
    cout<<"equal_bound(3): "<<*c.equal_bound(3).first<<" "<<*c.equal_bound(3).second<<endl;

    cout<<endl;
    cout<<"lower_bound(5): "<<*c.lower_bound(5) <<endl;
    cout<<"upper_bound(5): "<<*c.upper_bound(5) <<endl;
    cout<<"equal_bound(5): "<<*c.equal_bound(5).first<<" "<<*c.equal_bound(5).second<<endl;

}

程序输出(multiset结果一样):
lower_bound(3): 4
lower_bound(3): 4
lower_bound(3): 4 4

lower_bound(5): 5
lower_bound(5): 6
lower_bound(5): 5 6

代码示例2:

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

int main()
{
    set<int,greater<int> > coll;//采用大于准则排序而不是默认的小于准则

    coll.insert({5,6,2,3,1});
    coll.insert(5);

    for(int elem : coll) {
        cout<<elem<<" ";
    }
    cout<<endl;

    auto status_3 = coll.insert(3);
    if(status_3.second) 
        cout<<"3 insert as new element"<<endl;
    else
        cout<<"3 already exists"<<endl;
    cout<<"3 at: "<<distance(coll.begin(),status_3.first)+1<<endl;//返回该元素的位置

    auto status_4 = coll.insert(4);
    if(status_4.second) 
        cout<<"4 insert as new element"<<endl;
    else
        cout<<"4 already exists"<<endl;
    cout<<"4 at: "<<distance(coll.begin(),status_4.first)+1<<endl;

    status_3 = coll.insert(3);
    cout<<"after insert 4, 3 at "<<distance(coll.begin(),status_3.first)+1<<endl;
    return 0;
}

程序输出为:
6 5 3 2 1
3 already exists
3 at 3
4 insert as new element
4 at 3
after insert 4, 3 at 4

版权声明:本文为博主原创文章,未经博主允许不得转载。

© 著作权归作者所有

共有 人打赏支持
YourFirst
粉丝 1
博文 16
码字总数 17792
作品 0
合肥
程序员
私信 提问
学习C++的50条,谨以送给C++的粉丝们

1.把C++当成一门新的语言学习(和C没啥关系!真的);   2.看《Thinking In C++》,不要看《C++变成死相》(C++编程思想,翻译的非常差);   3.看《The C++ Programming Language》(这...

地瓜儿
2013/01/11
1K
7
C语言编程学习:制作掷骰子小游戏

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界
2018/05/20
0
0
牛逼的C/C++程序员是如何练成的?

这个题目的噱头太大,要真的写起来, 足够写一本书了。 牛耳人分享一些经验,希望能让初学的小伙伴少走弯路。 每个人的情况不一样,所以下面的描述可能并不适合每一个看到这篇文章的人。 一、...

weixin_42743471
2018/12/07
0
0
想学好C++当程序员大神,先把C语言基础打好

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界
2018/05/19
0
0
1+1=2的 blog 文章索引

百度空间中 原blog部分文章 索引:http://hi.baidu.com/cyclone/home Qt Bugs 通过 Qt Bugs 学习 Qt 似乎是一个不错的方法。 QString之arg使用一则 QTBUG-19027 QMainWindow上下文菜单内存泄...

晨曦之光
2012/05/08
309
0

没有更多内容

加载失败,请刷新页面

加载更多

聊聊ShenandoahGC的Brooks Pointers

序 本文主要研究一下ShenandoahGC的Brooks Pointers Shenandoah Shenandoah面向low-pause-time的垃圾收集器,它的GC cycle主要有 Snapshot-at-the-beginning concurrent mark包括Init Mark(P......

go4it
昨天
1
0
Makefile通用编写规则

#简单实用的Makefile模板: objs := a.o b.o test:$(objs) gcc -o test $^ # .a.o.d .b.o.d dep_files := $(foreach f,$(objs),.$(f).d) dep_files := $(wildcard $(dep_files)) ifneq ($(d......

shzwork
昨天
1
0
《万历十五年》的读后感作文4000字

《万历十五年》的读后感作文4000字: 万历十五年,即1587年,距今已过去432年。在明朝276的历史中,这一年很平淡,并没有什么特别之处。黄仁宇的《万历十五年》一书,有别于其他的历史叙述方...

原创小博客
昨天
0
0
vue组件系列4、Table封装下

知道了slot 怎么用,才可以理解table这样封装的原因 table插件部分 <template> <div> <!-- 关键字部分 --> <div class="pre_search" v-show="show_key"> <label>关键字:......

轻轻的往前走
昨天
0
0
laravel嵌套预加载限制字段

之前有写过laravel关联查询的坑,后经一位博友提醒可以简写,详见https://my.oschina.net/u/3470006/blog/3020215 自己实践了下果然如此,要查询user表和与之关联的信息表userinfo直接可以用...

gcudwork
昨天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部