【C++】Effective STL：50条有效使用STL的经验

大家好，欢迎来到IT知识分享网。

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

1、C++容器：先混个眼熟

2、C++容器：简介

2.1 序列容器

序列容器实现了可以顺序访问的数据结构。

2.2 有序关联容器

关联容器实现可以快速搜索的排序数据结构（O（log n）复杂度）。

set：只有键，没有值的集合，按键排序，并且键是唯一的；
map：键值对的集合，按键排序，并且键是唯一的；
multiset：只有键，没有值的集合，按键排序，键可以不唯一；
multimap：键值对的集合，按键排序，键可以不唯一；

2.3 无序关联容器

无序关联容器实现了可以快速搜索的未排序（哈希）数据结构（O（1）最好，O（n）最坏情况的复杂性）。

unordered_set：只有键，没有值的集合，按键哈希散列，并且键是唯一的；
unordered_map：键值对的集合，按键哈希散列，并且键是唯一的；
unordered_multiset：只有键，没有值的集合，按键哈希散列，键可以不唯一；
unordered_multimap：键值对的集合，按键哈希散列，键可以不唯一；

2.4容器适配器

3、选择容器

第二条：不要试图编写独立于容器类型的代码

1、禁止对容器进一步泛化

每一种容器是针对一类场景的泛化，不要试图进一步泛化容器。比如：针对当下场景使用vector容器，写代码时就围绕vector接口来写，不要试图写出能够兼容list、deque的代码。虽然这么做出发点是好的，但是最终总是误入歧途。

2、建议封装容器到类中

要想减少再替换容器类型时所需要修改的代码，可以把容器隐藏到一个类中，并尽量减少与容器相关的外部可见的接口。

第三条：确保容器中的对象拷贝正确而高效

1、使用智能指针

使拷贝动作高效、正确，并防止剥离问题发生的一个简单办法是使容器包含指针而不是对象，最佳选择是使用智能指针。

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

理由很的简单：empty对所有的标准容器都是常数时间操作，而对一些list实现，size耗时线性增长。

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

1、区间成员函数

区间成员函数像STL算法一样，使用两个迭代器参数来确定该成员操作所执行的区间。

2、区间成员函数的优点

代码量少、表达清晰直接，易写易懂。

3、何时使用区间成员函数

第六条：当心C++编译器最烦人的分析机制

第七条：如果容器中包含了通过new操作创建的指针，切记在容器对象析构前将指针delete掉

STL容器很智能，但没有智能到知道是否该删除自己所包含的指针所指向的空间。为了避免内存泄漏，建议使用引用计数形式的智能指针对象。

第八条：切勿创建包含auto_ptr的容器对象

不多说了，很多年以前就不再使用auto_ptr了。

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

1、删除特定值

2、删除满足特定条件的对象

第十条：了解分配子（allocator）的约定和限制

第十一条：理解自定义分配子的合理用法

第十二条：切勿对STL容器的线程安全性有不切实际的依赖

第十三条：vector和string优先于动态分配的数组

不解释了，直接照做就是了。

第十四条：使用reserver来避免不必要的重新分配

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

不同的string实现以不同的方式来组织下列信息：字符串的大小、容量capacity、字符串的值、对值的引用计数。

第十六条：了解如果把vector和string数据传给旧的API

vector返回C API：

vector<int> v; if(!v.empty()){ 
    doSomething(&v[0], v.size()); } 

注意：不要用v.begin()代替&v[0]

string返回C API：s.c_str();

第十七条：使用“swap技巧”除去多余的容量

class Contestant{ 
   ... ...}; vector<Contestant> contestants; ... ... vector<Contestant>(contestants).swap(contestants); 

string s; ... ... string(s).swap(s); 

第十八条：避免使用vector

代替方法：

deque<bool> 或者使用bitset 

第十九条：理解相等（equality）和等价（equivalence）的区别

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

struct DereferenceLess { 
    tumplate<typename PtrType> bool operator()(PtrType pT1, PtyType pT2) const { 
    return *pT1 < *pT2; } } 

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

第二十二条：切勿直接修改set或multiset的值

所有的标准关联容器是按照一定顺序来存放的，如果修改了会打破容器的有序性。

第二十三条：考虑用排序的vector替代关联容器

如果元素少并且几乎不会有插入删除操作，可以考虑使用排序的vector替代关联容器，无论是空间还是时间都是最优的。

第二十四条：当效率至关重要时，请在map::operator[]和map::insert之间谨慎做出选择

第二十五条：熟悉非标准的散列表

