Effective_STL 阅读笔记(五)

引言

STL算法有的是对于单个数据的处理，有对于区间数据的处理。单个数据的处理算法如: remove,它们仅仅对单个数据负责，而区间数据则不同。算法需要对区间的所有数据进行处理，因此效率衡量也是极为重要的，那么这个效率是如何保证的呢？

STL算法

排序的区间参数

STL中对区间排序有需求的算法有:

binary_search  lower_bound
upper_bound    equal_range
set_union      set_intersection
set_difference set_symmetric_difference
merge          inplace_merge
includes

提供了有序区间，那么效率就有了保证。如set_union、set_intersection、set_difference、set_symmetric_difference它们的时间复杂度是线性的，如果用户提供的参数是一个非排序区间，就会导致算法无法在线性的时间内完成。
这里的排序还有一个要求，即是不可与算法的排序相冲突，举例而言： binary_search默认情况下，会假设区间为升序，而你去提供了一个降序的函数子，那么想要得到一个正确的结果显然不会那么容易。

copy_if算法

STL提供了11种copy算法，但独独没有提供copy_if算法。虽然没有提供，但我们也同样可以实现一个。
具体实现如下:

template <typename Inputiterator,
          typename Outputiterator,
          typename Predicate>
copy_if (Inputiterator begin, Inputiterator end, Outputiterator destBegin, Predicate p) {
  while (begin != end) {
    if (p(*begin)) *destBegin++ = *begin;
  }
  return destBegin;
}

区间统计

若要计算一个vector的总和，可以不再需要烦琐的手写for循环，而是使用STL提供的accumulate算法。

std::vector<int> v;
accumulate(v.begin(), v.end(), 0);

这样就可以十分快捷的计算出它的总和。但它不仅仅限制于此，它还可以实现计算字符的总长:

string::size_type
stringlengthSum(string::size_type sumSofar, const string& s) {
  return sumSofar + s.size();
}

set<string> ss;
...
string::size_type len =
  accumulate(ss.begin(), ss.end(), static_cast<string::size_type>(0), stringlengthSum);

这样一个简单的字符总数统计就完成了。

STL额外也提供了一个区间统计算法for_each(),字面上看去，就可以知道它会对区间的每个数据进行操作。是的，它是可以用于区间数据的合法。它不同于accumulate直接的返回值，for_each返回的是一个函数拷贝，使用上也不如accumulate。

结语

STL中的算法需要不断去使用与学习，阅读只不过帮助我们更好的跳过使用中的暗坑。真正的理解与使用，仍需大量的实践累积。