程序设计实习: 9.5算法(续)

3. 删除算法 ：删除一个容器里的某些元素 删除 -- 不会使容器里的元素减少

将所有应该被删除的元素看做空位子

用留下的元素从后往前移, 依次去填空位子

元素往前移后, 它原来的位置也就算是空位子

也应由后面的留下的元素来填上

最后, 没有被填上的空位子, 维持其原来的值不变 删除算法不应作用于关联容器

算法复杂度都是O(n)的：

unique templateFwdIt unique(FwdIt first, FwdIt last); 用 == 比较是否等 templateFwdIt unique(FwdIt first, FwdIt last, Pred pr); 用 pr (x,y)为 true说明x和y相等 对[first,last) 这个序列中连续相等的元素, 只留下第一个 返回值是迭代器, 指向元素删除后的区间的最后一个元 素的后面

4. 变序算法 变序算法改变容器中元素的顺序 但是不改变元素的值 变序算法不适用于关联容器 算法复杂度都是O(n)的

stable_patition 把区间内满足某个条件的元素移到前面 不满足该条件的移到后面 而对这两部分元素, 分别保持它们原来的先后次序不变 random_shuffle templatevoid random_shuffle(RanIt first, RanIt last); 随机打乱[first,last) 中的元素, 适用于能随机访问的容器

reverse templatevoid reverse(BidIt first, BidIt last); 颠倒区间[first,last)顺序 next_permutation templatebool next_permutaion (Init first,Init last); 求下一个排列

5. 排序算法 比前面的变序算法复杂度更高, 一般是O(nlog(n)) 排序算法需要随机访问迭代器的支持 不适用于关联容器和list

sort 快速排序 templatevoid sort(RanIt first, RanIt last); 按升序排序 判断x是否应比y靠前, 就看 x < y 是否为true templatevoid sort(RanIt first, RanIt last, Pred pr); 按升序排序 判断x是否应比y靠前, 就看 pr(x,y) 是否为true

sort 实际上是快速排序, 时间复杂度 O(n*log(n))

平均性能最优

但是最坏的情况下, 性能可能非常差 如果要保证 “最坏情况下” 的性能, 那么可以使用

stable_sort

stable_sort 实际上是归并排序, 特点是能保持相等元素之间的 先后次序

在有足够存储空间的情况下, 复杂度为 n * log(n), 否则复杂度 为 n * log(n) * log(n)

stable_sort 用法和 sort相同。

排序算法要求随机存取迭代器的支持, 所以list不能使用 排序算法, 要使用list::sort

6. 有序区间算法 要求所操作的区间是已经从小到大排好序的 需要随机访问迭代器的支持 有序区间算法不能用于关联容器和list

binary_search 折半查找 要求容器已经有序且支持随机访问迭代器, 返回是否找到 templatebool binary_search(FwdIt first, FwdIt last, const T& val); 上面这个版本, 比较两个元素x, y 大小时, 看 x < y templatebool binary_search(FwdIt first, FwdIt last, const T& val, Pred pr); 上面这个版本, 比较两个元素x, y 大小时, 若 pr(x,y) 为true, 则 认为x小于y

lower_bound, uper_bound, equal_range lower_bound： templateFwdIt lower_bound(FwdIt first, FwdIt last, const T& val); 要求[first,last)是有序的 查找[first,last)中的, 最大的位置 FwdIt, 使得[first,FwdIt) 中所有的元素都比 val 小

upper_bound templateFwdIt upper_bound(FwdIt first, FwdIt last, const T& val); 要求[first,last)是有序的 查找[first,last)中的, 最小的位置 FwdIt, 使得[FwdIt,last) 中所有的元素都比 val 大

equal_range templatepairequal_range(FwdIt first, FwdIt last, const T& val); 要求[first,last)是有序的， 返回值是一个pair, 假设为 p, 则： [first,p.first) 中的元素都比 val 小 [p.second,last)中的所有元素都比 val 大 p.first 就是lower_bound的结果 p.last 就是 upper_bound的结果

merge templateOutIt merge(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt x); 用 < 作比较器 templateOutIt merge(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt x, Pred pr); 用 pr 作比较器 把[first1,last1), [ first2,last2) 两个升序序列合并, 形成第 3 个升序序列, 第3个升序序列以 x 开头

includes templatebool includes(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2); templatebool includes(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, Pred pr); 判断 [first2,last2)中的每个元素, 是否都在[first1,last1)中 第一个用 <作比较器 第二个用 pr 作比较器, pr(x,y) == true说明 x,y相等

set_difference templateOutIt set_difference(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt x); templateOutIt set_difference(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt x, Pred pr); 求出[first1,last1)中, 不在[first2,last2)中的元素, 放到 从 x 开始的地方 如果 [first1,last1) 里有多个相等元素不在[first2,last2)中, 则这多个元素也都会被放入x代表的目标区间里

set_intersection templateOutIt set_intersection(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt x); templateOutIt set_intersection(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt x, Pred pr); 求出[first1,last1)和[first2,last2)中共有的元素, 放到从x开始的 地方 若某个元素e 在[first1,last1)里出现 n1次, 在[first2,last2)里出 现n2次, 则该元素在目标区间里出现min(n1,n2)次

set_symmetric_difference templateOutIt set_symmetric_difference(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt x); templateOutIt set_symmetric_difference(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt x, Pred pr); 把两个区间里相互不在另一区间里的元素放入x开始的 地方

set_union templateOutIt set_union(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt x); 用<比较大小 templateOutIt set_union(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt x, Pred pr); 用 pr 比较大小 求两个区间的并, 放到以 x开始的位置 若某个元素e 在[first1,last1)里出现 n1次, 在[first2,last2)里 出现n2次, 则该元素在目标区间里出现max(n1,n2)次

bitset

In-Video Quiz 1. 下面的一些算法，哪个可以用于关联容器？ A)find B)sort C)remove D)random_shuffle