首家大数据培训挂牌机构 股票代码: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由小牛君创建

分享到:



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

2、 vector和string

所 有的STL容器都很有用,但是相比于其他容器,vector和string更常用。本章从多个角度覆盖vector和string,如:为什么提倡使用 vector代替数组,怎样改进vector和string的性能?怎样除去过剩的内存,vector<string>是个什么东西?……

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

使 用vector和string代替动态分配的数组是个很明智的选择,它们不仅能够自动管理内存(主要是自动释放内,自动增加内存),还提供了很多可用的函 数和类型:既有像begin、end和size这样的成员函数,也有内嵌的像iterator、 reverse_iterator或value_type的typedef。

对于string实现,可能使用了引用计数器,这是一种那个消 除了不必要的内存分配和字符拷贝的策略,而且在很多应用中可以提高性能。但这种方案在多线程环境下可能会严重降低性能,可能的解决方法是:(1)关闭引用 计数(如果可能的话) (2)寻找或开发一个不使用引用计数的string实现(或部分实现)替代品 (3)考虑使用vector<char>来代替string,vector实现不允许使用引用计数,所以隐藏的多线程性能问题不会出现了

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

reserve成员函数允许你最小化必须进行的重新分配的次数,因而可以避免真分配的开销和迭代器/指针/引用失效。

● size()返回容器中已经保存的元素个数

● capacity()返回容器可以保存的最大元素个数。如果要知道一个vector或string中有多少没有被占用的内存,可以让capacity() 减去size();如果size和capacity返回同样的值,容器中就没有剩余空间了,而下一次插入(通过insert或push_back等)会引 发重分配。

● resize(Container::size_type n)强制把容器改为容纳n个元素。调用resize之后,size将会返回n。如果n小于当前大小,容器尾部的元素会被销毁。如果n大于当前大小,新默认 构造的元素会添加到容器尾部。如果n大于当前容量,在元素加入之前会发生重新分配。

● reserve(Container::size_type n)强制容器把它的容量改为至少n,提供的n不小于当前大小。这一般强迫进行一次重新分配,因为容量需要增加。(如果n小于当前容量,vector忽略 它,这个调用什么都不做,string可能把它的容量减少为size()和n中大的数,但string的大小没有改变。)

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

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

我们可以将vector或者string传递给数组/指针类型的参数,如:

【1】 用C风格API返回的元素初始化一个vector,可以利用vector和数组潜在的内存分布兼容性将存储vecotr的元素的空间传给API函数:


// C API:此函数需要一个指向数组的指针,数组最多有arraySize个double

// 而且会对数组写入数据。它返回写入的double数,不会大于arraySize

size_t fillArray(double *pArray, size_t arraySize);

vector<double> vd(maxNumDoubles); // 建立一个vector,它的大小是maxNumDoubles

vd.resize(fillArray(&vd[0], vd.size())); // 让fillArray把数据写入vd,然后调整vd的大小 为fillArray写入的元素个数

【2】 用C风格API的数据初始化string对象,也很简单。只要让API将数据放入一个vector<char>,然后从vector中将数据拷到string:


// C API:此函数需要一个指向数组的指针,数组最多有arraySize个char

// 而且会对数组写入数据。它返回写入的char数,不会大于arraySize

size_t fillString(char *pArray, size_t arraySize);

vector<char> vc(maxNumChars); // 建立一个vector, 它的大小是maxNumChars

size_t charsWritten = fillString(&vc[0], vc.size()); // 让fillString把数据写入vc

string s(vc.begin(), vc.begin()+charsWritten); // 从vc通过范围构造函数拷贝数据到s

【3】让C风格API把数据放入一个vector,然后拷到你实际想要的STL容器中的主意总是有效的:


size_t fillArray(double *pArray, size_t arraySize); // 同上

vector<double> vd(maxNumDoubles); // 一样同上

vd.resize(fillArray(&vd[0], vd.size()));

deque<double> d(vd.begin(), vd.end()); // 拷贝数据到deque

list<double> l(vd.begin(), vd.end()); // 拷贝数据到list

set<double> s(vd.begin(), vd.end()); // 拷贝数据到set

【4】如何将vector和string以外的STL容器中的数据传给C风格API?只要将容器的每个数据拷到vector,然后将它们传给API:


void doSomething(const int* pints, size_t numInts); // C API (同上)

set<int> intSet; // 保存要传递给API数据的set

...

vector<int> v(intSet.begin(), intSet.end()); // 拷贝set数据到vector

if (!v.empty()) doSomething(&v[0], v.size()); // 传递数据到API

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

实 际项目中可能遇到这样的情况:刚开始时,将大量数据插入到一个vector中,后来随着实际的需要,将大量元素从这个vector中删除,这样的 话,vector中会占用大量未使用的内存(通过函数capacity()可看到结果),如何将这些未使用的内存释放,可采用以下几种方法:

 vector<Contestant>(contestants).swap(contestants); 

表达式vector<Contestant>(contestants)建立一个临时vector,它是 contestants的一份拷贝:vector的拷贝构造函数做了这个工作。但是,vector的拷贝构造函数只分配拷贝的元素需要的内存,所以这个临 时vector没有多余的容量。然后我们让临时vector和contestants交换数据,这时contestants只有临时变量的修整过的容量, 而这个临时变量则持有了曾经在contestants中的发胀的容量。在这里(这个语句结尾),临时vector被销毁,因此释放了以前 contestants使用的内存

同样的技巧可以应用于string:


string s;

... // 使s变大,然后删除所有它的字符

string(s).swap(s); // 在s上进行“收缩到合适”

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

