文档章节

高效使用STL

r
 ranjiewen
发布于 2016/11/03 23:48
字数 1620
阅读 7
收藏 0
高效使用STL  参考:http://blog.jobbole.com/99115/

仅仅是个选择的问题,都是STL,可能写出来的效率相差几倍;
熟悉以下条款,高效的使用STL;

当对象很大时,建立指针的容器而不是对象的容器

1)STL基于拷贝的方式的来工作,任何需要放入STL中的元素,都会被复制;
这也好理解,STL工作的容器是在堆内开辟的一块新空间,而我们自己的变量一般存放在函数栈或另一块堆空间中;为了能够完全控制STL自己的元素,为了能在自己的地盘随心干活;这就涉及到复制;
而如果复制的对象很大,由复制带来的性能代价也不小 ;
对于大对象的操作,使用指针来代替对象能消除这方面的代价;
2)只涉及到指针拷贝操作, 没有额外类的构造函数和赋值构造函数的调用;

1)容器销毁前需要自行销毁指针所指向的对象;否则就造成了内存泄漏;
2)使用排序等算法时,需要构造基于对象的比较函数,如果使用默认的比较函数,其结果是基于指针大小的比较,而不是对象的比较;

用empty() 代替size()来检查是否为空

因为对于list,size()会遍历每一个元素来确定大小,时间复杂度 o(n),线性时间;而empty总是保证常数时间;

尽量用区间成员函数代替单元素操作

使用区间成员函数有以下好处:

1)更少的函数调用
2)更少的元素移动
3)更少的内存分配

例:将v2后半部的元素赋值给v1:

单元式操作:

使用reserver避免不必要的内存分配(for vector)

新增元素空间不够时,vector会进行如下操作:
1)分配当前空间的两倍空间;
2)将当前元素拷贝到新的空间中;
3)释放之前的空间;
4)将新值放入新空间指定位置;

如果预先知道空间的大小,预先分配了空间避免了重新分配空间和复制的代价;

注:reserve()只是修改了容量,并非大小,向vector中增加元素还是需要通过push_back加入;

使用有序的vector代替关联容器(阶段性的操作适用)

对阶段性操作的定义:

先做一系列插入、完成之后,后续操作都是查询;

在阶段性的操作下,使用vector有以下优势:

1)因为vector有序,关联容器带来的有序优势散失;
2)都是使用二分法查找的前提下,查询算法对连续的内存空间的访问要快于离散的空间;

在map的insert()和operator[]中仔细选择

插入时,insert效率高;因为operator会先探查是否存在这个元素,如果不存在就构造一个临时的,然后才涉及到赋值,多了一个临时对象的构造;

更新时,[]效率更高,insert会创造一个对象,然后覆盖一个原有对象;而[]是在原有的对象上直接赋值操作;

散列函数的默认比较函数是equal_to,因为不需要保持有序;

尽量用算法替代手写的循环

1)效率相比手写更高;

STL的代码都是C++专家写出来的,专家写出来的代码在效率上很难超越;
除非我们放弃了某些特性来满足特定的需求,可能能快过stl;比如,基于特定场合下的编程,放弃通用性,可移植性;
2)不容易出错;
3)使用高层次思维编程
相比汇编而言,C是高级语言;一条C语言语句,用汇编写需要好几条;
同样的,在STL的世界中,我们也有高层次的术语:
高层次的术语:insert/find/for_each(STL算法)
低层次的词汇:for /while(C++语法)
用高层次术语来思考编程,会更简单;

尽量用成员函数代替同名的算法

1)基于效率考虑,成员函数知道自己这个容器和其他容器有哪些特有属性,能够利用到这些特性;而通用算法不可以;

2)对于关联容器,成员函数find基于等价搜索;而通用算法find基于相等来搜索;可能导致结果不一样;

使用函数对象代替裸函数作为算法的输入参数

因为内联,在函数对象的方式中,内联有效,而作为函数指针时,一般编译器都不会内联函数指针指向的函数;即使指定了inline;

比如:

更好的方式是使用函数对象:

注:《effcient c++》中的实验结论,使用函数对象一般是裸函数的1.5倍,最多能快2倍多

