Effective STL – 绿虫虫

参考来源：《Effective STL》(美) Scott Meyers [著]

Part One: Containers

Item 1：Choose your containers with care

Item 2：Beware the illusion of container-independent code

Item 3：Make copying cheap and correct for objects in containers

Item 4：Call empty instead of checking size() against zero

Item 5：Prefer range member functions to their single-element counterparts

Item 6：Be alert for C++’s most vexing parse

Item 7：When using containers of newed pointers, remember to delete the pointers before the container is destroyed

Item 8：Never create containers of auto_ptrs

Item 9：Choose carefully among erasing options

Item 10：Be aware of allocator conventions and restrictions

Item 11：Understand the legitimate uses of custom allocators

Item 12：Have realistic expectations about the thread safety of STL containers

Part Two: vector and string

Item 13：Prefer vector and string to dynamically allocated arrays

Item 14：Use reserve to avoid unnecessary reallocations

Item 15：Be aware of variations in string implementations

Item 16：Know how to pass vector and string data to legacy APIs

Item 17：Use “the swap trick” to trim excess capacity

Item 18：Avoid using vector<bool>

Part Three: Associative Containers

Item 19：Understand the difference between equality and equivalence

Item 20：Specify comparison types for associative containers of pointers

Item 21：Always have comparison functions return false for equal values

Item 22：Avoid in-place key modification in set and multiset

Item 23：Consider replacing associative containers with sorted vectors

Item 24：Choose carefully between map::operator[] and map-insert when efficiency is important

Item 25：Familiarize yourself with the nonstandard hashed containers

Part Four: Iterators

Item 26：Prefer iterator to const iterator, reverse_iterator, and const_reverse_iterator

首先来看看 vector<T> 容器 insert 和 erase 函数的声明

iterator insert(iterator position, const T& x);
iterator erase(iterator position);
iterator erase(iterator rangeBegin, iterator rangeEnd);

每个标准的容器都是类似，这些函数要求的迭代器类型都是 iterator，不是 const_iterator，不是 reverse_iterator，也不是 const_reverse_iterator。再来看看这四种迭代器类型的转换关系

+--base()--> iterator ----> const_iterator <--base()--+
|               |                                     |
|               v                                     |
+------ reverse_interator  ---------->  const_reverse_iterator

没有 const 修饰的迭代器可隐式转换为带 const 修饰的迭代器，带 reverse 修饰的迭代器可调用 base() 函数获得不带 reverse 修饰的迭代器，此外 iterator 能够隐式转换为 reverse_iterator。注意到没有从带 const 修饰到不带 const 修饰的隐式转换能力，于是 const_reverse 无法在诸如 insert 及 erase 类的成员函数中使用，至此有足够的理由为什么要偏好使用 iterator 而不是带 const 或 reverse 修饰的 iterator

一些 insert 和 erase 仅接受 iterators 作为形参；
无法将一个 const_iterator 隐式转换为一个 iterator，如 Item 27 所示，转换的方式既不普遍可行也不高效；
从一个 reverse_iterator 转换为一个 iterator 后可能需要调整，Item 28 解释了什么时候以及为什么需要。

Item 27：Use distance and advance to convert a container’s const_iterators to iterators

存在一种安全可移植的方式来根据 const_iterator 获得对应的 iterator：

deque<int> dq;
deque<int>::iterator iter(dq.begin());
deque<int>::const_iterator cIter;
... // make cIter point into dq
advance(iter, distance<deque<int>::const_iterator> >(iter, cIter)); // figure the distance between iter and cIter, then move iter that distance

上述做法取决于迭代器的类型，对于随机访问迭代器只需要常数的时间，对于双向访问迭代器需要线性的时间。因为这可能需要线性的时间来获得一个指向 const_iterator 所指向的元素的 iterator，而且必须在 const_iterator 所属容器可访问的情况下才可行（这样才可以执行 dq.begin() 语句），于是应当如 Item 27 所述尽量避免使用 const_iterator。

Item 28：Understand how to use a reverse_iterator’s base iterator

调用 reverse_iterator 的 base() 函数能够产生对应的 iterator，但其过程并不显而易见。考虑下例

vector<int> v;
v.reserve(5); // see Item 14
for (int i = 1;i <= 5;++i) // put 1-5 in the vector
    v.push_back(i);

vector<int>::reverse_iterator rIter = find(v.rbegin(), v.rend(), 3); // make rIter point to the 3
vector<int>::iterator iter(rIter.base()); // make iter the same as rIter's base

在代码执行过后，rIter 指向 3，iter 却指向 4。假设想要进行插入操作，在上例的 3 前面进行插入 99，调用 base() 把 rIter 转换为 iter 之后，由于 iter 指向 4，刚好就是需要插入的地方，再调用 insert 函数 v.insert(rIter.base(), 99)，即对于插入操作，reverse_iterator::base() 就是真正对应于 iterator。那么对于删除操作呢？因为 iter 的指向不同于 rIter，因此不能直接调用 erase(rIter.base())，应当删除的元素是 iter 所指元素的前驱，即对于删除操作，reverse_iterator::base() 并不真正对应于 iterator。

很容易对删除操作写出如下代码：

v.erase(--rIter.base()); // attempt to erase at the position preceding rIter.base(); for a vector, this will typically nor compile

vector 的 iterator 实质上是内置指针，于是 rIter.base() 返回一个指针，而 C++ 指示从函数返回的指针不能被修改，因此这样的表达式不能编译，正确的做法应当是先自增 reverse_iterator 对象再调用其 base() 方法，即

v.erase((++rIter).base()); // erase the element pointed to by rIter; this should always compile

Item 29：Consider istreambuf_iterators for character-by-character input

假设需要从一个文本文件拷贝内容到一个字符串中，看起来一种合理的方式是

ifstream inputFile("interestingData.txt");
string fileData((istream_iterator<char>(inputFile)), istream_iterator<char>());

很快便会发现这种方式不会拷贝空白符到字符串中，这是因为 istream_iterators 使用 operator<< 函数来完成实际的读取，而 operator<< 函数跳过空白符，于是需要清除 skipws 标识符：

