[关闭]
@zhengyuhong 2014-09-27T08:36:38.000000Z 字数 5003 阅读 1299

Effective STL

C++ STL 读书笔记

第一章、容器

第1条：慎重选择容器类型

第4条：调用empty而不是检查size()是否为0

empty对所有标准容器都是常数时间操作，而对一些list，size耗费线性时间
那为什么list增减结点时不同时更新size呢？这是因为如果每一次增减结点都更新size，这样会耗费很多无用功，增减一两个结点还是挺容易更新size，但是增减一个子链表，只知道头尾，那么还是需要遍历一下数一下，还是需要线性时间。所以干脆当需要size时才遍历。

第5条：区间成员函数优先于与之对应的单元素成员函数

　　区间成员函数是指像STL算法一样，使用两个迭代器参数确定该成员操作所执行的区间，尽量避免写循环赋值（assignment）。
　　区间创建：所有标准容器都提供了如下形式的构造函数：
　　container::container(InputIterator begin, InputIterator end);
　　区间插入：所有标准的序列容器都提供了如下形式的insert：
　　void container::insert(iterator position, InputIterator begin, InputIterator end);
关联容器则是利用比较函数来决定插入位置，可以省略上述的position参数
　　void container::insert(InputIterator begin, InputIterator end);
　　区间删除：所有标准的容器都提供了区间形式的删除操作，但对于序列和关联容器，其返回值不一样。
　　序列容器提供：
iterator container::erase(iterator begin, iterator end);
　　关联容器提供：
void container::erase(iterator begin, iterator end);
关于insert的效率分析与erase类似，对于单元素调用erase的反复调用比对区间erase的单次调用要导致更多的位置移动，区间的erase可以统计好需移动的次数，一次性移动到最终位置
　　区间赋值：void container::assign(InputIterator begin, InputIterator end);//本质是先clear原容器，再赋值，赋值之后大小等于区间长度

第9条：慎重选择删除元素的方法

　　假如有container c;想删除c中值为1的元素，令人惊讶的是，完成这一任务的方式随容器类型而异，没有对所有容器类型都适用的方式
　　如果用户有一个连续内存的容器，vector、deque、string，那么最好的删除方式用erase-remove
c.erase(remove(c.begin(),c.end(),1),c.end());
注意remove仅仅是把要删除的元素用后面的元素覆盖了，譬如

  1. #include <vector>
  2. #include <algorithm>
  3. #include <iostream>
  5. using std::cout;
  6. using std::endl;
  7. using std::vector;
  8. int main(){
  9.     int a[] = {1,2,3,0,0,0,4,5,0,0,0,6,7,8};
  10.     vector<int> vec(a,a+14);
  11.     remove(vec.begin(),vec.end(),0);
  12.     for(int i = 0; i < vec.size(); ++i){
  13.         cout<<vec.at(i)<<" ";
  14.     }
  15.     cout<<vec.size();
  16.     return 0;
  17. }

输出是
1,2,3,4,5,6,7,8,0,0,0,6,7,8
14
　　remove算法并不会真正删除容器中的元素。他的任务是负责把区间内的元素值为指定值的元素的位置腾出，然后后面的元素就会往前移动。返回一个新的end()，即为原来的区间移除指定值并且元素前移后的末尾的下一个位置。但是原来容器的end()并不会改变。如果要真正删除元素，那么要使用erase了
　　list的成员函数remove则是真正删除了元素。所以这个remove真的比较奇怪，不知道STL为何如此设计。
　　对于关联容器，删除特定元素的正确办法是调用erase，需要对数时间开销：
　　c.erase(0);
关联容器执行了erase(iter)，迭代器iter失效了，再通过++iter,iter++都已经无法迭代到下一个位置，所以得预先存储好下一个迭代位置，然后再执行erase(iter)，可以通过调用时对迭代器自增迭代到下一个位置，传入当前迭代器位置，erase(iter++)
　　总结：
　　要删除有特定值的所有对象：
　　如果是vector、string、deque则使用erase-remove
　　如果是list，直接使用list的remove成员函数
　　如果是标准关联容器，则使用成员函数erase(key),注意关联容器有三个erase成员函数，

  1.     void erase ( iterator position );
  2.     size_type erase ( const key_type& x );
  3.     void erase ( iterator first, iterator last );
如果删除满足特定表达式的所有对象：
如果是vector、string、deque则使用erase-remove_if
如果是list，直接使用list的remove_if成员函数
如果是标准关联容器，写一个循环遍历容器中元素，把符合表达式的erase(iter);注意小心迭代器失效

第二章、vector、string

第13条：vector、string优先于动态分配的数组

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

