前言
STL在C++开发中的重要性无需多言。它设计精妙，性能卓越，功能方便。
大多数时候，它都易于使用。但利刃能开几分光，还要依赖使用者的修养。提修养，多读书。《Efficient STL》中给出了关于STL的50条建议。
这些规则分为以下七个部分：
-
$\color{blue}{【Container(容器)】}$
-
$\color{blue}{【vector\&string(列表和字符串)】}$
-
$\color{blue}{【associate container(关联型容器)】}$
-
$\color{blue}{【Iterator(迭代器)】}$
-
$\color{blue}{【Algorithms(算法)】}$
-
$\color{blue}{【Function(函数)】}$
-
$\color{blue}{【编码实践】}$
本文将介绍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<char>(inputFile)), istream_iterator<char>());
如果只是读入字符，不需要做复杂的选项校验，可以使用istreambuf_iterator，在作者的benchmark测试中可以获得40%的性能提升:
ifstream inputFile("interestingData.txt");
string fileData( (istreambuf_iterator(inputFile)), istreambuf_iterator());
算法
算法库的目标地址需要有足够的空间，如果需要放在目标vector结尾，需要使用back_inserter，而不是使用end()
std::vector<int> results;
transform( values.begin(), values.end(), results.end(), some_func);
//错误，results.end() 没有内存地址
transform( values.begin(), values.end(), back_inserter(results.end()), some_func );
//正确
关于排序的选择：
- 如果需要对vector, string, deque, array 进行完成的排序，可以使用sort或者stable_sort
- 如果需要vector, string, deque, array的最大，次大……第N大的数，可以使用partial_sort
- 如果需要vector, string, deque, array的前N大的数，或者仅仅是第N大的数，而不关心顺序，可以用nth_element
- 如果要判断vector, string, deque, array中有哪些元素符合某个条件，可以用partition或stable_partition
- 如果数据是一个链表类型，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<int> 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
使用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<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);
}
另外还可以用非stl的第三方函数库：
int ciStringCompare(const string &s1, const string &s2) {
return stricmp(s1.c_str(), s2.c_str());
}
STL不提供默认的copy_if函数，一种实现如下：
template<typename InputIterator, typename OutputIterator, typename Predicate>
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<double> ld;
double sum = accumulate(ld.begin(), ld.end(), 0.0);
//注意第三个参数需要写成0.0,默认double 类型
accumulate 还可以传入自定义的range处理函数：
vector<float> vf;
float product = accumulate(vf.begin(), vf.end(), 1.0, multiplies<float>());
// 连乘；
list<Point> lp;
Point avg = accumulate(lp.begin(), lp.end(), Point(0.0), PointAverage()); //求点的质心
class PointAverage:
public: binary_function<Point, Point, Point> {
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<Point, Point, Point> {
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<Point> lp;
Point avg = for_each(lp.begin(), lp.end(), PointAverage()).result(); //foreach之后计算结果
