`
yangyou230
  • 浏览: 1639470 次
文章分类
社区版块
存档分类

《Effective STL》学习笔记2

阅读更多
转载自董的博客

本文链接地址: http://dongxicheng.org/cpp/effective-stl-part2/

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函数:


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

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


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

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

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

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

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

1
2
3
4
5
6
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:

1
2
3
4
set<int, less_equal<int> > s;// s以“<=”排序
s.insert(10); // 插入10

然后再插入一次10:

1
s.insert(10);

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

1
!(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模拟关联数组的代码如下:

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

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

条款25:XXXXXXXXXXXXXXXXXXXX(不常用)


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics