大数据培训新三板挂牌机构 股票代码:837906 | EN CN
Java是什么?
Java历史
Java语言特点
C++ VS Java比较
Java工厂设计模式
Java抽象工厂模式
Java单例模式
Java建造者(Builder)模式
Java原型模式
Java适配器模式
Java桥接模式
Java获取网络文件大小
Java套接字到单一的客户端
Java连接套接字
Java URL部分
Java URL连接日期
Java下载网页
Java主机指定IP地址
Java确定本地IP地址
Java检查端口占用
Java查找代理服务器设置
Java创建Socket
Java线程实例
Java检查线程活着
Java如何检查一个线程停止或没有?
Java解决死锁实例
Java如何获取正在运行的线程的优先级?
Java如何监视线程的状态?
Java获取线程名称
Java线程生产者消费者问题
Java如何设置线程的优先级?
Java如何停止线程一会儿?
Java如何暂停线程?
Java获取线程ID
Java如何检查线程的优先级?
Java显示所有正在运行的线程?
Java显示线程状态
Java中断一个线程
Java Applet实例
Java创建Applet
Java使用Applet创建横幅
Java使用Applet显示时钟?
Java在一个Applet创建不同形状
Java如何使用Applet填充形状的颜色?
Java使用Applet跳转到一个链接
Java在Applet创建事件监听器
Java使用Applet显示图像
Java使用Applet在新窗口中打开链接
Java使用Applet播放声音?
Java使用Applet读取文件
Java使用Applet写入文件
Java中Swing应用程序applet
Java简单的图形用户界面-GUI
Java以不同的字体显示文本
Java使用GUI画一条线
Java创建框架-frame
Java使用GUI显示多边形
Java在矩形中显示文本
Java GUI显示不同形状
Java如何绘制GUI实心矩形?
Java创建GUI透明光标
Java检查GUI平滑处理状态
Java在框架中显示颜色
Java GUI显示饼图
Java使用图形用户界面绘制文本
Java编辑表-table
Java 使用prepared语句
Java使用保存点和回滚
Java同时执行数据库多个SQL命令
Java使用行方法
Java使用列方法
Java正则表达式实例
Java将字符串分割
Java搜索重复单词
Java查找出现的单词
Java最后一个词的索引
Java模式匹配
Java删除空格
Java匹配电话号码
Java计数组词
Java搜索词组
Java拆分正则表达式
Java替换第一个出现字符串
Java检查日期格式
Java验证电子邮件地址格式
Java替换所有匹配字符串
Java使每个单词的第一个字母大写
从XML创建SqlSessionFactory实例
不使用XML来创建SqlSessionFactory
从SqlSessionFactory获取SqlSession
映射SQL语句
作用域和生命周期
Mapper XML配置
properties元素
Settings元素
typeAliases 元素
typeHandlers元素
理解CacheLine与写出更好的JAVA
Java核心技术点之动态代理
更好的使用JAVA线程池
理解Java中字符流与字节流的区别
深入分析Java方法反射的实现原理
关于Java面试,你应该准备这些知识点
Java内存模型
2017年你不能错过的Java类库
Leakcanary Square的一款Android/Java内存泄漏检测工具
Java Synchronised机制
Java核心技术点之注解
JVM(8):JVM知识点总览-高级Java工程师面试必备
JVM(3):Java GC算法 垃圾收集器
JVM(1):Java 类的加载机制
解决ActiveMQ中,Java与C++交互中文乱码问题
关于Java Collections的几个常见问题
Java I/O 总结
JVM源码分析之Java对象的创建过程
JVM源码分析之Java类的加载过程
Java GC的那些事(下)
Java GC的那些事(上)
java对象头的HotSpot实现分析
面试的角度诠释Java工程师(一)
面试的角度诠释Java工程师(二)
框架开发之Java注解的妙用
谈谈Java反射机制
Java并发:volatile内存可见性和指令重排
死磕Java并发:Java内存模型之happens-before
死磕Java并发:深入分析volatile的实现原理
死磕Java并发:深入分析synchronized的实现原理
Java 10 可能对 Lambda 表达式进行升级
G1垃圾回收器中的字符串去重(Java 8 Update 20)
Java RESTful框架的性能比较
理解RxJava的线程模型
继续了解Java的纤程库 – Quasar
Java中的纤程库 – Quasar
Java豆瓣电影爬虫——抓取电影详情和电影短评数据
Java集合框架源码剖析:LinkedHashSet 和 LinkedHashMap
Java Lambda表达式初探
Java中的陷阱题
Java 9的这一基本功能,你可能从未听过
关于Java并发编程的总结和思考
几种简单的负载均衡算法及其Java代码实现
JAVA虚拟机关闭钩子(Shutdown Hook)
Java 脚本化编程指南
Java Scripting API 使用示例
Java 8 的 Nashorn 脚本引擎教程
如何开始使用 Java 机器学习
CognitiveJ —— Java 的图像分析库
Java 性能优化的五大技巧
Java 解惑:Comparable 和 Comparator 的区别
Google Java编程风格指南
java NIO详解
Java 异常处理的误区和经验总结
Java语法糖(4):内部类
Java语法糖(3):泛型
Java语法糖(2):自动装箱和自动拆箱
Java消息队列任务的平滑关闭
Java语法糖(1):可变长度参数以及foreach循环原理
2016最流行的Java EE服务器
自己写一个java.lang.reflect.Proxy代理的实现
java 如何在pdf中生成表格
如何防止单例模式被JAVA反射攻击
java虚拟机 jvm 局部变量表实战
聊聊并发-Java中的Copy-On-Write容器
java.lang.Instrument 代理Agent使用
Java开发者需要了解的移动开发编程语言
13个不容错过的Java项目
2016年7款最佳 Java 框架推荐
Java 开发者值得关注的 11 个技术博客
Redmonk发布Java框架流行度调研结果
Java 8开发的4大顶级技巧
GitHub漫游指南:10个值得你关注的Java项目
除了Guava,Java开发者还值得了解的5个谷歌类库
Java中创建对象的5种不同方法
Java性能优化全攻略
奇怪的Java题:为什么1000 == 1000返回为False,而100 == 100会返回为True?
11个最值得Java开发者收藏的网站
Java的常见误区与细节
对Java意义重大的7个性能指标
Java调优经验谈
关于Java并发编程的总结和思考
HDFS Federation设计动机与基本原理
《Effective STL》学习笔记(第三部分)
《Effective STL》学习笔记(第二部分)
《Effective STL》学习笔记(第一部分)
数据结构之位图
Thrift使用指南
Cassandra概要介绍
Cassandra部署与安装
Cassandra客户端
Cassandra数据模型
Cassandra中的各种策略
数据结构之树状数组
数据结构之伸展树
数据结构之后缀数组
数据结构之堆
浅析MRv1与MRv2的API兼容性
Apache Tez最新进展
运行在YARN上的计算框架
从传统操作系统角度理解Hadoop YARN