ifstream inputFile("interestingData.txt");
inputFile.unsetf(ios_base::skipws); // disable the skipping of whitespace in inputFile
string fileData((istream_iterator<char>(inputFile)), istream_iterator<char>()};

这样所有的字符都会被拷贝到 fileData 中。你可能会发现拷贝的速度不然预期想象地快，operator<< 函数执行格式化输入，这意味着每次调用它时必须处理一大堆工作。它需要创建和销毁 sentry 对象（特殊的 iostream 对象用来在每次调用 operator<< 时执行 setup 及 cleanup 工作）；它需要检查可能会影响行为的流标识符，譬如 skipws；它需要执行读取错误的检查，在遇到错误时，需要检查流异常掩码来确定是否需要抛出一个异常。在执行格式化输入时就有这些所有的重要操作，但是如果只是想从输入流中一个个地抓取字符，此乃过分之举。

一种更高效的方式是采用包含于 <iterator> 头文件中的 istreambuf_iterators，它的使用方式同 istream_iterators 类似，不过 istreambuf_iterator<char> 对象直接从流缓冲区中读取下一个字符，更为精确的描述是，一个从输入流 s 读取的 istreambuf_iterator<char> 对象调用 s.rdbuf()->sgetc() 来读取 s 中的下一个字符。

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

不需要清除 skipws 标识符，istreambuf_iterators 从不跳过任何字符，无论流缓冲中下一个字符是什么，它都会去抓取。相较于 istream_iterators，istreambuf_iterators 的抓取速度最多能快 40% 左右。

对于非格式化的逐字符输出操作，同理考虑采用 ostreambuf_iterators 以避免 ostream_iterator 执行过多操作带来的开销。

Part Five: Algorithms

Item 30：Make sure destination ranges are big enough

STL 容器会自动扩容以容纳新插入的元素，但并不能理所当然地认为其总会按照意图的行为而自动扩容：

int transmogrify(int x); // this function produces some new value from x
vector<int> values;
vector<int> results;
// put data into values apply transmogrify to each object in values, appending the return values to results.
transform(values.begin(), values.end(), results.end(), transmogrify); // this code is error!

// apply transmogrify to each object in values, inserting the return values at the end of results.
transform(values.begin(), values.end(), back_inserter(results), transmogrify); // this code is right.

上面的错误代码试图对 value[0] 执行 transmogrify 操作后赋值给 *results.end()，但是 *results.end() 处并无对象，更何况 *(results.end()+1)！正确的做法是运用 back_inserter 来产生在指定目标范围起始位置的迭代器，程序运行的内部，back_inserter 返回的迭代器导致 push_back 被调用，因此 back_inserter 只能用于提供 push_back 方法的容器；同理，front_inserter 将导致 push_front 被调用，因此 front_inserter 只能用于提供 push_front 方法的容器，这也是为什么 front_inserter 用得没有 back_inserter 多的原因，因为 std::vector 没有提供 push_front 方法。使用 front_inserter 时会导致插入后的序列与原序列是逆向的，若要保持一致的顺序，应该对原序列进行逆向遍历：

list<int> results;
// insert transform's results at the front of results; preserve the relative object ordering.
transform(values.rbegin(), values.rend(), front_inserter(results), transmogrify);

若要在目标容器的任意位置进行插入，可借由 inserter 来完成：

// insert the results of the transmogrifications at the middle of results.
transform(values.begin(), values.end(), inserter(results, results.begin() + results.size()/2), transmogrify);

无论使用 back_inserter、front_inserter 还是 inserter，在目标范围的插入是逐个元素处理的，这对于连续存储的容器而言代价是昂贵的，尽管这无法改变，但在向 std::vector 或 std::string 插入时，可以事先调用 reserver 来避免内存重分配：

vector<int> results;
results.reserve(results.size() + values.size()); // ensure that results has the capacity for at least values.size() more elements
// as above, but results won't do any reallocations.
transform(values.begin(), values.end(), inserter(results, results.begin() + results.size()/2), transmogrify);

若是想覆盖目标容器中的元素而不是插入，则可以有下面两种方式来完成：

/* method 1 */
if (results.size() < values.size())
    results.resize(values.size()); // make sure results is at least as big as values is
// overwrite the first values.size() elements of results.
transform(values.begin(), values.end(), results.begin(), transmogrify);

/* method 2 */
results.clear(); // destroy all elements in results
results.reserve(values.size()); // reserve enough space
// put transform's return values into results.
transform(values.begin(), values.end(), back_inserter(results), transmogrify);

Item 31：Know your sorting options

一提及有序的元素，许多程序员想到的只有 sort，sort 固然很好，但倘若要求没那么苛刻呢？譬如，现在有一个存放元素类型是 Widget 的 vector，想要从中选取出质量最高的 20 个给用户，只需要前 20 个有序，其他 Widget 元素可以无序存放在 vector 中，这时可用 partial_sort：

bool qualityCompare(const Widget& lhs, const Widget& rhs)
{
    // return whether lhs's quality is greater than rhs's quality
}
/* put the best 20 elements(in order) at the front of widgets. */
partial_sort(widgets.begin(), widgets.begin() + 20, widgets.end(), qualityCompare);

在调用 partial_sort 之后，前 20 个元素就有序了，质量最高的 Widget 就是 widgets[0]，随后是 widgets[1]。倘若只需要选出质量最好的 20 个 Widget 就可以了而不需有序，partial_sort 已经比期望做得更多，这时可以采用 nth_element，它能够在指定一个元素的位置之后，调用的结果为，在该元素前面的元素都在排序规则上领先于在该元素后面的元素，而在该元素后面的元素都在排序规则上落后于在该元素前面的元素：

// put the best 20 elements at the front of widgets, but don't worry about their order.
nth_element(widgets.begin(), widgets.begin() + 20, widgets.end(), qualityCompare);

但是对于排序规则中相等的元素，partial_sort 和 nth_element 都不能让调用者控制其行为，如果要让排序前和排序后两个相等的元素的相对前后位置关系保持不变，则需要用 stable_sort，其提供稳定的排序。

nth_element 除了能够取得最前面的一些元素，还能够取得任何指定百分排序位置的元素，这正是其命名的由来：

vector<Widget>::iterator goalPosition; // iter indicating where the widget of interest is located
/* The following code finds the Widget with the median level of quality. */
goalPosition = widgets.begin() + widgets.size() / 2; // the widget of interest would be in the middle of the sorted vector
/* find the median quality value in widgets. */
nth_element(widgets.begin(), goalPosition, widgets.end(), qualityCompare); // goalPosition now points to the Widget with a median level of quality

/* The following code finds the Widget with a level of quality at the 75th percentile. */
vector<Widget>::size_type goalOffset = 0.25 * widgets.size(); // figure out how far from the beginning the Widget of interest is
/* find the quality value at the 75th percentile. */
nth_element(widgets.begin(), widgets.begin() + goalOffset, widgets.end(), qualityCompare); // goalPosition now points to the Widget with the 75th percentile level of quality

前述算法对于取得次序而言卓有成效，但有时是意图将容器中的元素按照某个规则进行分类，得到一个迭代器，在此位置前后的元素分别处于不同的分类中，可用 partition 完成这项工作：

bool hasAcceptableQuality(const Widget& w)
{
    // return whether w has a quality rating of 2 or better;
}
/* move all widgets satisfying hasAcceptableQuality to the front of widgets, and return an iterator to the first widget that isn't satisfactory. */
vector<Widget>::iterator goodEnd = partition(widgets.begin(), widgets.end(), hasAcceptableQuality);

在调用之后，从 widgets.begin() 到 goodEnd 范围内的所有 Widgets 的质量都是 1 或 2，从 goodEnd 到 widgets.end() 范围内的所有 Widgets 的质量都更差，如果想要维持相等元素在算法调用前后相对位置不变，自然而然地采用 stable_partition 替代 partition 即可。

算法 sort, stable_sort, partial_sort, 和 nth_element 需要随机访问迭代器，因此只能适用于 vectors, strings, deques 和 arrays，而 list 不能采用这些算法，当然，list 自身提供了一个成语函数 sort，而且该排序算法是稳定的。partition 和 stable_partition 只要求双向访问迭代器，因此能够适用于所有标准的序列容器。

总结这些算法如下：

If you need to perform a full sort on a vector, string, deque, or array, you can use sort or stable_sort.
If you have a vector, string, deque, or array and you need to put only the top n elements in order, partial_sort is available.
If you have a vector, string, deque, or array and you need to identify the element at position n or you need to identify the top n elements without putting them in order. nth_element is at your beck and call.
If you need to separate the elements of a standard sequence container or an array into those that do and do not satisfy some criterion, you’re probably looking for partition or stable_partition.
If your data is in a list, you can use partition and stable_partition directly, and you can use list-sort in place of sort and stable_sort. If you need the effects offered by partial_sort or nth_element, you’ll have to approach the task indirectly, but there are a number of options, as I sketched above.

从效率的角度来看，算法做得工作越是完备，则所需时间越多，一般而言，稳定的算法比不需要稳定的算法更费时，可将本条款所述 6 个算法的效率从优到劣排序如下：

1.partition, 2.stable_partition, 3.nth_element, 4.partial_sort, 5.sort, 6.stable_sort

因此在选择算法时，应当选择能够满足要求的算法即可，一来是代码的目的性表述地更为明确，二来是效率也更高。

Item 32：Follow remove-like algorithms by erase if you really want to remove something

remove 是 STL 中一个很容易让新手犯错的函数，先来看看其声明：

template<class ForwardIterator, class T>
ForwardIterator remove(ForwardIterator first, ForwardIterator last, const T& value);

像许多其他的算法函数一样，remove 接受一对指定范围的迭代器，remove 不接受容器作为参数，因此 remove 不知道其在对什么容器进行操作，因为没有能够从迭代器类型得知对应所属容器类型的方式。思考一下，唯一能够从容器中删除对象的方式是调用容器的方法，往往这样的方法命名为 erase，因此 remove 无法消除容器中的元素，下面的例子反映了这个事实：

vector<int> v; // create a vector<int> and fill it with
v.reserve(10); // the values 1-10 (See Item 14 for an explanation of the reserve call)
for (int i = 1; i <= 10; ++i)
    v.push_back(i);
cout << v.size(); // prints 10
v[3] = v[5] = v[9] = 99;        // set 3 elements to 99
remove(v.begin(), v.end(), 99); // remove all elements with value 99
cout << v.size(); // still prints 10!

从这个例子中应该深化记忆：remove doesn’t “really” remove anything, because it can’t.

刚刚解释了为什么 remove 无法消除容器中的对象，现在来看看 remove 操作的具体行为，在调用 remove 之前和之后的对比：

/* before execute */
// v.begin()                       v.end()
//   |                                |
//   1  2  3  99  5  99  7  8  9  99
vector<int>::iterator newEnd(remove(v.begin(), v.end(), 99) ;
/* after execute */
// v.begin()            newEnd   v.end()
//   |                    |        |
//   1  2  3  5  7  8  9  ?  ?  ?
//   1  2  3  5  7  8  9  8  9  99

上述用 ? 表示在概念上此元素已被消除，尽管实际上仍存在，从 v.begin() 到 newEnd 间是 “unremoved” 元素，从 newEnd 到 v.end() 间是 “removed” 元素。在几乎所有实现上，最后的三个 “removed” 元素为 8, 9, 99，有两个 99 不见了，仅剩下一个 99，如果想要保留下被消除的元素，最好采用 partition 来替代 remove。

remove 算法的内部，沿着指定的范围，用后面需要保留的元素覆盖需要 “removed” 的元素，覆盖通过赋值运算来进行。

可以认为需要 “removed” 的元素扮演了 hole 的角色等待后面需要保留的元素来填充，上述例子的详细运行过程如下：

remove 检查 v[0]，发现它不需要被移除，然后检查操作转向 v[1]，对 v[2] 也执行同样的操作；
它发现 v[3] 需要被移除，因此它标记 v[3] 需要被覆盖，随后检查操作转向 v[4]。类比地，它会注意 v[3] 是一个需要被填充的 “hole”；
它发现 v[4] 需要被保留，因此它把 v[4] 赋值给 v[3]，标记 v[4] 现在需要被覆盖，然后检查操作转向 v[5]。继续类比，它用 v[4] 填充 v[3] 并标记 v[4] 现在是一个 “hole”；
它发现 v[5] 需要被移除，因此它对其忽略并将检查操作转向 v[6]。它仍然记得 v[4] 是一个 “hole”；
它发现 v[6] 需要被保留，因此他把 v[6] 赋值给 v[4]，记得 v[5] 是一个新的 “hole” 需要被填充，随后检查操作转向 v[7]；
类似上面的行为，它会检查 v[7], v[8] 和 v[9]，它会将 v[7] 赋值给 v[5]，将 v[8] 赋值给 v[6]，忽略 v[9] 因为 v[9] 是一个需要被移除的元素；
它返回一个迭代器指示下一个需要被覆盖的元素，在此例中为 v[7]。

执行完 remove 操作后，需要被消除的元素就很容易确定了，就是从 “new logical end” 到 “real end of the container” 范围内的那些元素：

v.erase(remove(v.begin(), v.end(), 99), v.end()); // really remove all elements with value 99
cout << v.size(); // now returns 7

上述操作就是所谓的 erase-remove idiom，因为 remove 和 erase 是如此地联合在一块，以至于 list 的成员函数 remove 将这两者的功能并在了一块：

list<int> li;  // create a list
......         // put some values into it
li.remove(99); // eliminate all elements with value 99: this really removes elements, so li's size may change

另外行为和 remove 基本一致的算法有 remove_if 和 unique。此外就如同 list::remove 能真正地移除元素（比 erase-remove idiom 更高效），list::unique 也能真正地移除邻近的重复值（比 erase-unique idiom 高效得多）。

Item 33：Be wary of remove-like algorithms on containers of pointers

有一些动态分配的 Widgets，其中每个或许是 certified，将其指针存放在 vector 内：

class Widget
{
public:
    bool isCertified() const; // whether the Widget is certified
};
vector<Widget*> v;       // create a vector and fill it with pointers to dynamically
v.push_back(new Widget); // allocated Widgets

现在想要删除 uncertified Widgets，因为不再需要使用它们，回忆起条款三十二和条款四十三：

/* erase ptrs to uncertified Widgets; see Item 41 for info on mem_fun. */
v.erase(remove_if(v.begin(), v.end(), not1(mem_fun(&Widget::isCertified))), v.end());

马上，回忆起条款七，你将担心 erase 会造成在销毁指针之后无法删除指针所指的对象，即便如此也已经太晚了，remove_if 才是这段代码的罪魁祸首，比对下面两张执行 remove_if 前后 vector 的状态图，你马上就能看出问题的所在：

显然，原先指向 WidgetB 和 WidgetC 的指针被重新赋值，造成 WidgetB 和 WidgetC 无法被删除，从而引起内存泄漏。

一种解决方案是在使用 erase-remove idiom 前事先将需要移除的指针置 null，然后消除 vector 中所有的 null ptr：

void delAndNullifyUncertified(Widget*& pWidget)
{
    if (!pWidget->isCertified()) // if *pWidget is an uncertified Widget,
    {
        delete pWidget; // delete the pointer
        pWidget = 0;    // and set it to null
    }
}
/* delete and set to null all ptrs to uncertified widgets. */
for_each(v.begin(), v.end(), delAndNullifyUncertified);
/* eliminate null ptrs from v; 0 must be cast to a ptr so C++ correctly deduces the type of remove's 3rd param. */
v.erase(remove(v.begin(), v.end(), static_cast<Widget*>(0)), v.end());

或者也可以使用带引用计数的智能指针 shared_ptr，随后就可以直接使用 erase-remove idiom。在该例子中，需要 shared_ptr<Widget> 类型能够隐式地转换为 Widget* 类型，因为被调用的成员函数只接受 Widget* 类型的参数，如果不存在这样的隐式转换规则，编译器会报错：

vector<shared_ptr<Widget> > v; // create a vector and fill it with smart pointers to dynamically allocated Widgets
v.push_back(shared_ptr<Widget>(new Widget));
/* erase the ptrs to uncertified Widgets; no resources are leaked. */
v.erase(remove_if(v.begin(), v.end(), not1(mem_fun(&Widget::isCertified))), v.end());

Item 34：Note which algorithms expect sorted ranges

并不是所有的算法都适用于所有情况，例如 remove 需要前向迭代器以拥有赋值的能力，结果就是它不能运用于只有输入迭代器的情况，比如 maps 和 multimaps，如果忽视了这些规则，很有可能编译器会输出冗长且难以理解的错误信息，然而另外有些算法需要输入范围内的数据是有序的，服从它们的要求非常重要，因为编译器不会报错，然而运行期行为将是未定义的。

下面列举出所有对输入数据要求是已排序的算法：

binary_search  lower_bound  upper_bound  equal_range
includes set_union  set_intersection  set_difference  set_symmetric_difference
merge  inplace_merge

此外，存在两个算法通常是用于处理已排序的数据，尽管它们并不作此要求：

unique  unique_copy

对于算法 binary_search, lower_bound, upper_bound 和 equal_range，提供有序的数据，它们保证对数级运行时间（同时要求迭代器是随机访问的，若是双向访问迭代器，则比较次数仍是对数级的，但是运行却是线性级的，因为没法作 “iterator arithmetic”）。

算法 includes 用来确定是否一个范围内的数据是另一个范围内数据的子集，它以线性时间运行，算法 set_union, set_intersection, set_difference 和 set_symmetric_difference 也提供了线性时间的性能。

merge 和 inplace_merge 以线性时间运行，将两组已排序的数据并成一组排好序的数据。

不像前面的几个算法，unique 和 unique_copy 在输入数据是乱序的情况下有 well-defined 的行为，但是标准中对 unique 的行为描述为：Eliminates all but the first element from every consecutive group of equal elements. 根据其用途，也应当是接受有序的数据。

STL 允许对排序算法指定比较函数，当把排好序的数据传入一个有比较函数的算法时，必须保证该算法的比较函数与排序算法所采用的比较函数的比较规则是一致的，下面是一个错误的例子：

vector<int> v; //create a vector, put some data into it
sort(v.begin(), v.end(), greater<int>()); // sort it into descending order
/* work with the vector(without changing it) search for a 5 in the vector, assuming it's sorted in ascending order! */
bool a5Exists = binary_search(v.begin(), v.end(), 5);

binary_search 默认假定采用升序排列，然而在此例中 vector 中元素却是降序排列的，自然而然结果是无法预料的，正确的做法是：

/* search for a 5 using greater as the comparison function. */
bool a5Exists = binary_search(v.begin(), v.end(), 5, greater<int>());

最后顺便提一句，所有要求有序输入的算法根据 equivalence 确定两个元素值是否 “the same”，就像标准关联容器一样，作为对比，unique 和 unique_copy 算法根据 equality 确定两个元素值是否 “the same”。

Item 35：Implement simple case-insensitive string comparisons via mismatch or lexicographical compare

程序员们渴望的大小写无关的字符串比较接口通常有两种形式，一种是和 strcmp 类似的，另一种是和 operator< 类似的。

先解决第一类 strcmp-like 接口，写一个单个字符大小写无关的比较函数：

/* case-insensitively compare chars c1 and c2, returning -1 if c1 < c2, 0 if c1==c2, and 1 if c1 > c2. */
int ciCharCompare(char c1, char c2)
{
    int Ic1 = tolower(static_cast<unsigned char>(c1));
    int Ic2 = tolower(static_cast<unsigned char>(c2));
    if (Ic1 < Ic2) return -1;
    if (lc1 > Ic2) return 1;
    return 0;
}

上述的类型转换是因为和许多 <cctype> 中的函数一样， tolower 的参数和返回类型都是 int 型的，其值必须能够表示为 unsigned char。

在下面的实现中，将长度较短的字符串作为具体实现函数 ciStringCompareImpl 的第一个参数，外围函数 ciStringCompare 只是确保参数以正确的顺序被传递：

int ciStringCompare(const string& s1, const string& s2)
{
    return s1.size() <= s2.size() ? ciStringCompareImpl(s1, s2) : -ciStringCompareImpl(s2, s1);
}

int ciStringCompareImpl(const string& si, const strings s2)
{
    /* PSCI = "pair of string::const_iterator" */
    typedef pair<string::const_iterator, string::const_iterator> PSCI;
    /* see Item 41 for why we need ptr_fun. */
    PSCI p= mismatch(s1.begin(), s1.end(), s2.begin(), not2(ptr_fun(ciCharCompare)));

    if (p.first == s1.end()) // if true, either s1 and s2 are equal or s1 is shorter than s2
        return p.second == s2.end() ? 0 : -1;

    return ciCharCompare(*p.first, *p.second); // the relationship of the strings is the same as that of the mismatched chars
}

一旦知道两个字符串第一个不同的位置，就能很容易地确定出次序，看上去比较怪异的是 mismatch 的参数 not2(ptr_fun(ciCharCompare))，该谓词负责返回 true 当两个字符相同时，因为 mismatch 在该谓词返回 false 的时候停止运行，我们不能直接使用 ciCharCompare，因为其返回 -1, 1 或 0, 而且当字符相同的时候返回 0，如果将 ciCharCompare 作为谓词传递给 mismatch，C++ 会将其隐式转换为 bool，为修复这个问题，在外围添加上了not2 和 ptr_fun。

解决第二类 operator-like 接口，只需编写一个字符比较函数并将其作为谓词传递给 STL 的 lexicographical_compare 由后者来处理实际工作：

/* return whether c1 precedes c2 in a case-return insensitive comparison; Item 46 explains why a function object might be preferable to this function. */
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);
}

lexicographical_compare 可以被认为是 strcmp 的泛化形式，其能够被传递任意用户指定的谓词来判定两个元素的次序。

在标准 C 的扩展库中往往有这么一个函数，命名为 stricmp 或是 strcmpi，如果牺牲部分的可移植性，最简洁的方式就是将 string 转换为 const char* 指针后使用该函数来进行比较：

int ciStringCompare(const string& s1, const string& s2)
{
    /* the function name on your system might not be stricmp. */
    return stricmp(s1.c_str(),s2.c_str());
}

Item 36：Understand the proper implementation of copy_if

STL 有一个非常有趣的特征，它提供了 11 种名字中带有 “copy” 的算法：

copy  copy_backward  replace_copy  reverse_copy
replace_copy_if  unique_copy  remove_copy  rotate_copy
remove_copy_if  partial_sort_copy_unintialized_copy  unique_copy

但是 copy_if 在 C++11 中才被加入，在旧编译器中需要自己手写，下面是 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;
}

Item 37：Use accumulate or for_each to summarize ranges

有时需要对一个范围内的元素进行操作而得到单个对象，对通常需要的信息，特殊目的的算法能达到此项工作的能力，count 计算出范围内元素的数目，count_if 计算出范围内满足谓词的元素的个数，min_element 和 max_element 则用于得到范围内的最值。

但是有时需要按照特定的规则去 summarize 一个范围内的数据，譬如统计一个容器中所有字符串的总长度。STL 提供了 accumulate 算法助我们一臂之力，它并不是被包含在 <algorithm> 中，而是与其他三个数值算法 inner_product, adjacent_difference 和 partial_sum 一同被包含在 <numeric> 中。

如同许多算法一样，存在两种形式的 accumulate，第一种接受一对迭代器和初始值，返回范围内所有值的总和：

list<double> Id; // create a list and put some doubles into it
double sum = accumulate(ld.begin(), Id.end(), 0.0); // calculate their sum, starting at 0.0

注意上述的初始值不能是 0，因为 accumulate 被调用后实例化的模板参数应当是 double 而不是 int，否则会造成所有的运算都是基于 int 在进行，从而得到错误的结果。

accumulate 仅需要求输入迭代器即可，因此甚至能够对其配合使用 istream_iterators 和 istreambuf_iterators：

cout << "The sum of the ints on the standard input is" << accumulate(istream_iterator<int>(cin), istream_iterator<int>(), 0);

下面给出如何统计容器中字符串的总长度的示例：

string::size_type stringLengthSum(string::size_type sumSoFar, const strings s)
{
    return sumSoFar + s.size();
}

set<string> ss; // create container of strings and populate it
/* set lengthSum to the result of calling StringLengthSum on each element in ss, using 0 as the initial summary value. */
string::size_type lengthSum = accumulate(ss.begin(), ss.end(), 0, stringLengthSum);

我们也可以采用 STL 内置的 functors 作为 accumulate 的输入函数：

vector<float> vf; // create container of floats and populate it
/* set product to the result of calling multiplies<float> on each element in vf, using 1.0 as the initial summary value. */
float product = accumulate(vf.begin(), vf.end(), 1.0, multiplies<float>());

最后的例子要计算一系列点坐标的平均值：

struct Point {
    Point(double _x, double _y): x(_x), y(_y) {}
    double x, y;
};

class PointAverage : public binary_function<Point, Point, Point> // see Item 40
{
public:
    PointAverage(): xSum(0), ySum(0), numPoints(0) {}
    const Point operator()(const Point& avgSoFar, const Point& p)
    {
        ++numPoints;
        xSum += p.x;
        ySum += p.y;
        return Point(xSum/numPoints, ySum/numPoints);
    }
private:
    size_t numPoints;
    double xSum;
    double ySum;
};

list<Point> lp;
/* the initial point value passed to accumulate is ignored, as it should be. */
Point avg = accumulate(lp.begin(), lp.end(), Point(0, 0), PointAverage());

尽管上述代码运行良好，但是修改了其成员变量 numPoints, xSum 和 ySum 会导致副作用，C++ 标准禁止将含有副作用的函数传递给 accumulate，这恰好给了我们一个机会来讨论另一个算法 for_each，它也能用于 summarize 一个范围内的元素并且标准没有禁止传递带有副作用的函数，for_each 接受一个输入范围和一个函数，对其中每个元素都调用该函数，但是传递给 for_each 的函数只接受一个参数，在 for_each 执行完毕的时候返回此函数的副本。值得注意地，传递给 for_each 的函数也可能有副作用。忽视副作用的问题，使用 for_each 来进行 summarize 虽合理，但是没有 accumulate 来得清晰直观，for_each 返回的是一个函数对象，因此我们必须能够从该对象中析出所需的信息，这通过一个成员函数就可以完成：

class PointAverage : public unary_function<Point, void> // see Item 40
{
public:
    PointAverage(): xSum(0), ySum(0), numPoints(0) {}
    void operator()(const Point& p)
    {
        ++numPoints;
        xSum += p.x;
        ySum += p.y;
    }
    Point result() const { return Point(xSum/numPoints, ySum/numPoints); }
private:
    size_t numPoints;
    double xSum;
    double ySum;
};

Point avg = for_each(lp.begin(), lp.end(), PointAverage()).result;

Part Six: Functors, Functor Classer, Functions, etc

Item 38：Design functor classes for pass-by-value

C 和 C++ 都不允许把函数作为参数传递给其他函数，能够被用来传递的是函数指针，而且函数指针是按值传递的，譬如调用 qsort 时，其形参 cmpfcn 以值传递的方式从调用处传递给 qsort：

void qsort(void *base, size_t nmemb, size_t size, int (*cmpfcn)(const void*, const void*));

STL 的函数对象从函数指针模仿而来，因此它们也是按值传递的，for_each 的声明就能证明这点：

template <class InputIterator, class Function>
Function // note return-by-value
for_each(InputIterator first, InputIterator last, Function f); // note pass-by-value

既然函数对象按值传递并且按值返回，那么其尺寸就应该足够小以使得赋值开销很小，另外函数对象必须是 monomorphic 而不是 polymorphic，也就是不允许含有虚函数，这是因为派生类对象在以基类类型作为形参按值传递时会被 slicing，其派生类的部分会被切除。

若要使得函数对象能够 big 或 polymorphic，而且不违背按值传递的规则，可采用桥接模式，把大尺寸数据成员和虚函数放进实现类，函数对象中只存放指向实现类的指针：

template <typename T>
class BPFCImpl
{
public:
    virtual ~BPFCImpl(); // polymorphic classes need virtual destructors
    virtual void operator()(const T& val) const;

private:
    Widget w; // all the data that used to be in BPFC are here
    friend class BPFC<T>; // let BPFC access the data
};

template <typename T>
class BPFC : public unary_function<T, void> // small, monomorphic
{
private:
    BPFCImpl<T> *pImpl; // this is BPFC’s only data

public:
    void operator()(const T& val) const // this is nonvirtual
    { 
        pImpl->operator()(val); // it forwards to BPFCImpl
    }
};

这种技巧的使用需保证函数对象类的拷贝构造函数能够正确处理指向的实现类的指针，最简单的解决方案就是采用类似 shared_ptr 的引用计数型的智能指针。

Item 39：Make predicates pure functions

谓词（predicate）指的是返回类型是 bool 或是能够隐式转换为 bool 的函数。纯函数（pure function）指的是函数的返回值仅依赖于它的参数的取值，每次传递相同的参数都返回相同的结果。谓词类（predicate class）是那些 operator() 成员函数是谓词的仿函数类。

谓词函数必须是纯函数，下面是一个违反该限制的谓词类：

class BadPredicate : public unary_function<Widget, bool>
{
public:
    BadPredicate(): timesCalled(0) {} // init timesCalled to 0
    bool operator()(const Widget&) { return ++timesCalled == 3; }
private:
    size_t timesCalled;
};

假如我们需要使用这个类来消除 vector<Widget> 中的第三个 Widget：

vector<Widget> vw; // create vector and put some Widgets into it
/* eliminate the third Widget. */
vw.erase(remove_if(vw.begin(), vw.end(), BadPredicate()), vw.end());

这段代码看似合理，但是它不仅会消除第三个元素，而且还会消除第六个元素，为了解原因，需观察 remove_if 通常的实现方式：

template <typename FwdIterator, typename Predicate>
FwdIterator remove_if(FwdIterator begin, FwdIterator end, Predicate p)
{
    begin = find_if(begin, end, p);
    if (begin == end)
        return begin;
    else
    {
        FwdIterator next = begin;
        return remove_copy_if(++next, end, begin, p);
    }
}

注意到谓词 p 第一次从传递给 find_if，之后是 remove_copy_if，两次传递的都是 p 的副本。find_if 接受到的 BadPredicate 对象 p 的 timesCalled 为 0，随后 find_if 不断调用该 BadPredicate 对象直至返回 true，因此一共调用了三次，随后 remove_if 继续执行直至调用 remove_copy_if，传递另一个 p 的副本，此时 p 的 timesCalled 仍为 0，结果就是 remove_copy_if 第三次调用 p 的副本时会返回 true，因此共有两个 Widgets 被消除。

避免此类困境的一个最简单的方式是声明谓词类的 operator() 成员函数为 const，这样编译器就不会允许类数据成员被修改，虽然这种做法对于正确的行为是必要的，但是不够充分，一个有着良好行为的 operator() 不仅仅应当是 const，同时也应当是一个纯函数。

由于任何谓词类能被应用的地方，谓词函数经过 ptr_fun 修改后也能适用，因此纯函数的限制也就延伸至了谓词函数，下面是一个错误的谓词函数示例：

bool anotherBadPredicate(const Widget&, const Widget&)
{
    static int timesCalled = 0; // No! No! No! No! No! No! No!
    return ++timesCalled == 3;  // Predicates should be pure functions, and pure functions have no state
}

Item 40：Make functor classes adaptable

现在有一个存放着 Widget* 指针的 list 和一个确定一个 Widget 是否有趣的函数，于是要找到第一个有趣的 Widget 是非常容易的：

list<Widget*> widgetPtrs;
bool isInteresting(const Widget *pw);
list<Widget*>::iterator i = find_if(widgetPtrs.begin(), widgetPtrs.end(), isInteresting);
if (i != widgetPtrs.end()) {} // process the first interesting pointer-to-widget

若是要找到第一个不有趣的 Widget，大多数程序员第一反应：

list<Widget*>::iterator i = find_if(widgetPtrs.begin(), widgetPtrs.end(), not1(isInteresting)); // error! won't compile

然而，必须在调用 not1 前应用 ptr_fun 才能让编译器不发出抱怨：

list<Widget*>::iterator i = find_if(widgetPtrs.begin(), widgetPtrs.end(), not1(ptr_fun(isInteresting))); // fine

Why? ptr_fun 做的唯一一件事就是提供了一些 typedefs，而这些 typedefs 恰好是 not1 所需要的，应此直接将 isInteresting 应用于 not1 无法通过编译，这些 typedefs 是 argument_type, first_argument_type, second_argument_type 和 result_type，另外有四个函数适配器 not1, not2, bind1st 和 bind2nd 也需要这些 typedefs，提供了这些必要的 typedefs 的函数对象就被称为是 adaptable，而缺少这些 typedefs 的函数对象就不是 adaptable，adaptable 的函数对象与非 adaptable 的相比能被应用地更加广泛，在需要手写 adapters 时，最方便的方式是继承一个 base struct，对于成员函数 operator() 只接受一个参数的仿函数类而言，这个 base struct 是 std::unary_function，对于成员函数 operator() 接受两个参数的仿函数类而言，这个 base struct 是 std::binary_function。std::unary_function 和 std::binary_function 的定义中提供了这些 typedefs，而 ptr_fun() 只是负责创建一个继承自它们的类，其中包装只接受一个参数的函数的函数对象定义也在下面列出

template <typename T, typename R>
struct unary_function
{
    typedef T    argument_type; 
    typedef R    result_type; 
};

template <typename T1, typename T2, typename R>
struct binary_function
{
    typedef T1    first_argument_type; 
    typedef T2    second_argument_type;
    typedef R     result_type;
};

template <typename T, typename R>
class pointer_to_unary_function : public unary_function<T, R>
{
public:
    explicit pointer_to_unary_function(R (*__x)(T)) : _M_ptr(__x) { }
    R operator()(T __x) const { return _M_ptr(__x); }

protected:
    R (*_M_ptr)(T);
};

template <typename T, typename R>
inline pointer_to_unary_function<T, R> ptr_fun(R (*__x)(T))
{
    return pointer_to_unary_function<T, R>(__x);
}

下面是一对如何使用 std::unary_function 和 std::binary_function 的例子：

template<typename T>
class MeetsThreshold : public std::unary_function<Widget, bool>
{
private:
    const T threshold;

public:
    MeetsThreshold(const T& threshold);
    bool operator()(const Widget&) const;
};

struct WidgetNameCompare : std::binary_function<Widget, Widget, bool>
{
    bool operator()(const Widget& lhs, const Widget& rhs) const;
};

注意到传递给 unary_function 或 binary_function 的类型与仿函数类的 operator() 成员函数的参数类型和返回类型是一致的，从上面 binary_function 的例子还可以看到，尽管 operator() 成员函数的参数类型是 const Widget& 类型，传递给 binary_function 的类型是 Widget，通常，非指针类型传递给 unary_function 或 binary_function 时，const 和 reference 都被去除，然而对于指针类型，则不做任何改动：

struct PtrWidgetNameCompare : std::binary_function<const Widget*, const Widget*, bool>
{
    bool operator()(const Widget* lhs, const Widget* rhs) const;
}

继承这两个 base struct 的目的在于获得 typedefs，派生类自然而然是 adaptable，于是下面的代码可以正常运行：

