第五章. 算法
-
条款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中。
这四个算法要求有序区间,是为了保证线性时间复杂度。
如有错误,欢迎指正