《Effective STL》学习笔记(第一部分)

于2017-03-26由小牛君创建

分享到:



本书从STL应用出发,介绍了在项目中应该怎样正确高效的使用STL。本书共有7个小节50个条款,分别为

(1) 容器:占12个条款,主要介绍了所有容器的共同指导法则

(2) vector和string:占6个条款,介绍了最常用的两种容器的一些使用经验

(3) 关联容器:占7个条款,介绍了关联容器(*map,*set)的使用经验

(4) 迭代器:占12个条款,介绍了迭代器的一些使用技巧

(5) 算法:占8个条款,介绍STL算法的正确使用方法和提高效率的技巧

(6) 仿函数、仿函数类、函数等:占5个条款,介绍仿函数的使用经验

(7) 使用STL编程:占8个条款,介绍怎样在程序中使用由容器、迭代器、算法和函数对象组成的STL

在这些条款中,有的是一些编程经验,即告诉你,如果想避免错误,应该这样编写程序,应该使用这个函数而不是另一个,还有一些是告诉你怎样选择最高效的函数以提高你程序的效率,总结如下:

{1} 介绍编程经验:

条款1:仔细选择你的容器

条款2:小心对“容器无关代码”的幻想

条款6:警惕C++最令人恼怒的解析

条款7:当使用new得指针的容器时,记得在销毁容器前delete那些指针

条款8:永不建立auto_ptr的容器

条款9:在删除选项中仔细选择

条款12:对STL容器线程安全性的期待现实一些

条款13:尽量使用vector和string来代替动态分配的数组

条款16: 如何将vector和string的数据传给遗留的API

条款17:使用“交换技巧”来修整过剩容量

