Aug 21

Effective STL学习记录小整理 不指定

felix021 @ 2008-8-21 01:02 [IT » 程序设计] 评论(0) , 引用(0) , 阅读(4105) | Via 本站原创 | |
这些天花了不少时间看STL,当然也少不了看《Effective STL》这本书。
这本书讲了很多内容,我只记下了对于初学者比较容易理解和需要记住的一些重要条款:

条款4:用empty()来代替检查size()是否为0
因为size()可能需要O(n)的时间,但是empty()只需要O(1)

条款5:尽量使用区间成员函数代替它们的单元素兄弟
对于插入已知数量或已知区间的元素,使用区间版的成员函数效率高。
比如vt.insert(a, a+100000)效率将显然高于for(i=0;i<100000;i++)vt.insert(a[i]);
因为后者需要反复调用insert()并可能多次重新分配空间

条款7:当使用new得指针的容器时,记得在销毁容器前delete那些指针
容器被删除的时候指针被删除,但是指针指向的内存空间并不会被释放

条款17:使用“交换技巧”来修整过剩容量
注意!在vector里面删除元素的时候,多余的空间不会自动释放
vector<type>(vt).swap(vt);
释放vt占用的多余容量
vector<type>().swap(vt);
清空vt并释放其占用的容量

条款19:了解相等和等价的区别
相等:基于operator==,xy相等即x==y
等价:基于operator<,xy等价是!(x<y) && !(y<x),这是所有排序和插入时执行的比较!
等价是基于在一个有序区间中对象值的相对位置。等价一般在每种标准关联容器(比如,set、multiset、map和multimap)的一部分——排序顺序方面有意义。两个对象x和y如果在关联容器c的排序顺序中没有哪个排在另一个之前,那么它们关于c使用的排序顺序有等价的值。所以要遵循条款21——

条款21: 永远让比较函数对相等的值返回false
比如对于下面这个node类型的结构体
struct node{
  int i;
  bool operator<(const node &b)const{return i <= b.i}
};
如果结构体a和b的i值都为10,那么插入set或map的时候,根据等价的判断方式(!(a<b) && !(b<a)),10和10是不相等的——这样会破坏set和map,使得他们无法再正确运行,同样对于multiset和multimap,find函数也无法返回正确的迭代器了。从技术上说,用于排序关联容器的比较函数必须在它们所比较的对象上定义一个“严格的弱序化(strict weak ordering)”。(传给sort等算法的比较函数也有同样的限制)。

条款22:避免原地修改set和multiset的键
set和multiset保持它们的元素有序,这些容器的正确行为依赖于它们保持有序。 如果你改了关联容器里的一个元素的值(例如,把10变为1000),新值可能不在正确的位置,而且那将破坏容器的有序性。
->对于map和multimap,标准规定不允许修改,所以试图修改的函数可能会被提示编译错误,最安全的解决办法是删除这个元素,再插入一个新的pair

条款24:当关乎效率时应该在map::operator[]和map-insert之间仔细选择
给定 {map<K, V>m;},这个表达式--{m[k] = v;} 检查键k是否已经在map里。如果不,就添加上,以v作为它的对应值。如果k已经在map里,它的关联值被更新成v。出于对效率的考虑,当给map添加一个元素时,我们断定insert比operator[]好;而从效率和美学考虑,当更新已经在map里的元素值时operator[]更好。

条款31:了解你的排序选择
sort() 完全的nlogn的不稳定排序(随机化快速排序)
stable_sort() 完全的nlog的稳定排序(归并,效率稍低)
partial_sort() 部分排序,使得满足某顺序判断条件的前多少个元素有序地排在区间前面(不稳定)
nth_element() 分区,使得大于满足某顺序判断条件的前多少个元素(不一定有序)排在区间前面(不稳定),位置为n的元素是序列中按此顺序判断排列后的第n个元素。

条款32:如果你真的想删除东西的话就在类似remove的算法后接上erase
remove(begin, end)只是把后面的元素覆盖到前面,并不真正删除最后多余的元素(无法使得容器的end()所返回迭代器产生的变化,具体做了什么,参见本条款),它只是将begin, end之间的元素排出移除他们后得到的有效的区间,然后返回有效区间的结尾,同样的是remove_if(begin, end, testfunc)和unique(begin, end)。所以将remove/remove_if/unique放在erase(begin, end)的begin位置,就能保证容器删除多余的元素并正确重置其end()返回迭代器(否则还是指向原先的位置,因为元素并未被删除)。
比如vector<int>vt;
vt.erase(remove(vt.begin(), vt.begin()+6), vt.end());
vt.erase(remove_if(vt.begin(), vt.end(), testfunc), vt.end());
vt.erase(unique(vt.begin(), vt.end()), vt.end());

条款33:提防在指针的容器上使用类似remove的算法
因为remove会产生覆盖,如果你不事先将指针指向的内存删除,那么就会造成内存泄露。

条款34:注意哪个算法需要有序区间
对于非有序区间,调用以下函数一般无法得到你想要的结果
binary_search //二分查找
lower_bound  //下界
upper_bound //上界
equal_range //同时查找下届和上界
set_union  //集合的并
set_intersection //集合的交
set_difference //集合的差
set_symmetric_difference //集合的对称差
merge //有序区间的合并
unique //对于连续的重复元素只保留一个

条款43:尽量用算法调用代替手写循环
有三个理由:
效率:算法通常比程序员产生的循环更高效。
正确性:写循环时比调用算法更容易产生错误。
可维护性:算法通常使代码比相应的显式循环更干净、更直观。

条款44:尽量用成员函数代替同名的算法
有些容器拥有和STL算法同名的成员函数。关联容器提供了count、find、lower_bound、upper_bound和equal_range,而list提供了remove、remove_if、unique、sort、merge和reverse。大多数情况下,你应该用成员函数代替算法。这样做有两个理由。首先,成员函数更快。其次,比起算法来,它们与容器结合得更好(尤其是关联容器)。

条款45:注意count、find、binary_search、lower_bound、upper_bound和equal_range的区别
--->建议详读.
count() 返回值等于指定值的元素的个数,O(n)
  count回答的问题是:“是否存在这个值,如果有,那么存在几份拷贝?”
find() 返回第一个值等于指定值的元素的迭代器,如果没找到就返回end
  find回答的问题是:“是否存在,如果有,那么它在哪儿?”
binary_search() 测试在有序区间中是否存在一个指定值,返回bool类型
  binary_search回答这个问题:“它在吗?”它的回答只能是是或者否。
lower_bound() 返回第一个出现这个值的元素的迭代器(如果找到的话)到可以插入这个值的位置(如果没找到)。
  lower_bound回答这个问题:“它在吗?如果是,第一个拷贝在哪里?如果不是,它将在哪里?”
upper_bound() 返回最后一次出现这个值的元素之后的位置。
  lower_bound回答这个问题:“不管现在有没有和它相等的元素,在保证区间有序的情况下,我要尽可能把它插入到最靠后的位置,这个位置在哪里?”
equal_range() 返回一对迭代器,等于lower_bound返回的迭代器和upper_bound返回的迭代器。对于equal_range的返回值,有两个重要的地方。第一,如果这两个迭代器相同,就意味着对象的区间是空的;这个只没有找到;第二个要注意的是equal_range返回的东西是两个迭代器,对它们作distance就等于区间中对象的数:distance(p.first, p.second)




欢迎扫码关注:




转载请注明出自 ,如是转载文则注明原出处,谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php
Tags: ,
发表评论
表情
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
打开HTML
打开UBB
打开表情
隐藏
记住我
昵称   密码   *非必须
网址   电邮   [注册]