本文发自 http://www.binss.me/blog/my-excerpt-of-effective-stl/,转载请注明出处。

接下来是看《Effective STL》。依然还是受益匪浅,然而也有许多未理解之处,期望日后第二遍时有更深入的理解。

以下是读书过程中的摘录和体会:

引言

凡是涉及指针容器的的设计几乎无一例外地会用到引用计数。

所有重载了operator ()的类都是函数子类(functor class)。从这些类创建的对象被称为函数对象或函数子,因为它们可以像函数那样被调用。

模版的嵌套从属类型前需要加typename(避免被当作静态成员)。

第一章 容器

1 慎重选择容器类型

标准序列容器:vector、string、deque、list

标准关联容器:set、multiset、map、multimap

非标准序列容器:slist(单向列表)、rope(重型string)

非标准关联容器:hash_set、hash_multiset、hash_map、hash_multimap

非STL容器:数组、bitset、valarray、stack、queue、priority_queue

连续内存的容器:vector、deque、string、rope

基于节点的容器:list、slist、标准关联容器、散列容器

在任意位置插入新元素:序列容器

元素无序:散列容器

随机访问迭代器:vector、deque、string、rope

避免插入删除时移动元素:别使用连续内存容器

数据布局和C兼容:vector

关注查找速度:散列容器->排序的vector->标准关联容器

避免引用计数:别使用string、rope

可回滚:基于节点的容器。只有list支持多个元素操作的回滚。

避免迭代器、指针、引用无效:基于节点的容器

迭代器随机访问,若没有删除且插入只发生在容器末尾,则指针和引用不会失效(但迭代器可能会失效):deque

2 不要试图编写独立于容器类型的代码

不要妄想更换容器后代码无须改变:

  • 专有操作:比如序列容器才支持push_front和push_back,关联容器才支持count和lower_bound

  • 操作因容器不同而不同:如insert和erase

  • 只能使用功能的交集而无法使用特性

  • 迭代器、指针、引用失效时机不同

为了方便日后更换容器(或分配子)、缩短类型名称的长度,可以用typedef为容器和其迭代器定别名。

为了避免容器暴露,还可以用类对容器进行封住。

3 确保容器中的对象副本正确而高效

对象存入容器中时会被复制,被取出时会被复制(copy in, copy out)。在进行排序等操作时,容器中的对象也会被复制(移动)。

不要将子类元素放入基类容器中,不仅不能利用虚特性,还导致对象被切割。

为了高效,可以考虑智能指针。

STL仅在需要时才创建对象,比数组聪明的多。

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

empty对所有的标准容器都耗费常数时间,而对于一些list实现,size耗费线性时间。

这些list实现追求让操作(如splice)耗费常数时间,不维护链表的大小,而是直到调用size()时才进行计算。

否则,splice操作为了计算所链接的元素个数,需要耗费线性时间。

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

简单来说,能一次拷多个的就不要一个个拷,因为一个个拷效率低。也不要用alogirithm的copy+插入迭代器来拷,因为copy往往不能准确地表达语义,并且效率和一个个拷差不多。

注:copy的原型:

template<class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator _First, InputIterator _Last, OutputIterator _DestBeg);

区间函数列表:

区间创建:container::container(InputIterator begin, InputIterator end);

区间插入:序列容器:void container::insert(iterator position, InputIterator begin, InputIterator end);

     关联容器:void container::insert(InputIterator begin, InputIterator end);

区间删除:序列容器:iterator container::erase(iterator begin, iterator end);

     关联容器:void container::erase(iterator begin, iterator end);

区间赋值:void container::assign(InputIterator begin, InputIterator end);

区间成员函数的优势:

  • 意图清晰

  • 代码精简

  • 效率更高

假设容器中有n个元素,现新插入k个元素。

减少了不必要的函数调用:区间成员函数只需调用一次;而单元素成员函数要调用k次。

减少了容器中元素的移动开销:区间成员函数只需移动一次,带来n次赋值操作符函数的调用和k次复制构造函数的调用的开销;而单元素成员函数要移动k次,带来( n-1)*k次赋值操作符函数的调用和k次复制构造函数的调用的开销。

减少了容器扩展开销:基于连续内存的容器在容量不足进行扩展时会将容量加倍,区间成员函数能够一次到位;而单元素成员函数要扩展log2(k)次。

基于节点的容器虽然没有移动和扩展开销,但相应的,会带来2*(k-1)次不必要的节点next和prev指针赋值开销。

6 当心C++编译器最烦人的分析机制

C++会尽可能地解释为函数声明而非对象声明。

list data(istream_iterator(dataFile), istream_iterator()); 会被解析成一个data函数。

为了避免,只能使用命名的迭代器:

istream_iterator dataBegin(dataFile);

istream_iterator dataEnd;

list data(dataBegin, dataEnd);

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

使用智能指针容器(容器中的对象为智能指针,且要求为引用计数形式的,如std::shared_ptr),保证容器中new出来的资源总能被释放。

template <class InputIterator, class Function>
Function for_each (InputIterator first, InputIterator last, Function f);

8 切勿创建包含auto_ptr的容器对象

复制auto_ptr时,它所指对象的所有权会移交给新的指针。这样在容器中会导致严重后果:

对于vector sort()的一种实现——快排,在选轴(pivot)时会把对象的所有权转移到临时变量(pivot用于比较),然后临时变量在sort()结束时被释放,导致vector中的智能指针丢失对象(变为NULL)。

注:auto_ptr已在C++11中废弃。

http://stackoverflow.com/questions/3697686/why-is-auto-ptr-being-deprecated

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

没有对所有容器都适用的删除元素方法。

基于连续内存的容器:采用erase-remove

c.erase(remove(c.begin(), c.end(), deleteValue), c.end());
c.erase(remove_if(c.begin(), c.end(), deleteValuePredicate), c.end())

list:

c.remove(deleteValue);
c.remove_if(deleteValuePredicate);

for(Container<ValueType>::i=c.begin(); i != c.end();)
{
    if(deleteValuePredicate(*i))
    {
        i = c.erase(i);
    }
    else
    {
        ++i;
    }
}

标准关联容器:

c.erase(deleteValue);
for(Container<ValueType>::i=c.begin(); i != c.end();)
{
    if(deleteValuePredicate(*i))
    {
        c.erase(i++);
    }
    else
    {
        ++i;
    }
}

10 了解分配子(allocator)的约定和限制

STL内存分配子是一个模版,用于分配和释放原始内存。

声明:

template<typename T>
{
public:
    pointer allocate(size_type numOjbects, const void *localityHint=0);
    void deallocate(pointer ptrToMemory, size_type numOjbects);
    ...
};

模版参数T代表其分配内存对象的类型。它应该提供类型定义pointer(T*)和reference(T&)。

对于pointer(T *),即使T对象未进行构造,但是却返回了一个T的指针。STL期望调用者会在返回内存中构造T对象,然而在reserve情况下可能并不会发生构造。

C++标准允许STL的实现假定同一类型的分配子是等价的,因此可移植的分配子都不能拥有非静态的数据成员。

标准容器依赖于rebind模版,因此分配子必须提供rebind模版。

11 理解自定义分配子的合理用法

如果STL默认的分配子有新要求,可以自定义分配子,然后在构造容器时作为第二个模版参数传入。如:

vector<double, SharedMemoryAllocator<double>> SharedDoubleVec;

注意同类型的分配子必须等价。

主要需求:

  • 使用共享内存

  • 将不同容器的对象放置于不同的堆

12 切勿对STL容器的线程安全性有不切实际的依赖

STL标准只能保证:

  • 多个线程读是安全的

*多个线程对不同容器的写是安全的

为了实现线程安全,在容器的成员函数调用结束前、容器返回的迭代器生存期结束前、作用于容器的算法结束前,都要锁住容器。

有时还需要对多行代码进行同时加锁,STL很难推断出来。

加锁开销大,如果STL都加锁,对无须线程安全的用户不公平。

应该通过加锁类来创建容器,这样锁在容器作用域结束时随着析构自动释放。为了使加锁类发挥作用,创建新的代码块来括住要加锁的代码。

第二章 vector和string

13 vector和string优先于动态分配的数组

使用new需要确保:必须调用且只能调用一次delete(否则会资源泄漏),且delete形式正确(delete还是delete[])

vector和string消除了这些负担,且提供了begin、end、size这些方便的函数以及迭代器。因此考虑用vector和string来替代new T[...]。

string一般实现为引用计数,如果用于多线程环境,可以考虑用vector取代。

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

每当vector和string需要更多空间时,就会执行以下步骤:

  1. 分配一块大小为当前容量n倍的内存(一般n为2)

  2. 将原容器的内荣从旧内存拷贝到新的内存中

  3. 析构旧内存中的对象

  4. 释放旧内存

为了避免频繁的重新分配,可以通过reserve(Container::size_type n)来扩大容器容量。

这种做法适用于预先能估算容器元素数量的情况;也可以先预留,在元素加入完后再去除多余容量。

15 注意string实现的多样性

一般来说,string的实现包含以下信息:字符串的大小、容量、字符串的值。还可能包含分配子的一个副本、值的引用计数等。

实现一

包含字符串的大小、容量、和分配子的副本,还有一个指向动态分配内存的指针,内存中包含引用计数和字符串值。

实现二

只包含指向struct的指针。struct包含了字符串的大小、容量、引用计数、指向值的指针,以及同步控制相关的其它数据。

实现三

同实现二,只不过指针指向了一块动态分配的内存。不支持针对单个对象的分配子。

实现四

内部包含一块内存,可以容纳15个字符(小字符串优化)。当字符串大小超过15时,内存的起始部分被替换为指向动态分配内存的指针,指向字符串的值。

为了有效使用STL,应该了解string的实现。

16 了解如何把vector和sting数据传给旧API

vector中的元素存储在连续的内存中,所以能过直接把vector传给接受数组参数的API:

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

利用数组来初始化vector:

size_t fillArray(double * pArray, size_t arraySize);
vector<double> vd(maxNumDoubles);
vd.resize(fillArray(&vd[0], vd.size()));

fillArray用于向vector中写入double元素,并返回写入成功的个数。

因为只有vector有这种特性,可以让其作为容器和C API之间的中介,如:

传set参数:

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

初始化list:

list<double> l(vd.begin(), vd.end());

注意:通常(非排序)可以修改vector中的元素,但不能增加或删除vector中的元素。

17 使用swap技巧除去多余的容量

容器容量只会自动增加,不会自动减少。通过swap可以缩简容量:

vector<Contestant>(contestants).swap(contestants);

vector(contestants)会调用拷贝构造函数创建出临时对象,而拷贝复制函数只会为存在的元素分配内存,因此临时容器对象没有多余容量。然后通过swap交换两者的内容(当然迭代器、指针、引用也会被交换),于是原本容器中的内存随着临时变量的析构而释放了。

swap也可以用来清空容器:

vector<Contestant>().swap(contestants);

18 避免使用vector

vector并不存储bool,它无法完全满足STL容器的需求,不是一个STL容器。它是通过bitfield来实现的,用一个bit代表一个bool值,因此无法获取其中单独的一个元素对象。所以为了保持和其它容器行为上的一致,operator []返回代理而不是引用,导致对其返回值取址得到的不是一个bool指针,违反了STL的的要求。

可以使用deque和bitset(非STL)取代之。

第三章 关联容器

19 理解相等(equality)和等价(equivalence)的区别

相等:以operator ==为标准。只要operator ==返回true,不管内部是否相同,都表示相等。

等价:以"在排序的区间中对象值的相对顺序“为标准。

关联容器基于等价而非相等,始终使用判别式来排序、判断元素是否“相等”:

!c.key_comp()(x, y) && !c.key_comp()(y, x)

key_comp的默认实现为less,即“<“。可以自定义(通过函数子类)来实现:

struct StringCompare: public binary_function<string, string, bool>
{
    bool operator()(const string& lhs, const string& rhs) const
    {
        return my_compare(lhs, rhs);
    }
};

并作为第二个模版参数传入:

set<string, StringCompare> my_set;

注:set的声明:

template <class Key, class Compare = less<Key>, class Allocator = allocator<Key> >
    class set;

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

关联容器存放指针时,要想其按照内容排序(而不是按指针排序),应该自己实现比较函数子类(见19),并作为第二个模版参数传入。

为了方便,可以创建比较函数子类模版:

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

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

在自定义比较函数子类时,可能导致在等值情况下比较函数子返回true(如>=),于是集合允许两个等值的元素插入到容器中(判断为不等价),违反了标准关联容器(如set等)的定义。

对关联容器排序的比较函数必须为它们所比较的元素定义一个“严格的弱序化”,其中一个要求就是:总是在比较等值的两个元素的时候返回false。

22 切勿直接修改set或multiset中的键

对于map和multimap,其中的元素类型为pair,所以键无法被修改。而set或multiset中的元素类型却是T而不是const T,因为元素的某些成员需要能够被修改。因此需要保证元素的键成员不要被修改,因为它们影响了容器的有序性。

在某些实现中,set或multiset中的元素不允许被修改。不要使用const_cast来去除const元素属性,因为在这种情况下键可能会被修改。

安全的修改步骤:

  1. 用迭代器找出要修改的容器元素

  2. 为该元素复制一份非const副本

  3. 修改该副本

  4. 把元素从容器中删除(erase)

  5. 把元素副本插入到容器中(insert,可以传入1的迭代器作为提示)

23 考虑用排序的vector替代关联容器

若对查找速度要求高,可以采用散列容器(几乎为常数时间的查找,视散列函数)。

若对容器操作行为规律(始终按照批量设置->批量查找),可以采用排序的vector。相比标准关联容器,避免了二叉树指针空间开销(占用过多的内存会导致换页,产生page fault),并且由于其节点散布在全部内存空间中,降低了引用局限性。查找时间都是log2n。

但是这种使用方法必须让vector保持有序,因此仅在操作行为规律,即始终按照批量设置->批量查找来时采用。

而由于标准关联容器通常被实现为平衡二叉树,更适合增删查操作混杂时使用。

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

map的operator []:先检查key是否在map中,如果是,返回其引用,如果否,构造一个新对象并返回它的引用。

在为map插入元素时,使用insert比operator[]后赋值效率高,因为可以直接调用构造函数而不是先调用默认构造函数再赋值。

但如果是修改元素,则operator[]效率更高,因为insert必须构造pair。

结合operator[]和insert的优点:

template<typename MapType, typename KeyArgType, typename ValueArgType>
typename MapTypee::iterator efficientAddOrUpdate(MapType& m, const KeyArgType& k, const ValueArgType& v)
{
    // lower_bound返回元素位置,如果元素不存在,则返回它应该在(插入到)什么位置
    typename MapType::iterator lb = m.lower_bound(k);
    if( lb != m.end() && !(m.key_comp()(k, lb->first)) )
    {
        lb->second = v;
        return lb;
    }
    else
    {
        typedef typename MapType::value_type MVT;
        return m.insert(lb, MVT(k,v));
    }
}

使用KeyArgType、而ValueArgType不是MapType::key_key、MapType::value_type,是为了避免对象因需要转换而被构造,在赋值情况下,直接调用类的operator = 赋值。

25 熟悉非标准的散列容器

STL没有散列容器。可以熟悉非标准版本的散列容器。 注:C++11引入散列容器std::unordered_map

第四章 迭代器

26 iterator优先于const_iterator、reverse_iterator以及const_reverse_iterator

STL为所有标准容器都提供了4种迭代器:

iterator:相当于T*

const_iterator:相当于const T*

reverse_iterator:相当于T*,从容器尾部反向遍历到头部

const_reverse_iterator:相当于const T*,从容器尾部反向遍历到头部

iterator是基类,const_iterator和reverse_iterator继承了iterator,const_reverse_iterator继承了const_iterator和reverse_iterator。

尽量使用iterator、避免混用的原因:

  1. 大部分版本的insert和erase函数要求使用iterator。

  2. 无法将const_iterator隐式转换为iterator

  3. 将reverse_iterator转换为iterator后摇经过调整才能用

27 使用distance和advance将容器的const_iterator转换成iterator

不存在从const_iterator到iterator的隐式转换,也无法通过const_cast进行强制类型转换(除了vector和string,因为它们的迭代器是指针)。

因此将容器的const_iterator转换成iterator的最好方法是复制一个:

Container::const_iterator ci;
...
Container d;
Container::iterator i(d.begin());
advance(i, distance<Container::const_iterator>(i, ci));

28 正确理解由reverse_iterator的base()成员函数所产生的iterator的用法

调用reverse_iterator的base()成员函数可以得到与之相对应的iterator,对于插入操作,可以直接用,而对于删除操作,reverse_iterator调用base()返回的是下一个位置,应该使用(++ri).base()。

29 对于逐个字符的输入请考虑使用istreambuf_iterator

使用istream_iterator来复制文本内容到string中,要清除输入流的skipws标志:

inputFile.unsetf(ios::skiwps);

但istream_iterator内部调用opertaor>>来进行格式化输入,带来了类型检查、异常检查等开销。

如果单纯进行逐字符拷贝,可以使用istreambuf_iterator,该迭代器只会简单地从流缓冲区中取出下一个字符。

相比来说,istreambuf_iterator比istream_iterator具有更优越的性能。

第五章 算法

30 确保目标足够大

transform:将一个容器中符合条件的元素复制到另外一个容器

使用transform算法时,因为默认进行的是替换型操作,必须确保目标容器相应的元素存在(即目标容器应该大于等于原容器,如果不够可以用resize调整)。

为了将transform的结果插入到目标容器尾端,需要传入back_inserter生成迭代器(需要容器支持push_back):

transform(values.begin(), values.end(), back_inserter(results), transmogrify);

同理,front_inserter能将transform的结果插入到目标容器前端(需要容器支持push_front)。

inserter则能过将结果插入到特定位置,如插入到中间:

transform(values.begin(), values.end(), inserter(results, result.begin() + result.size()/2), transmogrify);

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

完全排序:

template<class ForwardIt, class UnaryPredicate>
ForwardIt partition( ForwardIt first, ForwardIt last, UnaryPredicate p );

找到前n并排序:

template<class RandomIt, class Compare>
void partial_sort( RandomIt first, RandomIt middle, RandomIt last, Compare comp );

找到前n:

template<class RandomIt, class Compare>
void nth_element( RandomIt first, RandomIt nth, RandomIt last, Compare comp );

sort、partial_sort、nth_element都属于非稳定排序,即在排列等价元素的时候,无法保证原来在前面的排完序依然在前面。

稳定排序:

template<class RandomIt, class Compare>
void stable_sort( RandomIt first, RandomIt last, Compare comp );

因为sort、partial_sort、nth_element、stable_sort需要随机访问迭代器,所以只能应用于vector、string、deque和数组。

满足函数UnaryPredicate(返回bool)的元素会被移到容器前端,返回指向最后一个满足条件元素的下一个元素的迭代器:

template<class ForwardIt, class UnaryPredicate>
ForwardIt partition( ForwardIt first, ForwardIt last, UnaryPredicate p );
partition和stable_partition只需要双向迭代器,所以可以应用于所有标准序列容器。

32 如果确实需要删除元素,则需要在remove这一类算法之后调用erase

无法从迭代器推知对应的容器类型。

remove算法不是真正意义上的删除,它不能从容器中删除元素,

实际上,remove将“不用被删除”的元素移动到区间前部,并返回指向最后一个“不用被删除”元素的下一个元素。

所以在remove后应该调用erase,如删除值为99的元素:

v.erase(remove(v.begin(), v.end(), 99), v.end());

与之相似的还有remove_if和unique。

33 对包含指针的容器使用remove这一类算法时要特别小心

通过remove(remove_if、unique)删除元素时,若元素是指针,则指针会因为被覆盖导致资源泄漏。

解决方法: 调用remove前先遍历容器,如果指针所指的元素要被删除,析构指针所指对象,保留空指针 使用智能指针

34 了解哪些算法要求使用排序的区间作为参数

要求排序区间的STL算法:

为了使用二分查找:binary_search、lower_bound、upper_bound、equal_range、

为了提高性能(保证线性时间):set_union、set_intersection、set_difference、set_symmetric_difference、megre、inplace_merge、includes

不一定要排序区间(但排好序更好):unique、unique_copy

如果容器的排序方式和算法的默认排序方式less(<)不同时,需要指定函数子,如:binary(v.begin(), v.end(), 5, greater());

35 通过mismatch或lexicographical_compare实现简单的忽略大小写的字符串比较

tolower的参数和返回值都是int,且规定除了EOF外(用负数表示),其他值必须能用unsigned char来表示。

lexicographical_compare可以根据传入函数(判别式)来进行容器内容比较,返回两个容器不同的第一个位置。

不区分大小写字符串比较;

bool ciCharLess(char c1, char c2)
{
    return tolower(static_cast<unsigned char(c1)) < 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);
}

如果sting中间不包含空字符且不考虑国际化支持,可以把string专为const char*后用strcmp比较。

36 理解copy_if算法的正确实现

STL中没有copy_if( 注:C++11已加入 ),在此之前,只能手动复制:

while(begin != end)
{
    if( p(*begin) )
    {
        *destBegin ++ = *begin;
    }
    ++begin;
}

37 使用accumulate或者for_each进行区间统计

统计区间元素数目:count

统计区间满足判别式元素数目:count_if

区间最小值:min_element

区间最大值:max_element

自定义统计:

方法一:

template<class InputIt, class T, class BinaryOperation>
T accumulate(InputIt first, InputIt last, T init, BinaryOperation op);

init为统计初始值。op为统计函数,接受两个参数。op不能使任何迭代器失效,也不能修改范围内的任何一个元素(C++11)。

template<class InputIt, class T>
T accumulate(InputIt first, InputIt last, T init);

特化版。统计函数为operator+。即以init为初始值进行累加。

方法二:

template<class InputIt, class UnaryFunction>
UnaryFunction for_each(InputIt first, InputIt last, UnaryFunction f);

f可以是统计函数,但只接受一个参数。在for_each执行完毕后,f的副本会被返回,我们必须从中提取我们所需的统计信息。

第六章 函数子、函数子类、函数及其它

38 遵循按值传递的原则来设计函数子类

对于函数(指针)和函数子,作为STL的参数和返回值都是按值传递的。

如果通过模版参数来强制指定为引用,则可能编译不通过(出于性能考虑,有些STL配接器和算法使用引用参数来接受函数子,这样做会造成引用的引用)。

为了避免函数子(对象)的巨大复制开销和子类向父类传参导致的切割问题,将函数子中的数据和虚函数放到一个新的类中,函数子只保留一个指向新类对象的指针(桥接模式)。

39 确保判别式是“纯函数”

判别式(predicate)是一个返回值为bool类型(或可隐式转换为bool)的函数。STL中常用于关联容器的比较函数以及排序算法的参数。

纯函数:返回值仅仅依赖于其参数的函数(当然还有常量)。

判别式类:函数子类,operator ()是判别式。

如果判别式不是纯函数,则其必定依赖于其它某些变量,如函数子的类成员、函数的static变量等。这样会导致判别式拥有状态,影响下次调用的结果。

由于STL中接受判别式的地方既可以接受判别式,也可以接受判别式对象。

40 若是一个函数子,则应使他可配接

STL函数配接器:能够将函数子与另一个函数子、或某一个一般函数、或某个值结合起来形成一个新的函数子,预定义由四个:not1、not2、bind1st、bind2nd。

函数配接器都要求参数可配接,即包含特殊的类型定义:argument_type、first_argument_type、second_argument_type、result_type。

ptr_fun:将普通函数转换为可配接

对于函数子,获取这些特殊类型定义的最好办法是继承以下基类:

template <class ArgumentType, class ResultType>
struct unary_function;
template <class ArgumentType1, class ArgumentType2, class ResultType>
struct binary_function;

尽量不要让函数子拥有多个operator (),因为函数子最多只能继承一个模版实例化的基类,因此只有一种调用形式是可配接的。

注:C++11中,bind1st和bind2nd被废弃。由更泛化的std::bind取代。

ptr_fun被废弃。由更泛化的std::function和std::ref取代。

unary_function和binary_function被废弃。可能是因为C++11引入了更泛化的可变参数模版std::function的原因?

41 理解ptr_fun、mem_fun和mem_fun_ref的来由

mem_fun:用于指针容器对象调整成员函数调用为普通的函数调用( obj->function() -> function(obj) )。函数返回配接器mem_fun_t,该函数子实现调用利用参数调用成员函数。

mem_fun_ref:用于容器对象调整成员函数调用为普通的函数调用( obj.function() -> function(obj) )。函数返回配接器mem_fun_ref_t,该函数子实现调用利用参数调用成员函数。

注:C++11中,mem_fun和mem_fun_ref被废弃。由更泛化的mem_fn和bind取代。

42 确保less与operator<具有相同的语义

程序员可以针对用户定义的类型,特化std命名空间内的模版,但不能修改std命名空间中的组件。 less默认调用operator <来完成比较,为了避免违反直觉,不要修改less的行为。

第七章 在程序中使用STL

43 算法调用优先于手写的循环

每一个算法都至少需要使用一对迭代器来指定一个区间,然后在该区间上执行操作。

算法优于手写循环的原因:

  • 效率高(STL的设计者比使用者更了解其内部结构并进行相应的优化,能够采用更高效的算法)

  • 正确性高(更不容易出错)

  • 可维护性强(更简短、语义上更清晰)

44 容器的成员函数优于同名的算法

有些STL容器提供了与算法同名的成员函数,原因:

  • 成员函数速度更快(对于关联容器,对数时间对比线性时间)

  • 成员函数和容器的一贯行为保持一致(对于关联容器,采取等价而不是等值比较;对于map,只比较键而不是全部)

45 正确区分count、find、binary_search、lower_bound、upper_bound和equal_range

线性时间、相等性判断

  • count:用作存在性测试,统计数目

  • find:用作存在性测试,返回第一个匹配位置,比count效率更高。因为一旦匹配到立刻返回(如果没找到,指向end)

对数时间(需排好序)、等价性判断

  • binary_search:仅用作存在性判断(只返回bool,表示是否存在)

  • lower_bound:用作存在性判断,返回匹配的第一个位置(如果没找到,指向第一个适合插入的位置),所以需要检查返回位置的值是否与目标值等价,要手工实现等价

  • upper_bound:同lower_bound(如果没找到,指向最后一个适合插入的位置)

  • equal_range:用作存在性判断,返回一对迭代器,第一个为lower_bound返回值,第二个为upper_bound返回值。通过两者返回值是否相等来判断存在,通过两者距离来统计数目(distance)。

46 考虑使用函数对象而不是函数作为STL算法的参数

使用函数子(函数对象)的效率比函数高。

编译器将函数子模版在实例化过程中将operator ()内联,避免了函数调用。此外,在实例化的过程中进行了一些正确性检查,减少了运行期出错的可能。

而函数由于通过函数指针来传参,每次调用时都产生一次间址访问开销。受到函数指针的抑制,即使函数被声明为inline,编译器总是不会进行优化。

47 避免产生“直写型”的代码

在一行中调用多个算法的复杂语句被称为直写型代码,这种代码虽然很容易便携,但难以阅读和理解。

应该将复杂语句分解成容易理解的简单语句,并适当地加上一些注释。

48 总是包含(#include)正确的头文件

C++没有规定STL中头文件的相互包含关系,不同的实现中包含方式可能不同,基于可移植性,应该包含全部依赖的头文件,而不依赖于它们之间的相互包含。

几乎所有标准STL容器都被声明在与之同名的头文件中。

除了accumulate、inner_product、adjacent_difference、partial_sum在中外,其它算法都被声明在中。

特殊类型的迭代器(如istream_iterator、istreambuf_iterator)被声明在中。

标准函数子(如less)和函数子配接器(如not1)被声明在头文件中。

49 学会分析与STL相关的编译器诊断信息

STL相关语句在编译错误时会抛出一大堆乱七八糟的诊断信息。

简化诊断信息:

  • 对于string的诊断信息,可将basic_string相关的长字符串替换成string。

  • 对于内部类(下划线开头),可以将其模版内容删除掉。

  • 由于vector和string的迭代器是指针,因此可将指针替换为迭代器。

50 熟悉与STL相关的Web站点

SGI:为STL所有组建提供了详尽的文档。有些实现超出了STL范畴。

STLport:提供可在超过20种编译器上使用的SGISTL改进版本,并提供调试模式(用法错误时抛出错误)。

Boost:提供了大量的C++库,并称为STL标准的候补。简称干儿子。