条款18:避免使用vector<bool>

条款19:了解相等和等价的区别

条款20:为指针的关联容器指定比较类型

条款21: 永远让比较函数对“相等的值”返回false

条款22:避免原地修改set和multiset的键

条款26:尽量用iterator代替const_iterator,reverse_iterator和const_reverse_iterator

条款27:用distance和advance把const_iterator转化成iterator

条款28:了解如何通过reverse_iterator的base得到iterator

条款30:确保目标区间足够大

……

{2}提高程序效率:

条款3:使容器里对象的拷贝操作轻量而正确

条款4:用empty来代替检查size()是否为0

条款5:尽量使用区间成员函数代替它们的单元素兄弟

条款14:使用reserve来避免不必要的重新分配

条款15:小心string实现的多样性

条款23:考虑用有序vector代替关联容器

条款24:当关乎效率时应该在map::operator[]和map-insert之间仔细选择

条款25:熟悉非标准散列容器

条款29:需要一个一个字符输入时考虑使用istreambuf_iterator

条款31:了解你的排序选择

条款44:尽量用成员函数代替同名的算法

条款46:考虑使用函数对象代替函数作算法的参数

关于《Effective STL》学习笔记分为四部分,本文是第一部分(对应书中“容器”一节),第二、三、四部分分别为:《Effective STL》学习笔记(第二部分)(对应书中“vector和string”,“关联容器”两小节)Effective STL》学习笔记(第三部分)对应书中“迭代器”和“算法”两小节)《Effective STL》学习笔记(第四部分)(对应书中“仿函数、仿函数类、函数等”和“使用STL”两小节)

1、 容器

本章关注的是可以适用于所有STL容器的指导方针。后面的章节则专注于特殊的容器类型。

条款1:仔细选择你的容器

C++提供了很多可供程序员使用的容器:

(1) 标准STL序列容器:vector,string,deque和list

(2) 标准STL关联容器:set,multiset,map和multimap

(3) 非标准序列容器slist(单链表)和rope(重型字符串)

(4) 非标准关联容器hash_set,hash_multiset,hash_map和hash_multimap

(5) vector<char>可以作为string的替代品

(6) vector作为标准关联容器的替代品

(7) 几种标准非STL容器,包括数组、bitset、valarray、stack、queue和priority_queue

不同容器有不同的优缺点,用户需要根据实际应用的特点综合决定使用哪种容器,如:vector是一种可以默认使用的序列类型,当很频繁地对序列中部进行插入和删除时应该用list,当大部分插入和删除发生在序列的头或尾时可以选择deque这种数据结构。

条款2:小心对“容器无关代码”的幻想

本条款要告诫程序员:编写与容器无关的代码是没有必要的。

有人想编写这样的程序,刚开始时使用vector存储,之后由于需求的变化,将vector改为deque或者list,其他代码不变。实际上,这基本上是做不到的。这是因为:不同的序列容器所对应了不同的迭代器、指针和引用的失效规则,此外,不同的容器支持的操作也不相同,如:vector支持reserve()和capacity(),而deque和list不支持;即使是相同的操作,复杂度也不一样(如:insert),这会让你的系统产生意想不到的瓶颈。

此外,鼓励程序员在声明容器和迭代器的时候使用typedef进行重命名,这能够对你的程序进行封转,从而使用起来更简单,如有下面一个map容器:

map<string,vectorWidget>::iterator,CIStringCompare>;

如要用const_iterator遍历这个map,你需不止一次地写下:

map<string, vectorWidget>::iterator, CIStringCompare>::const_iterator

如果使用typedef,会快速方便很多。

条款3:使容器里对象的拷贝操作轻量而正确

容器容纳了对象,但不是你给它们的那个对象。当你向容器中插入一个对象时,你插入的是该对象的拷贝而不是它本身;当你从容器中获取一个对象时,你获取的是容器中对象的拷贝。

拷贝是STL的基本工作方式。当你删除或者插入某个对象时,现有容器中的元素会移动(拷贝);当你使用了排序算法,remove、uniquer或者他们的同类,rotate或者reverse,对象会移动(拷贝)。

一个使拷贝更高效、正确的方式是建立指针的容器而不是对象的容器,即保存对象的指针而不是对象,然而,指针的容器有它们自己STL相关的头疼问题,改进的方法是采用智能指针。

