• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

C++标准模板库STL算法与自适应容器(栈和队列)

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

参考《21天学通C++》第23与第24章节,对STL算法与自适应容器进行介绍。

实际上在前面的STL顺序容器、关联容器进行介绍时或多或少引用到了一些STL算法中的模板函数。而自适应容器是在顺序容器的基础上按照stack、queue的性质进行定制实现的。所以,本篇博文将言简意赅地总结出需要掌握的纲要。

查找、搜索、删除、计数、排序等都是一些通用算法,STL通过模板函数提供了这些算法,可通过迭代器对容器进行操作。需要包含<algorithm>头文件。

1. find,find_if

用于在vector等顺序容器中查找与值匹配或满足条件的元素,返回值为对应的迭代器;

2. count,count_if

用于计算在给定范围内的元素数;

3. search,search_n

用于在一个序列中查找另一个序列;

4. fill,fill_n

用于将容器中的元素初始化为指定值;

5. generate,generate_n

用于将元素设置为运行阶段生成的值;比如:generate(vecIntegers.begin(),vecIntegers.end(), rand)//用随机数填充;generate_n(vecIntegers.begin(), 5, rand) //用随机数填充开始五个数据

6. for_each

用来对指定范围的元素进行处理;采用一个指定的一元函数对象。

7. transform

用来对源范围内每个元素调用指定的函数对象;函数对象可以是一元函数,也可以是二元函数。for_each与transform非常相似。

8. copy,copy_if,copy_backward

copy沿着前向复制,copy_if仅在指定的一元谓词返回true时才返回,copy_backward沿着后向复制。

9. replace,replace_if

用于替换集合中等于指定值和满足给定条件的元素。

10. sort

用于排序;

11. partition,stable_partition

将输入范围分为两个部分:一部分满足谓词,一部分不满足谓词。stable_partition还能保证每个分区中元素的相对顺序不变,而partition则不能保证。

12. unique

用于删除重复的元素;

13. binary_search

用于有序容器中的快速查找;

14. lower_bound,upper_bound

用于将元素插入到有序集合时,其可插入到有序范围内的最前位置和最后位置。

15. remove,remove_if

从容器中移除符合条件的元素;

总结:

使用算法remove、remove_if、unique之后要使用容器的成员函数erase调整容器大小;返回值为迭代器的时候要注意检查返回值与容器end(),以确定迭代器的有效性;仅当元素相对顺序很重要时,才使用stable_partition来做。记住在调用unique之前,先使用sort对容器进行排序,保证相同值得元素彼此相邻,这样unique才能发挥作用。

二、自适应容器之栈 stack

1.stack概念和定义

栈的数据结构特性是:先入后出,后入先出,只能从栈顶插入、删除和访问。可将栈视为一叠盘子,最后叠上去的盘子首先被取下来,而不能从中间或底部取出盘子。

std::stack的定义如下:

template <class elementType, class Container=deque<Type>> class stack;

elementType为stack存储的对象类型;Container是stack使用的默认底层容器实现类。stack默认在内部使用std::deque实现,但可指定vector、list来存储数据。

2. stack实例化

stack实例化的形式可以有:

std::stack<int> stackInts;//整型stack

std::stack<Tuna> stackObjs;//存储类对象Tuna的栈

std::stack<double,vector<double>> stackDoublesInVector;//double型stack,指定内部使用vector容器实现。

3.stack成员函数

push//在栈顶插入

pop//在栈顶删除

empty//检查栈是否为空

size//返回栈中元素数

top//获得指向栈顶元素的引用

三、自适应容器之队列 queue

1.queue概念和定义

队列的数据结构特性是:先进先出,允许在开头删除,在末尾插入,类似排队系统。

queue的定义如下:

template <class elementType, class Container=deque<Type>> class queue;

elementType为queue存储的对象类型;Container是queue使用的默认底层容器实现类。queue默认在内部使用std::deque实现,但可指定vector、list来存储数据。

2. queue实例化

queue实例化的形式可以有:

std::queue<int>queueInts;//整型queue

std::queue<Tuna>queueObjs;//存储类对象Tuna的queue

std::queue<double,list<double>>queueDoublesInList;//double型queue,指定内部使用list容器实现。

3.queue成员函数

push//在队尾插入

pop//在队首删除

front//返回指向队首的元素引用

back//返回指向队尾的元素引用

empty//检查队列中是否为空

size//返回队列中元素数

四、自适应容器之优先级队列 priority_queue

1.priority_queue概念和定义

优先级队列与队列的最大区别是含有最大值(或二元谓词认为的最大值)的元素位于队首,且只能在队首执行操作。

priority_queue定义如下:

template <class elementType, class Container=vector<Type>, class Compare=less<typename Container::value_type>> class priority_queue;

elementType为priority_queue存储的对象类型;Container是priority_queue使用的默认底层容器实现类。priority_queue默认使用vector进行内部实现。第三个参数指定一个二元谓词,帮助实现优先级的,如果没有指定二元谓词,将默认使用std::less,使用运算符<比较对象。

2.priority_queue实例化

std::priority_queue<int> priority_queueInts;//整型priority_queue

std::priority_queue<Tuna> priority_queueObjs;//存储类对象Tuna的priority_queue

std::queue<double,deque<double>,greater<int>> priority_queueGreaterDoublesInDeque;//double型priority_queue,指定内部使用deque容器实现,按照小到大的顺序存储在deque中。

3.priority_queue成员函数

push//在优先级队列中插入一个元素

pop//在队首(最大元素)删除

top//返回指向队首(最大元素)的元素引用

size//返回优先级队列中元素数

empty//检查优先级是否为空


总结:

本文阐述了3个重要的自适应容器STL stack,queue,priority_queue。这些容器使用顺序容器并进行改造,以满足其具体的数据结构特性,再通过成员函数呈现出栈、队列独特的行为特征。

*******************************************************************************************************

2015-8-6


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
C#中TransactionScope的使用方法和原理发布时间:2022-07-13
下一篇:
C#如何提前结束Sleep?发布时间:2022-07-13
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap