STL闪电来自EfficientSTL的最佳实践（迭代器算法）

　　前言
　　STL在C++开发中的重要性无需多言。它设计精妙，性能卓越，功能方便。其余介绍参见：STL闪电：来自《Efficient STL》的最佳实践(容器篇) ， STL闪电：来自《Efficient STL》的最佳实践(数组/字符串/哈希表)
　　本文将介绍Iterator和Algorithm方面的内容。迭代器应该尽可能地使用iterator作为迭代器。
　　container包含四种类型的迭代器：iterator, const iterator, reverse iterator, const reverse iterator; 而insert 和 erase接口只接收container iterator；各种迭代器支持的类型转换关系如下：
　　iterator可被转换为另外的迭代器类型，可以方便地进行运算操作；iterator和const iterator是两种不同的类型，需要用advance和distance进行转换。
　　考虑下面的代码：typedef sometype::iterator iter;
　　typedef sometype::const_iterator const_iter;
　　const_iter ci;
　　iter i(ci);
　　iter i(const_cast(ci));
　　如果sometype是vector或者string, 因为iterator通常是T*的类型别名，转换能够成立；对deque，list，hash_map等类型则不能；
　　正确的转换方式如下：iter i = some_instance.begin();
　　advance(i, distance(i, ci));调用reverse_iterator.base()可以获得相应的iterator，它们的指针关系如图：
　　ri到rbegin()的offset是4，对应的base()里，i到begin()的offset也是4；
　　如果要进行对应位置的操作，需要计算位移：
　　v.erase((++ri).base()); // erase可以用istream_iterator将文件内容拷贝到string:ifstream inputFile(＂a.txt＂);
　　inputFile.unsetf(ios::skipws); //保留空格
　　string fileData((istream_iterator(inputFile)), istream_iterator());
　　如果只是读入字符，不需要做复杂的选项校验，可以使用istreambuf_iterator，在作者的benchmark测试中可以获得40%的性能提升:ifstream inputFile(＂interestingData.txt＂);
　　string fileData( (istreambuf_iterator(inputFile)), istreambuf_iterator());算法算法库的目标地址需要有足够的空间，如果需要放在目标vector结尾，需要使用back_inserter，而不是使用end()std::vector results;
　　transform( values.begin(), values.end(), results.end(), some_func);
　　//错误，results.end() 没有内存地址
　　transform( values.begin(), values.end(), back_inserter(results.end()), some_func );关于排序的选择：
　　1）如果需要对vector, string, deque, array 进行完成的排序，可以使用sort或者stable_sort
　　2) 如果需要vector, string, deque, array的最大，次大……第N大的数，可以使用partial_sort
　　3) 如果需要vector, string, deque, array的前N大的数，或者仅仅是第N大的数，而不关心顺序，可以用nth_element
　　4) 如果要判断vector, string, deque, array中有哪些元素符合某个条件，可以用partition或stable_partition
　　5) 如果数据是一个链表类型，partition和stable_partition仍然可以用；list::sort可以代替sort和stable_sort；如果是需要partial_sort或nth_element，需要额外的代码实现，比如把数据拷贝进vector并进行排序；
　　它们消耗的资源依次排列如下：
　　partition > stable_partition > nth_element > partial_sort > sort > stable_sort要删除元素的话，仅用remove-like的函数是不够的，还需要加上erase
　　template Forwardlterator remove(Forwardlterator first, Forwardlterator last, const T& value);
　　remove只接受iterator，也只返回iterator，不知道具体的容器是什么，所以无法从容器里删除数据；获得iterator后需要再调用对象的erase成员函数进行删除。
　　remove的作用：将不需要remove的元素前移，并返回新的end位置；
　　正确的删除方法：std::vector v;
　　v.erase(remove(v.begin(), v.end(), 99), v.end()); // 删除所有值为99的元素；
　　list.remove合并了erase和std::remove。如果容器里存储的是指针类型，使用remove的时候要注意是否释放资源；最好存储智能指针的类型，析构时可以自动释放资源；要求数组有序的算法有：binary_search, lower_bound, upper_bound, equal_range, set_union, set_intersection, set_difference, set_symmetric_difference, merge, inplace_merge, includes使用mismatch和lexicographical_compare实现大小写不敏感的字符串比较函数
　　mismatch：参数mismatch(s1.begin(), s1.end(), s2.begin(), predictor), 它会返回第一个不匹配的pair，可以根据pair返回的iterator值判断是否相等；
　　lexicographical_compare: 一个strcmp的更通用的版本，如果第一个区间短于第二个区间，或者比较函数返回true，则compare函数返回true；实现自定义的compare函数即可bool ciCharLess(char c1, char c2) {
　　return tolower(static_cast(c1)) < tolower(static_cast(c2));
　　}
　　bool ciStringCompare(const string& s1, const string& s2) {
　　return lexicographical_compare(s1.begin(), s1.end(), s2.begin(), s2.end(), ciCharLess);
　　}
　　另外还可以用非stl的第三方函数库：int ciStringCompare(const string &s1, const string &s2) {
　　return stricmp(s1.c_str(), s2.c_str());
　　}STL不提供默认的copy_if函数，一种实现如下：template
　　OutputIterator copy_if(InputIteratro begin, InputIterator end, OutputIterator destBegin, Predicate p) {
　　while (begin != end) {
　　if (p(*begin)) *destBegin++ = *begin;
　　++begin;
　　}
　　return destBegin;
　　}可以用accumulate和for_each对一段区间求和list ld;
　　double sum = accumulate(ld.begin(), ld.end(), 0.0);
　　//注意第三个参数需要写成0.0,默认double 类型
　　accumulate 还可以传入自定义的range处理函数：vector vf;
　　float product = accumulate(vf.begin(), vf.end(), 1.0, multiplies());
　　// 连乘；
　　list lp;
　　Point avg = accumulate(lp.begin(), lp.end(), Point(0.0), PointAverage()); //求点的质心
　　class PointAverage:
　　public: binary_function {
　　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;
　　}
　　for_each的传参和accumulate类似，但for_each主要对每个元素起作用；它的返回类型是函数对象，需要用额外的对象获取结果：//用for_each 求点的质心
　　class PointAverage:
　　public: binary_function {
　　public:
　　PointAverage():xSum(0), ySum(0), numPoints(0) {}
　　void operator() (const Point& avgSoFar, const Point& p) {
　　++numPoints; xSum += p.x; ySum += p.y;
　　}
　　const Point result() const {
　　return Point(xSum / numPoints, ySum / numPoints);
　　}
　　private:
　　size_t numPoints;
　　double xSum;
　　double ySum;
　　}
　　list lp;
　　Point avg = for_each(lp.begin(), lp.end(), PointAverage()).result();