条款4:用empty来代替检查size()是否为0

对于任意容器c,写下

if (c.size() == 0)…

本质上等价于写下

if (c.empty())…

但是为什么第一种方式比第二种优呢?理由很简单:对于所有的标准容器,empty是一个常数时间的操作,但对于一些list实现,size花费线性时间。

这什么造成list这么麻烦?为什么不能也提供一个常数时间的size?如果size是一个常数时间操作,当进行增加/删除操作时每个list成员函数必须更新list的大小,也包括了splice,这会造成splice的效率降低(现在的splice是常量级的),反之,如果splice不必修改list大小,那么它就是常量级地,而size则变为线性复杂度,因此,设计者需要权衡这两个操作的算法:一个或者另一个可以是常数时间操作。

条款5:尽量使用区间成员函数代替单元素操作

给定两个vector,v1和v2,怎样使v1的内容和v2的后半部分一样?

可行的解决方案有:

(1) 使用区间函数assign:

 v1.assign(v2.begin() + v2.size() / 2, v2.end()); 

(2) 使用单元素操作:

 vector<Widget>::const_iterator ci = v2.begin() + v2.size() / 2;

ci != v2.end();

++ci)

v1.push_back(*ci); 

(3) 使用copy区间函数

 v1.clear();

copy(v2.begin() + v2.size() / 2, v2.end(), back_inserter(v1)); 

(4) 使用insert区间函数

 v1.insert(v1.end(), v2.begin() + v2.size() / 2, v2.end()); 

最优的方案是assign方案,理由如下:

首先,使用区间函数的好处是:

● 一般来说使用区间成员函数可以输入更少的代码。

● 区间成员函数会导致代码更清晰更直接了当。

使用copy区间函数存在的问题是:

【1】 需要编写更多的代码,比如:v1.clear(),这个与insert区间函数类似

【2】 copy没有表现出循环,但是在copy中的确存在一个循环,这会降低性能

使用insert单元素版本的代码对你征收了三种不同的性能税,分别为:

【1】 没有必要的函数调用;

【2】 无效率地把v中的现有元素移动到它们最终插入后的位置的开销;

【3】 重复使用单元素插入而不是一个区间插入必须处理内存分配。

下面进行总结:

说明:参数类型iterator表示容器的迭代器类型,也就是container::iterator,参数类型InputIterator表示可以接受任何输入迭代器。

【1】 区间构造

所有标准容器都提供这种形式的构造函数:

 container::container(InputIterator begin, // 区间的起点

InputIterator end); // 区间的终点 

【2】 区间插入

所有标准序列容器都提供这种形式的insert:


void container::insert(iterator position, // 区间插入的位置

InputIterator begin, // 插入区间的起点

InputIterator end); // 插入区间的终点

关联容器使用它们的比较函数来决定元素要放在哪里,所以它们了省略position参数。

.

 void container::insert(lnputIterator begin, InputIterator end); 

【3】 区间删除

每个标准容器都提供了一个区间形式的erase,但是序列和关联容器的返回类型不同。序列容器提供了这个:

 iterator container::erase(iterator begin, iterator end); 

而关联容器提供这个:

 void container::erase(iterator begin, iterator end); 

为什么不同?解释是如果erase的关联容器版本返回一个迭代器(被删除的那个元素的下一个)会招致一个无法接受的性能下降.

【4】 区间赋值

所有标准列容器都提供了区间形式的assign:

 void container::assign(InputIterator begin, InputIterator end); 

条款6:警惕C++最令人恼怒的解析

假设你有一个int的文件,你想要把那些int拷贝到一个list中。这看起来像是一个合理的方式:


ifstream dataFile("ints.dat");

list<int> data(istream_iterator<int>(dataFile), // 警告!这完成的并不

istream_iterator<int>()); // 是像你想象的那样

这里的想法是传一对istream_iterator给list的区间构造函数(参见条款5),因此把int从文件拷贝到list中。

实际上,这段代码可以编译通过,但运行时不会产生任何结果。仔细分析后,会发现,你这段代码实际上是声明了一个data函数,它的返回值是list<int>,两个参数均为istream_iterator<int>类型。

解决办法是在数据声明中从时髦地使用匿名istream_iterator对象后退一步,仅仅给那些迭代器名字。以下代码到哪里都能工作:


ifstream dataFile("ints.dat");

istream_iterator<int> dataBegin(dataFile);

istream_iterator<int> dataEnd;

list<int> data(dataBegin, dataEnd);

条款7:当使用new得指针的容器时,记得在销毁容器前delete那些指针

条款8:永不建立auto_ptr的容器

条款9:在删除选项中仔细选择

(1)假定你有一个标准STL容器,c,容纳int,

 Container<int> c; 

而你想把c中所有值为1963的对象都去,则不同的容器类型采用的方法不同:没有一种是通用的.

[1] 如果采用连续内存容器(vector、queue和string),最好的方法是erase-remove惯用法:


c.erase(remove(c.begin(), c.end(), 1963), // 当c是vector、string

c.end()); // 或deque时,erase-remove惯用法是去除特定值的元素的最佳方法

[2] 对于list,最有效的方法是直接使用remove函数:

 c.remove(1963); 

[3] 对于关联容器,解决问题的适当方法是调用erase:

 c.erase(1963); // 当c是标准关联容器时,erase成员函数是去除特定值的元素的最佳方法 

(2)让我们换一下问题:不是从c中除去每个有特定值的元素,而是消除下面判断式返回真的每个对象:

 bool badValue(int x); // 返回x是否是“bad” 

[1] 对于序列容器(vector、list、deque和string),只需要将remove换成remove_if即可:


c.erase(remove_if(c.begin(), c.end(), badValue), // 当c是vector、string

c.end()); // 或deque时这是去掉badValue返回真的对象的最佳方法

c.remove_if(badValue); // 当c是list时这是去掉badValue返回真的对象的最佳方法

[2] 对于关联容器,有两种方法处理该问题,一个更容易编码,另一个更高效。“更容

易但效率较低”的解决方案用remove_copy_if把我们需要的值拷贝到一个新容器中,然后把原容器的内容和新的交换:


AssocContainer<int> c; // c现在是一种标准关联容器

AssocContainer<int> goodValues; // 用于容纳不删除的值的临时容器

remove_copy_if(c.begin(), c.end(), // 从c拷贝不删除

inserter(goodValues, // 的值到

goodValues.end()), // goodValues

badValue);

c.swap(goodValues); // 交换c和goodValues的内容

“更高效”的解决方案是直接从原容器删除元素。不过,因为关联容器没有提供类似remove_if的成员函数,所以我们必须写一个循环来迭代c中的元素,和原来一样删除元素:


AssocContainer<int> c;

...

for (AssocContainer<int>::iterator i = c.begin(); // for循环的第三部分

i != c.end(); // 是空的;i现在在下面

/*nothing*/ ){ // 自增

if (badValue(*i)) c.erase(i++); // 对于坏的值,把当前的

else ++i; // i传给erase,然后

} // 作为副作用增加i;对于好的值,只增加i

(3)进一步丰富该问题:不仅删除badValue返回真的每个元素,而且每当一个元素被删掉时,我们也想把一条消息写到日志文件中。

[1] 对于关联容器,只需要对我们刚才开发的循环做一个微不足道的修改就行了:


ofstream logFile; // 要写入的日志文件

AssocContainer<int> c;

...

for (AssocContainer<int>::iterator i = c.begin(); // 循环条件和前面一样

i !=c.end();){

if (badValue(*i)){

logFile << "Erasing " << *i <<'\n'; // 写日志文件

c.erase(i++); // 删除元素

}

else ++i;

}

[2] 对于vector、string、list和deque,必须利用erase的返回值。那个返回值正是我们需要的:一旦删除完成,它就是指向紧接在被删元素之后的元素的有效迭代器。换句话说,我们这么写:


for (SeqContainer<int>::iterator i = c.begin();

i != c.end();){

if (badValue(*i)){

logFile << "Erasing " << *i << '\n';

i = c.erase(i); // 通过把erase的返回值赋给i来保持i有效

}

else

++i;

}

条款10:注意分配器的协定和约束

条款11:理解自定义分配器的正确用法

条款12:对STL容器线程安全性的期待现实一些

当涉及到线程安全和STL容器时,你可以确定库实现了“允许在一个容器上的多读者”(在读取时不能 有任何写入者操作这个容器。)和“不同容器上的多个写者”(多线程可以同时写不同的容器。)。你不能希望库消除对手工并行控制的需要,且你完全不能依赖于任何线程支持。