第二十六条：iterator优先于const_iterator、reverse_iterator及const_reverse_iterator。

第二十七条：使用distance和advance将容器的const_iterator转换成iterator

typedef deque<int> IntDeque; typedef IntDeque::iterator Iter; typedef IntDeque::const_iterator ConstIter; IntDeque d; ConstIter ci; ... Iter i(d.begin()); /迭代器 i 指向容器 d 起始位置 advance(i, distance<ConstIter>(i, ci)); /注意这里指明distance所使用的类型为ConstIter 

效率问题：对于随机访问的迭代器（如vector、string、deque产生的迭代器）而言，执行时间是常数时间；对于其他标准容器以及散列表的迭代器而言，执行时间是一个线性时间，因此推荐二十六条，尽量用iterator代替const_iterator

第二十八条：正确理解由reverse_iterator的base()成员函数所产生的iterator的用法

第二十九条：对于逐个字符的输入请考虑使用istreambuf_iterator

ifstream inputFile("test.txt"); string fileData((istreambuf_iterator<char>(inputFile)), istreambuf_iterator<char>()); 

第三十条：确保目标区间足够大

第三十一条：了解各种与排序有关的选择

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

vector<int> v; ... v.erase(remove(v.begin(), v.end(), 99), v.end()); 

同理unique也需要和erase配合使用。

注意：list::remove会真正删除元素，并且比使用erase-remove配合使用更高效，list::unique也会真正删除元素。

第三十三条：对包含指针的容器使用remove这一类算法时要特别小心

第三十四条：了解哪些算法要求使用排序的区间作为参数

需要排序后才能使用的算法：

// 使用二分法查找的算法，需要先排序 binary_search lower_bound upper_bound equal_range // 集合操作，为了提高效率（为了保证线性时间效率），需要先排序 set_union set_intersection set_defference set_symmetric_defference // 合并操作，为了提高效率 merge inplace_merge // 判断一个区间中的所有的对象是否都在另一个区间中，为了提高效率 includes 

第三十五条：通过mismatch或lexicographical_compace实现简单的忽略大小写的字符串比较

略

第三十六条：理解copy_if算法的正确实现

STL中包含copy的算法

copy copy_backward replace_copy replace_copy_if reverse_copy unique_copy remove_copy remove_copy_if rotate_copy partial_sort_copy uninitialized_copy 

但是就是没有copy_if算法，需要自己实现

template<typename InputIterator, 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; } 

第三十七条：使用accumulate或者for_each进行区间统计

accumulate：对区间进行自定义的操作，比如计算一个容器中字符串长度的总和。

/计算和 list<double> ld; ... double sum = accumulate(ld.begin(), ld.end(), 0.0); / 计算容器中字符串长度的总和 string::size_type stringLengthSum(string::size_type sumSoFar , const string& s) { 
    return sumSoFar + s.size(); } set<string> ss; ...//插入一些字符串 string::size_type lengthSum = accumulate(ss.begin(), ss.end(), static_cast<string::size_type>(0), stringLengthSum); }; 

第三十八：遵循按值传递的原则来设计函数子类

第三十九：确保判别式是“纯函数”。

第四十条：若一个类是函数类，则应使它可配接

第四十一条：理解ptr_fun、mem_fun和mem_fun_ref的来由

STL算法只支持非成员函数，不支持成员函数（无法通过编译），如果要使用成员函数需要使用ptr_fun、mem_fun或者mem_fun_ref来将成员函数封装到一个函数类中

第四十二条：确保less与operator<具有相同的语义

第四十三条：算法调用优先于手写的循环

class Widget{ 
    public: ... void redraw() const; ... } 

使用手写循环来重画容器list中的所有的Widget：

list<Widget> lw; ... for (list<Widget>::iterator i=iw.begin(); i!=iw.end(); ++i){ 
    i->redraw(); } 

使用for_each循环算法来完成

for_each(lw.begin(), lw.end()), mem_fun_ref(&Widget::redray)); 

mem_fun_ref：封装成员函数，使它可以用在算法中，因为算法只能使用非成员函数

第四十四条：容器的成员函数优先于同名的算法

第四十五条：正确区分count、find、binary_search、lower_bound、upper_bound和equal_range

第四十六条：考虑使用函数对象而不是函数作为STL算法的参数

第四十七条：避免产生“直写型”(wirte-only)的代码

第四十八条：总是包含（#include）正确的头文件

第四十九条：学会分析与STL相关的编译器诊断信息

第五十条：熟悉与STL相关的web站点