作为一个STL容器,vector<bool>有两个问题。第一,它不是一个STL容器。第二,它并不容纳bool,因而永远不要使用vector<bool>。

标 准库提供了两个替代品,它们能满足几乎所有需要。第一个是deque<bool>。deque提供了几乎所有vector所提供的(唯一值得 注意的是reserve和capacity),而deque<bool>是一个STL容器,它保存真正的bool值。当然,deque内部内 存不是连续的。所以不能传递deque<bool>中的数据给一个希望得到bool数组的C API。第二个vector<bool>的替代品是bitset。bitset不是一个STL容器,但它是C++标准库的一部分。与STL容 器不同,它的大小(元素数量)在编译期固定,因此它不支持插入和删除元素。此外,因为它不是一个STL容器,它也不支持iterator

3、 关联容器

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

set中的find函数采用的是等价准则,而find算法采用的是相等准则。

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

当关联容器中保存的是对象指针时,需要自己定义比较器(不是一个函数,而是一个仿函数模板),不然关联容器会按照指针大小进行排序,而不是指针指向的内容。

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

在关联容器中,用户自定义比较类型时,当两个元素相等时,应该返回false。

举例:建立一个set,比较类型用less_equal,然后插入一个10:


set<int, less_equal<int> > s; // s以“<=”排序

s.insert(10); // 插入10

然后再插入一次10:

 s.insert(10); 

关联容器对“相同”的定义是等价,因此set测试10B是否等价于10A。当执行这个测试时,它自然是使用set的比较函数。在这一例子 里,是operator<=,因为我们指定set的比较函数为less_equal,而less_equal意思就是operator<=。 于是,set将计算这个表达式是否为真:

 !(10A <= 10B) && !(10B <= 10A) // 测试10A和10B是否等价 

显然,该表达式返回false,于是两个10都会插入这个set,结果是set以拥有了两个为10的值的拷贝而告终,也就是说它不再是一个set了。通过使用less_equal作为我们的比较类型,我们破坏了容器!

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

原地修改map和multimap的键值是不允许的,同时,应避免原地修改set和multiset的键(尽管这是允许的),因为这可能影响容器有序性的元素部分,破坏掉容器。

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

在你的应用中,如果查找的频繁程度比插入和删除的高很多,那么推荐你用有序vector代替关联容器,这主要是从内存引用失效频率考虑的。

用vector模拟关联数组的代码如下:


typedef pair<string, int> Data; // 在这个例子里

// "map"容纳的类型

class DataCompare { // 用于比较的类

 public:

  bool operator()(const Data& lhs, // 用于排序的比较函数

   const Data& rhs) const

 {

  return keyLess(lhs.first, rhs.first); // keyLess在下面

}

bool operator()(const Data& Ihs, // 用于查找的比较函数

const Data::first_type& k) const // (形式1)

{

  return keyLess(lhs.first, k);

}

bool operator()(const Data::first_type& k, // 用于查找的比较函数

const Data& rhs) const // (形式2)

{

  return keyLess(k, rhs.first);

}

private:

bool keyLess(const Data::first_type& k1, const Data::first_type& k2) const // “真的” 比较函数

{

  return k1 < k2;

}

};

vector<Data> vd; // 代替map<string, int>

... // 建立阶段:很多插入,

// 几乎没有查找

sort(vd.begin(), vd.end(), DataCompare()); // 结束建立阶段。(当模拟multimap时,你可能更喜欢用stable_sort 来代替)

string s; // 用于查找的值的对象

... // 开始查找阶段

if (binary_search(vd.begin(), vd.end(), s,

DataCompare()))... // 通过binary_search查找

vector<Data>::iterator i =

lower_bound(vd.begin(), vd.end(), s,

DataCompare()); // 再次通过lower_bound查找,

if (i != vd.end() && !DataCompare()(s, *i))... // 条款45解释了“!DataCompare()(s, *i)”测试

pair<vector<Data>::iterator,

vector<Data>::iterator> range =

equal_range(vd.begin(), vd.end(), s,

DataCompare()); // 通过equal_range查找

if (range.first != range.second)...

... // 结束查找阶段,开始

// 重组阶段

sort(vd.begin(), vd.end(), DataCompare()); // 开始新的查找阶段...

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

STL map的operator[]被设计为简化“添加或更新”功能,但事实上,当“增加”被执行时,insert比operator[]更高效。当进行更新 时,情形正好相反,也就是,当一个等价的键已经在map里时,operator[]更高效。理由如下:当进行“增加”操作时,operator[]会有三 个函数调用:构造临时对象,撤销临时对象和对对象复制,而insert不会有;而对于更新操作,insert需要构造和析构对象,而operator[] 采用的对象引用,不会有这样的效率损耗。一个较为高效的“添加或更新”功能实现如下:


template<typename MapType, // map的类型

typename KeyArgType, // KeyArgType和ValueArgtype是类型参数

typename ValueArgtype>

typename MapType::iterator

efficientAddOrUpdate(MapType& m, const KeyArgType& k, const ValueArgtype& v)

{

  typename MapType::iterator Ib = // 找到k在或应该在哪里;

  m.lower_bound(k);

  if(Ib != m.end() && // 如果Ib指向一个pair

   !(m.key_comp()(k, Ib->first))) { // 它的键等价于k...

  Ib->second = v; // 更新这个pair的值

  return Ib; // 并返回指向pair的迭代器

 } else{

  typedef typename MapType::value_type MVT;

  return m.insert(Ib, MVT(k, v)); // 把pair(k, v)添加到m并返回指向新map元素的迭代器

 }

}

条款25:XXXXXXXXXXXXXXXXXXXX(不常用)