选择合适的排序算法

需要排序前思考我们的必要需求,可能我们只是需要前多少个元素,这时并不需要使用sort这种线性时间的工具,性能消耗更少的parttition可能是更好的选择;
以下算法的效率从左到右依次递减:

功能说明:
partition :将集合分隔为满足和不满足某个标准两个区间;
stable_partition :partition的稳定版本;
nth_element :获取任意顺序的前N个元素;
patical_sort :获取前N个元素,这个N个元素已排序;
sort:排序整个区间;
stable_sort:sort的稳定版本;

选择合适的容器

为什么vector不提供push_front()成员方法?因为效率太差,如果有太多从前面插入的需求,就不应该使用vector,而用list;

关心查找速度,首先应该考虑散列容器(非标准STL容器,如:unordered_map,unordered_set);其次是排序的vector,然后是标准的关联容器;

本文转载自:http://www.cnblogs.com/ranjiewen/p/5901215.html

r
粉丝 1
博文 203
码字总数 28
作品 0
武汉
程序员
私信 提问
cxxJava -- 像Java一样开发C++

cxxJava -- 像Java一样开发C++ 当你同时有过java和c++两个语言的开发经历后,你会喜欢上java语言开发效率的高效但又深深的被c++语言运行效率的高效所吸引。 java类库的丰富性、通用性、易用性...

cxxjava
2016/12/12
181
0
Java程序员如何高效而优雅地入门C++

Java程序员如何高效而优雅地入门Cpp,由于工作需要,需要用C++写一些模块。关于C++ 的知识结构,虽说我有过快速学习很多新语言的经验,但对于C++ 我也算是老手,但也还需要心生敬畏,本文会从...

小欣妹妹
2018/04/23
105
1
如何学习一门新的语言二——方法与步骤

之前发表过一篇文章,也是谈如何学习一门新的语言《如何学习一门新的语言》,这篇文章主要的关注点是心态。 今天这篇文章主要的关注点是具体的方法和步骤,是我学习C++和python的一些经验,整...

晨曦之光
2012/06/06
168
0
一个典型的 C++ 程序员成长经历

1. 完整的学一遍 C++ 所有语言特性,典型书籍 "The C++ Programming Language" Part1, Part2, "C++ Primer" 感觉 C++ 像大杂烩(多编程范型),各种精妙的语法特性 (friend, virtual/RTTI, c......

晨曦之光
2012/05/16
546
0
15 款最好的 C/C++ 编译器和集成开发环境

我们有很多编程语言来进行 web 开发,比如 Java,.Net,PHP,Ruby,Perl,Python 等等。今天我们主要讨论的是两大古老而又流行的语言: C 和 C++ ,它们有着许多卓越的特性,更高效的功能和支...

oschina
2014/03/03
358K
84

没有更多内容

加载失败,请刷新页面

加载更多

Mybatis Plus删除

/** @author beth @data 2019-10-17 00:30 */ @RunWith(SpringRunner.class) @SpringBootTest public class DeleteTest { @Autowired private UserInfoMapper userInfoMapper; /** 根据id删除......

一个yuanbeth
今天
4
0
总结

一、设计模式 简单工厂:一个简单而且比较杂的工厂,可以创建任何对象给你 复杂工厂:先创建一种基础类型的工厂接口,然后各自集成实现这个接口,但是每个工厂都是这个基础类的扩展分类,spr...

BobwithB
今天
5
0
java内存模型

前言 Java作为一种面向对象的,跨平台语言,其对象、内存等一直是比较难的知识点。而且很多概念的名称看起来又那么相似,很多人会傻傻分不清楚。比如本文我们要讨论的JVM内存结构、Java内存模...

ls_cherish
今天
4
0
友元函数强制转换

友元函数强制转换 p522

天王盖地虎626
昨天
5
0
js中实现页面跳转(返回前一页、后一页)

本文转载于:专业的前端网站➸js中实现页面跳转(返回前一页、后一页) 一:JS 重载页面,本地刷新,返回上一页 复制代码代码如下: <a href="javascript:history.go(-1)">返回上一页</a> <a h...

前端老手
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部