「语法学习」C++ STL 实用函数

<!--index-menu-->

在 C++ 的 STL 里有很多高级实用的函数,甚至让人虎躯一震,它们对简化代码量很有帮助。

由于篇幅限制,参数列表中的参数类型全部省略。其中有 ? 的参数可以省略。

std::prev_permutation(__first, __last, ?__comp):得到序列 [__first, __last) 的上一个排列。时间复杂度 $O(n)$。

std::next_permutation(__first, __last, ?__comp):得到序列 [__first, __last) 的下一个排列。时间复杂度 $O(n)$。

std::sort(__first, __last, ?__comp):将序列 [__first, __last) 进行排序。时间复杂度 $O(n \log n)$。

std::stable_sort(__first, __last, ?__comp):同上。相同元素的相对位置不变。时间复杂度 $O(n \log n)$。

std::partition(__first, __last, __pred):将序列 [__first, __last) 重新排列,所有使谓词返回 true 的元素放在所有使谓词返回 false 的元素前面。时间复杂度 $O(n)$。

std::stable_partition(__first, __last, __pred):同上。相同元素的相对位置不变。时间复杂度 $O(n)$。

std::merge(__first1, __last1, __first2, __last2, __result, ?__comp):将序列 [__first1, __last1)[__first2, __last2) 合并成有序序列,并存放到序列 __result 中,该操作是稳定的。时间复杂度 $O(n)$。

std::inplace_merge(__first, __middle, __last, ?__comp):将序列 [__first, __middle)[__middle, __last) 合并成有序序列,该操作是稳定的。时间复杂度与缓存区大小有关:缓存区大小足够时为 $O(n)$,否则为 $O(n \log n)$。

std::nth_element(__first, __nth, __last, ?__comp):将序列 [__first, __last) 中第 __nth 小的元素放在排序序列上的位置,但是不保证其他元素有序。时间复杂度 $O(n)$。

std::prev(it, ?n = 1):返回迭代器 it 的第 n 个前驱,但是不改变其本身的值。时间复杂度与迭代器类型有关:一般情况为 $O(n)$,如果迭代器额外满足随机访问迭代器则复杂度为 $O(1)$。

std::next(it, ?n = 1):返回迭代器 it 的第 n 个后继,但是不改变其本身的值。时间复杂度与迭代器类型有关:一般情况为 $O(n)$,如果迭代器额外满足随机访问迭代器则复杂度为 $O(1)$。

std::advance(it, n):增加给定的迭代器 itn 个元素的步长,无返回值。若 n 为负,则迭代器自减。该情况下,it 必须满足双向迭代器的要求,否则行为未定义。时间复杂度与迭代器类型有关:一般情况为 $O(n)$,如果迭代器额外满足随机访问迭代器则复杂度为 $O(1)$。

std::distance(first, last):返回从迭代器 firstlast 的路程。若使用随机访问迭代器且 first 可从 last 抵达,则值可能为负。若迭代器不是随机访问迭代器,则若 last 不可从 first 通过(可以重复)自增 first 抵达,则行为未定义。若迭代器是随机访问迭代器,则若 last 不可从 first 抵达且 first 不可从 last 抵达,则行为未定义。时间复杂度与迭代器类型有关:一般情况为 $O(n)$,如果迭代器额外满足随机访问迭代器则复杂度为 $O(1)$。

函数原型 功能 时间复杂度
`std::prev_permutation(__first, __last, ?__comp)` 得到序列 `[__first, __last)` 的上一个排列。 $O(n)$。
`std::next_permutation(__first, __last, ?__comp)` 得到序列 `[__first, __last)` 的下一个排列。 $O(n)$。
`std::sort(__first, __last, ?__comp)` 将序列 `[__first, __last)` 进行排序。 $O(n \log n)$。
`std::stable_sort(__first, __last, ?__comp)` 同上。相同元素的相对位置不变。 $O(n \log n)$。
`std::partition(__first, __last, __pred)` 将序列 `[__first, __last)` 重新排列,所有使谓词返回 `true` 的元素放在所有使谓词返回 `false` 的元素前面。 $O(n)$。
`std::stable_partition(__first, __last, __pred)` 同上。相同元素的相对位置不变。 $O(n)$。
`std::merge(__first1, __last1, __first2, __last2, __result, ?__comp)` 将序列 `[__first1, __last1)` 和 `[__first2, __last2)` 合并成有序序列,并存放到序列 `__result` 中,该操作是稳定的。 $O(n)$。
`std::inplace_merge(__first, __middle, __last, ?__comp)` 将序列 `[__first, __middle)` 和 `[__middle, __last)` 合并成有序序列,该操作是稳定的。 时间复杂度与缓存区大小有关:缓存区大小足够时为 $O(n)$,否则为 $O(n \log n)$。
`std::nth_element(__first, __nth, __last, ?__comp)` 将序列 `[__first, __last)` 中第 `__nth` 小的元素放在排序序列上的位置,但是不保证其他元素有序。 $O(n)$。
`std::prev(it, ?n = 1)` 返回迭代器 `it` 的第 `n` 个前驱,但是不改变其本身的值。 时间复杂度与迭代器类型有关:一般情况为 $O(n)$,如果迭代器额外满足随机访问迭代器则复杂度为 $O(1)$。
`std::next(it, ?n = 1)` 返回迭代器 `it` 的第 `n` 个后继,但是不改变其本身的值。
`std::advance(it, n)` 增加给定的迭代器 `it` 以 `n` 个元素的步长,无返回值。若 `n` 为负,则迭代器自减。该情况下,`it` 必须满足双向迭代器的要求,否则行为未定义。
`std::distance(first, last)` 返回从迭代器 `first` 到 `last` 的路程。若使用随机访问迭代器且 `first` 可从 `last` 抵达,则值可能为负。若迭代器不是随机访问迭代器,则若 `last` 不可从 `first` 通过(可以重复)自增 `first` 抵达,则行为未定义。若迭代器是随机访问迭代器,则若 `last` 不可从 `first` 抵达且 `first` 不可从 `last` 抵达,则行为未定义。

2 条评论

  1. GoneTime

    qwq

  2. Langlangago

    强啊OωO

发表评论