Effective STL中文版 8.9分
读书笔记 第226页
[已注销]

## 术语: * 重载了函数调用操作符(即,operator())的任何类叫做仿函数类。从这样的类建立的对象称为函数对象或仿函 数。 ## 条款1:仔细选择你的容器 标准STL序列容器:vector、string、deque和list 标准STL关联容器:set、multiset、map和multimap 标准的连续内存容器是vector、string和deque。 ## 条款2:小心对“容器无关代码”的幻想 不同的容器是不同的,而且它们的优点和缺点有重大不同。它们并不被设计成可互换的,而且你做不了什么包装的工作 ## 条款3:使容器里对象的拷贝操作轻量而正确 当你向容器中添加一个对象(比如通过insert或push_back等),进入容器的是你指定的对象的拷贝。拷进去,拷出来。这就是STL的方式。 如果你用一个拷贝过程很昂贵对象填充一个容器,那么一个简单的操作——把对象放进容器也会被证明为是一个性能瓶颈。容器中移动越多的东西,你就会在拷贝上浪费越多的内存和时钟周期。 一个使拷贝更高效、正确而且对分割问题免疫的简单的方式是建立指针的容器而不是对象的容器。 ## 条款4:用empty来代替检查size()是否为0 对于所有的标准容器,empty是一个常数时间的操作,但对于一些list实现,size花费线性时间。 ## 条款5:尽量使用区间成员函数代替它们的单元素兄弟 一个区间插入可以在开始插入东西前计算出需要多少新内存(假设给的是前向迭代器),所以它不用多于一次地重新分配vector的内在内存。就像你可以想象到的,这个节省相当可观。 * 区间构造。所有标准容器都提供这种形式的构造函数。 ``` container::container(InputIterator begin, // 区间的起点 InputIterator end); // 区间的终点 ``` * 区间插入。所有标准序列容器都提供这种形式的insert: ``` void container::insert(iterator position, // 区间插入的位置 InputIterator begin, // 插入区间的起点 InputIterator end); // 插入区间的终点 ``` 关联容器 ``` void container::insert(lnputIterator begin, InputIterator end); ``` * 区间删除。每个标准容器都提供了一个区间形式的erase,但是序列和关联容器的返回类型不同。序列容器提供 了这个: ``` iterator container::erase(iterator begin, iterator end); ``` 而关联容器提供这个: ``` void container::erase(iterator begin, iterator end); ``` * 区间赋值。所有标准列容器都提供了区间形式的assign: ``` void container::assign(InputIterator begin, InputIterator end); ``` ## 条款6:警惕C++最令人恼怒的解析 几乎任何东西都可能被分析成函数声明。 声明了一个函数g,它带有一个参数,那个参数是指向一个没有参数、返回double的函数的指针: ``` int g(double (*pf)()); // g带有一个指向函数的指针作为参数 ``` 等价形式:pf使用非指针语法来声明 ``` int g(double pf()); // 同上;pf其实是一个指针 ``` 参数名可以省略,所以这是g的第三种声明,去掉了pf这个名字: ``` int g(double ()); // 同上;参数名省略 ``` 假设你有一个int的文件,你想要把那些int拷贝到一个list中。这里的想法是传一对istream_iterator给list的区间构造函数,因此把int从文件拷贝到list中。 ``` ifstream dataFile("ints.dat"); list<int> data(istream_iterator<int>(dataFile), istream_iterator<int>()); ``` 以上第二行声明了一个函数data,它的返回类型是list<int>。这个函数data带有两个参数: ● 第一个参数叫做dataFile。它的类型是istream_iterator<int>。dataFile左右的括号是多余的而且被忽略。 ● 第二个参数没有名字。它的类型是指向一个没有参数而且返回istream_iterator<int>的函数的指针。 正确做法:用括号包围一个实参的声明是不合法的,但用括号包围一个函数调用的观点是合法的,所以通过增加一对括号,我们强迫编译器以我们的方式看事情 ``` list<int> data((istream_iterator<int>(dataFile)), // 注意在list构造函数 istream_iterator<int>()); // 的第一个实参左右的新括号 ``` ## 条款7:当使用new得指针的容器时,记得在销毁容器前delete那些指针 ## 条款8:永不建立auto_ptr的容器 auto_ptr的容器(COAPs)是禁止的。试图使用它们的代码都不能编译。 当你拷贝一个auto_ptr时,auto_ptr所指向对象的所有权被转移到拷贝的auto_ptr,而被拷贝的auto_ptr被设为NULL。你正确地说一遍:拷贝一个auto_ptr将改变它的值 ## 条款9:在删除选项中仔细选择 ``` Container<int> c; ``` 如果要删除其中值为1963的元素。 * 如果你有一个连续内存容器(vector、deque或string——参见条款1),最好的方法是erase-remove惯用法: ``` c.erase(remove(c.begin(), c.end(), 1963), // 当c是vector、string或deque时 c.end()); // erase-remove惯用法是去除特定值的元素的最佳方法 ``` * list的成员函数remove更高效: ``` c.remove(1963); // 当c是list时,remove成员函数是去除特定值的元素的最佳方法 ``` * 对于关联容器,解决问题的适当方法是调用erase: ``` c.erase(1963); // 当c是标准关联容器时, erase成员函数是去除特定值的元素的最佳方法 ``` 去除一个容器中满足一个特定判定式的所有对象: * 如果容器是vector、string或deque,使用erase-remove_if惯用法。 * 如果容器是list,使用list::remove_if。 * 如果容器是标准关联容器,使用remove_copy_if和swap,或写一个循环来遍历容器元素,当你把迭代器传给erase时记得后置递增它。 在循环内做某些事情(除了删除对象之外): * 如果容器是标准序列容器,写一个循环来遍历容器元素,每当调用erase时记得都用它的返回值更新你的迭代器。 * 如果容器是标准关联容器,写一个循环来遍历容器元素,当你把迭代器传给erase时记得后置递增它。 ## 条款10:注意分配器的协定和约束 ## 条款11:理解自定义分配器的正确用法 ## 条款12:对STL容器线程安全性的期待现实一些 从实现里确定的最多是下列内容: * 多个读取者是安全的。多线程可能同时读取一个容器的内容,这将正确地执行。当然,在读取时不能 有任何写入者操作这个容器。 * 对不同容器的多个写入者是安全的。多线程可以同时写不同的容器。 ## 条款13:尽量使用vector和string来代替动态分配的数组 我想到了一个(也是唯一一个)用vector或string代替动态分配数组会出现的问题,而且它只关系到string。很多string实现在后台使用了引用计数(参见条款15),一个消除了不必要的内存分配和字符拷贝的策略,而且在很多应用中可以提高性能。 ## 条款14:使用reserve来避免不必要的重新分配 关于STL容器,最神奇的事情之一是只要不超过它们的最大大小,它们就可以自动增长到足以容纳你放进去的数据。(要知道这个最大值,只要调用名叫max_size的成员函数。) 这个类似于realloc的操作有四个部分: 1. 分配新的内存块,它有容器目前容量的几倍。在大部分实现中,vector和string的容量每次以2为因数增 长。也就是说,当容器必须扩展时,它们的容量每次翻倍。 2. 把所有元素从容器的旧内存拷贝到它的新内存。 3. 销毁旧内存中的对象。 4. 回收旧内存。 size()告诉你容器中有多少元素。 capacity()告诉你容器在它已经分配的内存中可以容纳多少元素。 resize(Container::size_type n)强制把容器改为容纳n个元素。调用resize之后,size将会返回n。如果n小于当前大小,容器尾部的元素会被销毁。 reserve(Container::size_type n)强制容器把它的容量改为至少n,提供的n不小于当前大小。这一般强迫进行一次重新分配,因为容量需要增加。 ``` vector<int> v; for (int i = 1; i <= 1000; ++i) v.push_back(i); ``` 在大多数STL实现中,这段代码在循环过程中将会导致2到10次重新分配。(10这个数没什么奇怪的。记住vector在重新分配发生时一般把容量翻倍,而1000约等于210。) 把代码改为使用reserve, 这在循环中不会发生重新分配。 ``` vector<int> v; v.reserve(1000); for (int i = 1; i <= 1000; ++i) v.push_back(i); ``` ## 条款15:小心string实现的多样性 * 字符串值可能是或可能不是引用计数的。 * string对象的大小可能从1到至少7倍char*指针的大小。 * 新字符串值的建立可能需要0、1或2次动态分配。 * string对象可能是或可能不共享字符串的大小和容量信息。 * string可能是或可能不支持每对象配置器。 * 不同实现对于最小化字符缓冲区的配置器有不同策略。 ## 条款16: 如何将vector和string的数据传给遗留的API 类似从vector上获取指向内部数据的指针的方法,对string不是可靠的,因为(1)string中的数据并没有保证被存储在独立的一块连续内存中,(2)string的内部表示形式并没承诺以一个null字符结束。这解释了string的成员函数c_str存在的原因,它返回一个按C风格设计的指针,指向string的值。 事实上,让C风格API把数据放入一个vector,然后拷到你实际想要的STL容器中的主意总是有效的 ## 条款17:使用“交换技巧”来修整过剩容量 这是你怎么修整你的竞争者vector过剩容量的方法: ``` vector<Contestant>(contestants).swap(contestants); ``` ## 条款18:避免使用vector<bool> vector<bool>确实只有两个问题。第一,它不是一个STL容器。第二,它并不容纳bool。 如果c是一个T类型对象的容器,且c支持operator[],那么以下代码必须能够编译: ``` T *p = &c[0]; // 无论operator[]返回什么, // 都可以用这个地址初始化一个T* ``` 每个保存在“vector”中的“bool”占用一个单独的比特,而一个8比特的字节将容纳8个“bool”。在内部,vector<bool>使用了与位域(bitfield)等价的思想来表示它假装容纳的bool。 标准库提供了两个替代品,它们能满足几乎所有需要。 * 第一个是deque<bool>。deque提供了几乎所有vector所提供的(唯一值得注意的是reserve和capacity),而deque<bool>是一个STL容器,它保存真正的bool值。 * 第二个vector<bool>的替代品是bitset。bitset不是一个STL容器,但它是C++标准库的一部分。与STL容器不同,它的大小(元素数量)在编译期固定,因此它不支持插入和删除元素。此外,因为它不是一个STL容器,它也不支持iterator。但就像vector<bool>,它使用一个压缩的表示法, ## 条款19:了解相等和等价的区别 find算法和set的insert成员函数是很多必须判断两个值是否相同的函数的代表。但它们以不同的方式完成,find对“相同”的定义是相等,基于operator==。set::insert对“相同”的定义是等价,通常基于operator<。 操作上来说,相等的概念是基于operator==的。如果表达式“x == y”返回true,x和y有相等的值,否则它们没有。 两个值如果没有哪个在另一个之前(关于某个排序标准),那么它们等价。 ## 条款20:为指针的关联容器指定比较类型 ## 条款21: 永远让比较函数对相等的值返回false 关联容器对“相同”的定义是等价,通过使用less_equal作为我们的比较类型,我们破坏了容器(例如set)! ## 条款22:避免原地修改set和multiset的键 Key是const类型,需要用key保持有序 如果你要总是可以工作而且总是安全地改变set、multiset、map或multimap里的元素,按五个简单的步骤去做: 1. 定位你想要改变的容器元素。如果你不确定最好的方法,条款45提供了关于怎样进行适当搜寻的指导。 2. 拷贝一份要被修改的元素。对map或multimap而言,确定不要把副本的第一个元素声明为const。毕竟,你想要改变它! 3. 修改副本,使它有你想要在容器里的值。 4. 从容器里删除元素,通常通过调用erase(参见条款9)。 5. 把新值插入容器。如果新元素在容器的排序顺序中的位置正好相同或相邻于删除的元素,使用insert的“提示”形式把插入的效率从对数时间改进到分摊的常数时间。使用你从第一步获得的迭代器作为提示。 ## 条款23:考虑用有序vector代替关联容器 数据结构使用的时候查找几乎不和插入和删除混合时,使用有序vector代替关联容器才有意义。 ## 条款24:当关乎效率时应该在map::operator[]和map-insert之间仔细选择 insert 通常节省了三次函数调用:一个建立临时的默认构造Widget对象,一个销毁那个临时的对象和一个对Widget的赋值操作。那些函数调用越昂贵,你通过使用map-insert代替map::operator[]就能节省越多。 ## 条款25:熟悉非标准散列容器 在C++标准委员会的议案中,散列容器的名字是unordered_set、unordered_multiset、unordered_map和unordered_multimap。恰好是为了避开现存的hash_*名字。 ## 条款26:尽量用iterator代替const_iterator,reverse_iterator和const_reverse_iterator ## 条款27:用distance和advance把const_iterator转化成iterator ``` typedef deque<int> IntDeque; typedef IntDeque::iterator Iter; typedef IntDeque::const_iterator ConstIter; IntDeque d; ConstIter ci; ... // 让ci指向d Iter i(d.begin()); // 初始化i为d.begin() advance(i, distance(i, ci)); // 把i移到指向ci位置(但请留意下面关于为什么在它编译前要调整的原因) ``` ## 条款28:了解如何通过reverse_iterator的base得到iterator 因为vector的insert函数不接受reverse_iterator。如果你想要删除ri所指位置上的元素也会有同样的问题。erase成员函数会拒绝reverse_iterator,坚持要求iterator。为了完成删除和一些形式的插入操作,你必须先通过base函数将reverse_iterator转换成iterator,然后用iterator来完成工作。 ``` vector<int> v; v.reserve(5); // 参见条款14 for(int i = 0;i < 5; ++ i) { // 向vector插入1到5 v.push_back(i); } vector<int>::reverse_iterator ri = // 使ri指向3 find(v.rbegin(), v.rend(), 3); vector<int>::iterator i(ri.base()); // 使i和ri的base一样 ``` 执行上述代码后,可以想到产生的结果就像这样: ## 条款29:需要一个一个字符输入时考虑使用istreambuf_iterator istreambuf_iterators。你可以像istream_iterator一样使用istreambuf_iterator,但istream_iterator<char>对象使用operator>>来从输入流中读取单个字符。istreambuf_iterator<char>对象进入流的缓冲区并直接读取下一个字符。 ## 条款30:确保目标区间足够大 “请把transform的结果放入叫做results容器的结尾”的方式是调用back_inserter来产生指定目标区间起点的迭代器: ``` vector<int> results; // 把transmogrify应用于 transform(values.begin(), values.end(), // values中的每个对象, back_inserter(results), // 在results的结尾 transmogrify); // 插入返回的values ``` 如果你想让一个算法在容器的前端插,你可以使用front_inserter。在内部,front_inserter利用了push_front,所以front_insert只和提供那个成员函数的容器配合(也就是deque和list): ``` list<int> results; // results现在是list transform(values.begin(), values.end(), // 在results前端 front_inserter(results), // 以反序 transmogrify); // 插入transform的结果 ``` ## 条款31:了解你的排序选择 总结一下你的排序选择: * 如果你需要在vector、string、deque或数组上进行完全排序,你可以使用sort或stable_sort。 *你有一个vector、string、deque或数组,你只需要排序前n个元素,应该用partial_sort。 * 如果你有一个vector、string、deque或数组,你需要鉴别出第n个元素或你需要鉴别出最前的n个元素,而不用知道它们的顺序,nth_element是你应该注意和调用的。 * 如果你需要把标准序列容器的元素或数组分隔为满足和不满足某个标准,你大概就要找partition或stable_partition。 * 如果你的数据是在list中,你可以直接使用partition和stable_partition,你可以使用list的sort来代替sort和stable_sort。如果你需要partial_sort或nth_element提供的效果,你就必须间接完成这个任务,但正如我在上面勾画的,会有很多选择。 需要更少资源(时间和空间)的算法列在需要更多的前面: 1. partition 2. stable_partition 3. nth_element 4. partial_sort 5. sort 6. stable_sort ## 条款32:如果你真的想删除东西的话就在类似remove的算法后接上erase remove移动指定区间中的元素直到所有“不删除的”元素在区间的开头(相对位置和原来它们的一样)。它返回一个指向最后一个的下一个“不删除的”元素的迭代器。返回值是区间的“新逻辑终点”。 删除所有99: ``` vector<int> v; // 正如从前 v.erase(remove(v.begin(), v.end(), 99), v.end()); // 真的删除所有等于99的元素 ``` 对于list,调用remove成员函数比应用erase-remove惯用法更高效 ## 条款33:提防在指针的容器上使用类似remove的算法 ## 条款34:注意哪个算法需要有序区间 这里有一个只能操作有序数据的算法的表: binary_search lower_bound upper_bound equal_range set_union set_intersection set_difference set_symmetric_difference merge inplace_merge includes 算法set_union、set_intersection、set_difference和set_symmetric_difference的四人组提供了线性时间设置它们名字所提出的操作的性能。为什么它们需要有序区间?因为如果不是的话,它们不能以线性时间完成它们的工作。 如果你传一个区间给一个也带有比较函数的算法,确保你传递的比较函数行为和你用于排序这个区间的一样。 例如,默认情况下,binary_search假设它搜索的区间是以“<”排序(也就是,值是升序),如果自定义的vector是降序,调用binary_search也要指定相应比较函数: ``` vector<int> v; sort(v.begin(), v.end(), greater<int>()); // 降序排列 bool a5Exists = binary_search(v.begin(), v.end(), 5. greater<int>()); // 搜索5 ``` ## 条款35:通过mismatch或lexicographical比较实现简单的忽略大小写字符串比较 lexicographical_compare是strcmp的泛型版本。strcmp只对字符数组起作用,但lexicographical_compare对所有任何类型的值的区间都起作用。同时,strcmp总是比较两个字符来看看它们的关系是相等、小于或大于另一个。lexicographical_compare可以传入一个决定两个值是否满足一个用户定义标准的二元判断式。 ``` bool ciCharLess(char c1, char c2) // 返回在忽略大小写的情况下c1是否在c2前面; { tolower(static_cast<unsigned char>(c1)) < // 条款46解释了为什么 tolower(static_cast<unsigned char>(c2)); // 一个函数对象可能比函数好 } bool ciStringCompare(const string& s1, const string& s2) { return lexicographical_compare(s1.begin(), s1.end(), s2.begin(), s2.end(), ciCharLess); } ``` 在上面的调用中,lexicographical_compare用来寻找s1和s2第一个不同的位置,基于调用ciCharLess的结果。如果,使用那个位置的字符,ciCharLess返回true,lexicographical_compare也是;如果,在第一个字符不同的位置,从第一个字符串来的字符先于对应的来自第二个字符串的字符,第一个字符串就先于第二个。就像strcmp,lexicographical_compare认为两个相等值的区间是相等的,因此它对于这样的两个区间返回false:第一个区间不在第二个之前。也像strcmp,如果第一个区间在发现不同的对应值之前就结束了,lexicographical_compare返回true:一个先于任何区间的前缀是一个前缀。 ## 条款36:了解copy_if的正确实现 STL有很多有趣的地方,其中一个是虽然有11个名字带“copy”的算法,但没有一个是copy_if。这意味着你可以replace_copy_if,你可以remove_copy_if,你可以copy_backward或者reverse_copy,但如果你只是简单地想要拷贝一个区间中满足某个判断式的元素,你只能自己做。 ``` template<typename InputIterator, // 一个copy_if的 typename OutputIterator, // 正确实现 typename Predicate> OutputIterator copy_if(InputIterator begin, InputIterator end, OutputIterator destBegin, Predicate p) { while (begin != end) { if (p(*begin))*destBegin++ = *begin; ++begin; } return destBegin; } ``` ## 条款37:用accumulate或for_each来统计区间 在那些情况中,你需要统计一个区间,但你需要有定义你需要统计的东西的能力。没问题。STL为你准备了那样的算法,它叫作accumulate。它和其他三个“数值算法”都在<numeric>中。(那三个其它的算法是inner_product、adjacent_difference和partial_sum。) 正如accumulate,for_each带有一个区间和一个函数(一般是一个函数对象)来调用区间中的每个元素,但传给for_each的函数只接收一个实参(当前的区间元素),而且当完成时for_each返回它的函数。(实际上,它返回它的函数的一个拷贝)值得注意的是,传给(而且后来要返回)for_each的函数可能有副作用。 ## 条款38:把仿函数类设计为用于值传递 ## 条款39:用纯函数做判断式 ## 条款40:使仿函数类可适配 ## 条款41:了解使用ptr_fun、mem_fun和mem_fun_ref的原因 调用语法: ``` f(x); // 语法#1:当f是一个非成员函数 x.f(); // 语法#2:当f是一个成员函数而且x是一个对象或一个对象的引用 p->f(); // 语法#3:当f是一个成员函数而且p是一个对象的指针 ``` 也许现在清楚为什么mem_fun和mem_fun_ref存在了。它们让成员函数(通常必须使用句法#2或者#3来调用的)使用句法1调用。 ## 条款42:确定less<T>表示operator< 不要通过把less的定义当儿戏来误导那些程序员。如果你使用less(明确或者隐含),保证它表示operator<。如果你想要使用一些其他标准排序对象,建立一个特殊的不叫做less的仿函数类。 ## 条款43:尽量用算法调用代替手写循环 有三个理由: * 效率:算法通常比程序员产生的循环更高效。 * 正确性:写循环时比调用算法更容易产生错误。 * 可维护性:算法通常使代码比相应的显式循环更干净、更直观。 第二个主要的效率因素是,除了最微不足道的STL算法,所有的STL算法使用的计算机科学都比一般的C++程序员能拿得出来的算法复杂——有时候会复杂得多。几乎不可能被打败的sort及其同族算法(比如,stable_sort(),nth_element()等,参见条款31);适用于有序区间的搜索算法(比如,binary_search,lower_bound等,参见条款34和35)也一样好;就算是很平凡的任务,比如从连续内存容器中除去一些对象,使用erase-remove惯用法都比绝大多数程序员写的循环更高效(参见条款9)。 ## 条款44:尽量用成员函数代替同名的算法 首先,成员函数更快。其次,比起算法来,它们与容器结合得更好(尤其是关联容器)。那是因为同名的算法和成员函数通常并不是是一样的。 ## 条款45:注意count、find、binary_search、lower_bound、upper_bound 和equal_range的区别 ## 条款46:考虑使用函数对象代替函数作算法的参数 把函数指针作为参数会抑制内联的事实解释了一个长期使用C的程序员经常发现却难以相信的现象:在速度上,C++的sort实际上总是使C的qsort感到窘迫。 两个排序版本: ``` vector<double> v; ... sort(v.begin(), v.end(), greater<double>()); inline bool doubleGreater(double d1, double d2) { return dl > d2; } ... sort(v.begin(), v.end(), doubleGreater); ``` 使用greater<double>的版本每次都比较快。 在上面的例子中,greater<double>::operator()是一个内联函数,所以编译器在实例化sort时内联展开它。结果,sort没有包含一次函数调用。 ## 条款47:避免产生只写代码 只写代码:很容易写,但很难读和理解。 一个程序员很有表现力的方法是另一个程序员的噩梦。 ## 条款48:总是#include适当的头文件 ## 条款49:学习破解有关STL的编译器诊断信息 string不是一个类,它是typedef。实际上,它是这个的typedef: ``` basic_string<char, char_traits<char>, allocator<char> > `` ## 条款50:让你自己熟悉有关STL的网站 * SGI STL网站,http://www.sgi.com/tech/stl/。 * STLport网站,http://www.stlport.org/。 * Boost网站,http://www.boost.org/

0
《Effective STL中文版》的全部笔记 5篇
豆瓣
免费下载 iOS / Android 版客户端