前言

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();