reserve成员函数能告诉你把重新分配的次数减少到最低限度，从而避免重新分配与指针迭代失效带来的开销。

  1. size()告诉你容器中有多少元素。它没有告诉你容器为它容纳的元素分配了多少内存。
  2. capacity()告诉你容器在它已经分配的内存中可以容纳多少元素。那是容器在那块内存中总共可以容纳多少元素，而不是还可以容纳多少元素。如果你想知道一个vector或string中有多少没有被占用的内存，你必须从capacity()中减去size()。如果size和capacity返回同样的值，容器中就没有剩余空间了，而下一次插入（通过insert或push_back等）会引发上面的重新分配步骤。
  3. resize(Container::size_type n)强制把容器改为容纳n个元素。调用resize之后，size将会返回n。如果n小于当前大小，容器尾部的元素会被销毁。如果n大于当前大小，新默认构造的元素会添加到容器尾部。如果n大于当前容量，在元素加入之前会发生重新分配。
  4. reserve(Container::size_type n)强制容器把它的容量改为至少n，提供的n不小于当前大小。这一般强迫进行一次重新分配，因为容量需要增加。（如果n小于当前容量，vector忽略它，这个调用什么都不做)

第15条：注意string实现的多样性

第17条：使用swap技巧除去多余容量

其实这就是copy-swap技术

  1. vector<int> tmp(c);
  2. tmp.swap(c);
  3. string temp(str);
  4. temp.swap(str);

如此就可以把c、str的容量收缩了

第18条：避免使用vector

因为它为了节省内存，采用了位图的方法，譬如使用8bit就能表示有8个bool元素的vector数组，当用C语言的接口时，会发现这样子是不行的，譬如

  1. vector<bool> flag；
  2. &flag[0] = 1;
  3. &flag[1] = 1;

会产生越界情况。

第三章、关联容器

第19条：理解相等于等价的区别

第20条：为包含指针的关联容器指定比较类型

第21条：总是让比较函数在等值情况下返回false

先针对<=来说，关联容器中的等价比较不是使用==，而是使用
!(A<=B)&&!(B<=A)，就是都不满足非等价时才是等价
而对于<就更加直接了明显是
!(A 所以对于定义关联容器的比较函数时，当两个值等值的情况下，返回false；

第22条：切勿直接修改set或者multiset中的键

　　关联容器中里面的元素按照一定的顺序排列，如果随意修改关联容器元素的值，那么打破了有序性，关联容器就会失效了，所以不能随便修改关联容器。
对于map，multimap来说，比较简单，因为它们是按照键（key）来排序的，所以可以修改它的值value,如果需要修改键的话，就是先erase，再插入新的键值对。倘若执意修改键

  1. map<int,string> m;
  2. m.insert(pair<int,string>(1,"1"));
  3. m->first()-first = 0;//错误，因为key有const声明限定了

　　那么set、multiset能不能能不能设置为const，不能
　　譬如set s；如果类型用const限定的话，那么就不能修改Employee当中的除了键的变量，因为是按照键来排序的嘛，所以只要不修改键，那么修改其他就不会影响排序了，所以不能使用const来限定类型。于是乎，键可以被修改，这时候一旦键被修改，编译器没有报错，但是关联容器就失效了，不再维持有序性。

第24条：当效率至关重要时，请在map::operator[]与map::insert之间慎重做出选择

  1. p<K,V> m;
  2. m[k] = v;//检查k是否在map中了，没有就添加k，v键值对，有就更新k的值为v

第四章、迭代器

第26条：超特rat而优先于const_iterator、reverse_iterator及const_reverse_iterator

第五章、算法

第31条：了解各种与排序有关的选择

全局排序

  1. template <class RandomAccessIterator>
  2.   void sort ( RandomAccessIterator first, RandomAccessIterator last );
  4. template <class RandomAccessIterator, class Compare>
  5.   void sort ( RandomAccessIterator first, RandomAccessIterator last, Compare comp );

部分排序

  1. template <class RandomAccessIterator>
  2.   void partial_sort ( RandomAccessIterator first, RandomAccessIterator middle,
  3.                       RandomAccessIterator last );
  5. template <class RandomAccessIterator, class Compare>
  6.   void partial_sort ( RandomAccessIterator first, RandomAccessIterator middle,
  7.                       RandomAccessIterator last, Compare comp );

最好的middle在前面有序排列，后面的就无序

排序一个区间

  1. template <class RandomAccessIterator>
  2.   void nth_element ( RandomAccessIterator first, RandomAccessIterator nth,
  3.                      RandomAccessIterator last );
  5. template <class RandomAccessIterator, class Comapre>
  6.   void nth_element ( RandomAccessIterator first, RandomAccessIterator nth,
  7.                      RandomAccessIterator last, Compare comp );

仅仅把最好的n个放在前n个位置，但是前n个位置是无序的。

第32条：如果确实需要删除元素，则需要再remove这一类算法之后调用erase

第六章、函数子、含数字类、函数及其他

下面仅是个人记忆一下

  1. class functor{
  2. public:
  3.     return_type operator()(classType arg){
  4.         ...
  5.         return returnValue;
  6.     }
  7. };
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注