list<Widget> widgets;
/* find the last widget that fails to meet the threshold of 10. */
list<Widget>::reverse_iterator i1 = find_if(widgets.rbegin(), widgets.rend(), not1(MeetsThreshold<int>(10)));
Widget w(constructor arguments);
/* find the first widget that precedes w in the sort order defined by WidgetNameCompare. */
list<Widget>::iterator i2 = find_if(widgets.begin(), widgets.end(), bind2nd(WidgetNameCompare(), w);

STL 默认一个仿函数类只有一个 operator() 成员函数，因此若需要使用同时使用引用传递和指针传递的形式，应该写两个仿函数类 WidgetNameCompare 和 PtrWidgetNameCompare 而不是把两种形式的 operator() 塞进行一个仿函数里。

Item 41：Understand the reasons for ptr_fun, mem_fun, and mem_fun_ref

如果有一个函数 f 和一个对象 x，在 x 成员函数外部想要调用 x，C++ 提供了以下三种方式：

f(x); // Syntax #1: when f is a non-member function
x.f(); // Syntax #2: when f is a member function and x is an object or a reference to an object
p->f(); // Syntax #3: when f is a member function and p is a pointer to x

假定有一个函数用来测试 Widgets 和一个充满 Widgets 的容器，为了测试容器中的所有 Widgets，可以采用 for_each 这么做：

void test(Widget& w); // test w and mark it as "failed" if it doesn't pass the test
vector<Widget> vw;    // vw holds widgets
for_each(vw.begin(), vw.end(), test); // Call #1 (compiles)

如果 test 函数是 Widget 的成员函数呢？

class Widget
{
public:
    void test();   // perform a self-test; mark *this as "failed" if it doesn't pass
};

list<Widget*> lpw; // lpw holds pointers to widgets
for_each(vw.begin(), vw.end(), &Widget::test);   // Call #2 (won't compile)
for_each(lpw.begin(), lpw.end(), &Widget::test); // Call #3 (also won't compile)

为什么 Call #2 和 Call #3 不能通过编译呢？看下 for_each 的实现便知：

template <typename InputIterator, typename Function>
Function for_each(InputIterator begin, InputIterator end, Function f)
{
    while (begin != end)
        f(*begin++);
}

明显地看出，for_each 对 Syntax #1 形式进行了硬编码，因此仅有 Call #1 是与之兼容的，现在或许可以猜到 mem_fun 和 mem_fun_ref 为什么存在的原因了，看下函数对象适配器中 mem_fun 和 mem_fun_ref 的定义：

/**
 * There are a total of 8 = 2^3 function objects which are adaptors for pointers to members.
 * (1) Member functions taking no arguments vs member functions taking one argument.
 * (2) Call through pointer vs call through reference.
 * (3) Const vs non-const member function.
 * All of this complexity is in the function objects themselves. You can ignore it
 * by using the helper function mem_fun and mem_fun_ref, which create whichever type
 * of adaptor is appropriate.
 */
template <typename R, typename T>
class mem_fun_t : public unary_function<T*, R>
{
public:
    explicit mem_fun_t(R (T::*__pf)()) : _M_f(__pf) { }
    R operator()(T* __p) const { return (__p->*_M_f)(); }

private:
    R (T::*_M_f)();
};

template <typename R, typename T>
class mem_fun_ref_t : public unary_function<T, R>
{
public:
    explicit mem_fun_ref_t(R (T::*__pf)()) : _M_f(__pf) { }
    R operator()(T& __r) const { return (__r.*_M_f)(); }

private:
    R (T::*_M_f)();
};

/* declaration for mem_fun for non-const member functions taking no parameters. T is the class, R is the return type of the pointed-to member function. */
template <typename R, typename T>
inline mem_fun_t<R, T> mem_fun(R (T::*__f)())
{
    return mem_fun_t<R, T>(__f);
}

template <typename R, typename T>
inline mem_fun_ref_t<R, T> mem_fun_ref(R (T::*__f)())
{
    return mem_fun_ref_t<R, T>(__f);
}

mem_fun 接受一个成员函数指针 __f，返回一个类型为 mem_fun_t 的对象，类 mem_fun_t 接受一个成员函数指针并提供一个自己的 operator() 然后在其中调用传进来的成员函数，下面是其应用示例：

for_each(lpw.begin(), lpw.end(), mem_fun(&Widget::test));   // this will now compile
for_each(vw.begin(), vw.end(), mem_fun_ref(&Widget::test)); // this will now compile too

Item 42：Make sure less<T> means operator<

现在的 Widget 提供了获取 weight 和 maxSpeed 的方法，默认的排序规则取决于 weiget：

class Widget
{
public:
    size_t weight() const;
    size_t maxSpeed() const;
}

bool operator<(const Widget& lhs, const Widget& rhs)
{
    return lhs.weight() < rhs.weight();
}

假定我们想要创建一个 multiset<Widget>，其中 Widgets 按 maximum speed 排序，由于 multiset<Widget> 的默认比较函数是 less<Widget>，默认情况下，它就是通过调用 Widgets 的 operator< 来工作的，于是一种方法试图创建 less 模板针对 Widget 的特化形式：

template<> // This is a specialization of std::less for Widget; it's a very bad idea
struct std::less<Widget> : public std::binary_function<Widget, Widget, bool>
{
    bool operator()(const Widget& lhs, const Widget& rhs) const
    {
        return lhs.maxSpeed() < rhs.maxSpeed();
    }
}

这种做法是极为不被推荐的，因为它试图特化一个 std 命名空间内的模板，而不应当修改关于 std 命名空间的任何已经存在的内容，极少数的情况下能够允许添加用户自定义的类型：

namespace std {
template <typename T> // this is a spec, of std::less for boost::shared_ptr<T>
struct less<boost::shared_ptr<T> > : public binary_function<boost::shared_ptr<T>, boost::shared_ptr<T>, bool>
{ 
    bool operator()(const boost::shared_ptr<T>& a, const boost::shared_ptr<T>& b) const
    {
        return less<T*>()(a.get(),b.get()); // shared_ptr::get returns the built-in pointer that s in the shared_ptr object
    }
};
}

上述特化之所以合理是因为它只确保智能指针的排序行为与内置指针保持一致。

回到我们原始的例子，如果需要根据 maximum speed 对 multiset<Widget> 排序，最后新创建一个仿函数类：

struct MaxSpeedCompare : public std::binary_function<Widget, Widget, bool>
{
    bool operator()(const Widget& lhs, const Widget& rhs) const
    {
        return lhs.maxSpeed() < rhs.maxSpeed();
    }
};

std::multiset<Widget, MaxSpeedCompare> widgets;

不要通过特化 less 误导其他程序员，若需要根据其他规则进行排序，重创建一个不命名为 less 的仿函数类便可。

Part Seven: Programming with the STL

Item 43：Prefer algorithm calls to hand-written loops

Item 44：Prefer member functions to algorithms with the same names

Item 45：Distinguish among count, find, binary search, lower_bound, upper_bound, and equal_range

Item 46：Consider function objects instead of functions as algorithm parameters

Item 47：Avoid producing write-only code

Item 48：Always #include the proper headers

Item 49：Learn to decipher STL-related compiler diagnostics

Item 50：Familiarize yourself with STL-related web sites