Effective STL 中文版记录（六）

Effective STL 章节（六）

——50条有效使用STL的经验(37/50)
STL算法专项

文章目录

Effective STL 章节（六）
第三十条、确保目标空间足够大
第三十一条、了解各种与排序有关的选择
第三十二条、如果确实需要删除元素，则需要在remove这一类算法后调用erase
第三十三条、对包含指针的容器使用remove这一类算法时要特别小心
第三十四条、了解哪些算法要求使用排序的区间作为参数
第三十五条、通过mismatch或lexicographical_compare实现简单的忽略大小写的字符串比较
第三十六条、理解copy_if算法的正确实现
第三十七条、使用accumulate或者for_each进行区间统计

第三十条、确保目标空间足够大

首先明确一点，这里的算法指的是STL库中提供的算法函数，如sort，transform等，包含在头文件algorithm中

当使用算法对容器进行插入操作时，需要保证容器的容量足够大，或者保证容器容量会跟着算法的需求而扩大

如果需要再算法执行过程中增加容量，需要使用插入型迭代器

第三十一条、了解各种与排序有关的选择

algorithm提供了很多种排序算法，常见的就是

sort(v.begin(), v.end(), cmp);

定义cmp，表示排序判断条件，遍历整个容器v即可对v排序，同样的有函数stable_sort也能够做到这一功能

stable_sort能够保证等价元素的相对位置在排序时不发生改变

另外有

partial_sort(v.begin(), v.begin()+20, v.end(), cmp);
nth_element(v.begin(), v.begin()+19, v.end(), cmp);

来进行局部排序，都是将最好的20个元素放在v的前20位中

区别在于partial_sort会对这20个元素排序，而nth_element不会

还有

partition(v.begin(), v.end(), threshold);

通过定义threshold函数来设定一个阈值，高于这个阈值的会被放在v的前面，函数返回第一个低于阈值的元素迭代器

同理，它也有stable版本，即stable_partition

特别的，list不能用sort，所以有特定的函数list::sort来完成这一行为

根据使用情况来选择排序算法

第三十二条、如果确实需要删除元素，则需要在remove这一类算法后调用erase

这条是为了说，remove并不会真的删除元素，因为remove并不知道容器是哪个

实际上remove只会把需要删除的元素用后面的元素覆盖，整体前移，并不会改变整个容器的大小

std::vector<int> vec = {1, 2, 3, 4, 3, 5, 3};
auto new_end = std::remove(vec.begin(), vec.end(), 3);  // 此时vector是：1 2 4 5 3 5 3
// new_end 此时等价于 vec.begin() + 4

所以是为了强调，不要试图用一个通用的算法对特别的容器进行增删减改操作，一定remove后调用容器对应的删除函数

第三十三条、对包含指针的容器使用remove这一类算法时要特别小心

上条所说的，remove会对元素进行覆盖，所以如果当容器存的是指针，调用remove就会导致一些指针被覆盖

然而这些指针指向的数据并未被释放，然而你也再也无法找到它们了，这就导致了内存泄漏

std::vector<int> vec = {1, 2, 3, 4, 3, 5, 3};
auto new_end = std::remove(vec.begin(), vec.end(), 3);  // 此时vector是：1 2 4 5 3 5 3
// 原本的vec第三位的3，已经永远的丢失了，如果它是指针，那它指向的内容也永远找不到了

解决方法就是在remove之前就先把这些内容释放掉，再remove，并调用erase

第三十四条、了解哪些算法要求使用排序的区间作为参数

这条就是纯工具书的感觉了，一般也用不到，需要提示的是unique虽然不要求，但是它常常与排序区间一起使用

第三十五条、通过mismatch或lexicographical_compare实现简单的忽略大小写的字符串比较

知道有这两条函数即可，一般情况下都是使用strcmp进行比较，忽略大小写的话，也可以将两个字符串拷贝，都变成小写再比较

第三十六条、理解copy_if算法的正确实现

该函数的目的是：当满足某个条件，就copy，原本是STL库函数，后来被移除了，想用就要自己写

一个正确的实现是：

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;
}