第五章. 算法

---

• 条款30：确保目标区间足够大

首先了解标准库中的一个算法：

template <class InputIterator, class OutputIterator, class UnaryOperation>
OutputIterator transform (InputIterator first1, InputIterator last1, OutputIterator result, UnaryOperation op);

transform将[first1, last1)区间中的每个元素，传入函数op，然后将返回的结果赋值给result所指向的元素
但是这个算法有一个非常容易错误的用法：

transform(values.begin(), values.end(), results.end(), func);

意在将values中的元素一一传入func()，然后将返回值依次放在results的末尾。

这个用法的错误在于，results.end()返回的迭代器及其之后并没有指向任何元素，这样只会给不存在的对象赋值。
正确的用法是使用back_inserter().

template <class Container>
back_insert_iterator<Container> back_inserter(Container& x);

将容器作为back_inserter的参数可以获得指向该容器末尾的一个back_insert_iterator，而这个末尾插入迭代器重载了赋值运算符：

back_insert_iterator<_Container>& operator=(typename _Container::const_reference _Val)
{   
    container->push_back(_Val);
    return (*this);
}

对这个迭代器赋值，即是向容器push_back一个元素。
所以正确的用法是这样：

transform(values.begin(), values.end(), back_inserter(results), func);

相对的，有尾插入就会有头插入，front_inserter()，赋值时会调用push_front，所以只能用在提供了该方法的deque和list容器上
inserter()则允许结果插入容器中的任意位置。
无论何时你使用一个要求指定目的区间的算法，确保目的区间已经足够大或者在算法执行时可以增加大小。
如果你选择增加大小，就使用插入迭代器。

---

• 条款31：了解各种和排序有关的选择

STL算法中用于排序的算法不止sort一个，本条款介绍了另外的几个：

template <class RandomAccessIterator>
void partial_sort (RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp);

partial_sort将[first, last)区间中，最好的(middle - first)个元素，排好序放在容器的[first, middle)区间中，comp()是判断是否更好的方法。
即把最好的n个元素按顺序放在容器前面，其他的无序。
实现方式是通过堆排序时，每次建堆可以获得一个最佳元素，持续n次后，将一共获得的n个最好元素按顺序放在容器前面。

template <class RandomAccessIterator, class Compare>
void nth_element (RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);

nth_element这个算法和partial_sort类似，但是放在最前面的n个元素不进行排序。
sort、partial_sort、nth_element这三个算法都是不稳定的排序算法（即不能保证值相同的元素在排序前后的顺序）.
稳定的排序算法是stable_sort，因为使用的归并排序。

template <class RandomAccessIterator, class Compare>
void stable_sort ( RandomAccessIterator first, RandomAccessIterator last,Compare comp );

还有一个算法是partition:

template <class BidirectionalIterator, class UnaryPredicate>
BidirectionalIterator partition (BidirectionalIterator first,BidirectionalIterator last, UnaryPredicate pred);

partition()重排[first, last)区间中的元素，以使满足pred条件(使pred返回true)的元素都在区间的开头，并返回重排后第一个不满足pred条件的元素的迭代器。
stable_partition则是partition的稳定版本。
算法sort、stable_sort、partial_sort和nth_element需要随机访问迭代器，所以无法用于list，而list提供了专属的list::sort用于稳定排序。

---

• 条款32.如果确实需要删除元素，则需要在remove这一类算法之后调用erase

我在条款9中说明了std::remove所做的操作，它并不删除某个元素，而是将不需被删除的元素放在容器的前端。
类似的算法还有unique，用于删除相邻的重复元素，它也不真的删除相邻重复元素，而是将相邻的不重复元素放在容器的前端，最后返回一个指向边界的迭代器。
所以如果需要真的删除其它元素，应该在remove、unique后调用erase.

---

• 条款33.对包含指针的容器使用remove这一类算法时要特别小心

还是std::remove的问题，如果容器中的指针指向的是动态分配的内存，在调用remove时会导致一些指针丢失，导致内存泄漏。
如果向容器中添加的是智能指针，那这个问题就不存在了，你可以放心的对容器使用erase-remove删除元素。

---

• 条款34.了解哪些算法要求使用排序的区间作为参数

搜索算法binary_search、lower_bound、upper_bound和equal_range(详见条款45)需要有序区间，因为它们使用二分法查找。
set_union、set_intersection、set_difference和set_symmetric_difference都需要有序区间。

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_union (InputIterator1 first1, InputIterator1 last1,InputIterator2 first2, InputIterator2 last2, OutputIterator result);

set_union将两个有序区间中的元素合并，重复的元素只保留一份。

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_intersection (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);

set_intersection将两个有序区间中共有的元素拷贝一份

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_difference (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);

set_difference将区间[first1, last1)中有但是区间[first2, last2)中没有的元素拷贝到result中。

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_symmetric_difference (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);

set_symmetric_difference将区间[first1, last1)中有但是区间[first2, last2)中没有,与区间[first2, last2)中有但是区间[first1, last1)中没有的元素都拷贝到result中。
这四个算法要求有序区间，是为了保证线性时间复杂度。

---

如有错误，欢迎指正