std::sort
-
将容器元素进行排序, 会改变容器顺序, 默认从小到大排序 void sort( RandomIt first, RandomIt last );
-
comp: returns true if the first argument is less than the second. struct {
bool operator()(int a, int b) const { return a < b; }
} customLess;
-
算法复杂度: nlogn
std::partial_sort
-
将容器中的[first, middle)元素进行排序, 会改变容器顺序, 默认从小到大排序 void partial_sort( RandomIt first, RandomIt middle, RandomIt last );
-
comp: returns true if the first argument is less than the second. -
算法复杂度: Approximately (last-first)log(middle-first) applications of cmp.
std::nth_element
-
找到容器中假设从小到大排序的第n个元素, 会改变容器顺序, 一般用于找中位数 void nth_element( RandomIt first, RandomIt nth, RandomIt last );
-
comp: returns true if the first argument is less than the second. -
算法复杂度: Linear in std::distance(first, last) on average.
std::partition
-
将容器中满足条件的放在一边, 不满足条件的放在另一边, 返回两边中间另一边开始前的指针, 会改变容器顺序 -
UnaryPredicate: unary predicate which returns true if the element should be ordered before other elements. auto it = std::partition(v.begin(), v.end(), [](int i){return i % 2 == 0;});
-
算法复杂度: n
std::lower_bound
-
找到容器中第一个大于等于一个值的元素, 不会改变容器顺序, 要求容器有序
Returns an iterator pointing to the first element in the range [first, last) that does not satisfy element < value (or comp(element, value)),
(i.e. greater or equal to), or last if no such element is found. ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value );
-
comp: binary predicate which returns true if the first argument is less than the second. auto prc_info = std::lower_bound(prices.begin(), prices.end(), to_find,
[](const PriceInfo& info, double value)
{
return info.price < value;
});
-
算法复杂度: logn
std::upper_bound
-
找到容器中第一个大于一个值的元素, 不会改变容器顺序, 要求容器有序
Returns an iterator pointing to the first element in the range [first, last) such that value < element
(or comp(value, element)) is true (i.e. strictly greater), or last if no such element is found. ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value );
-
comp: binary predicate which returns true if the first argument is less than the second. auto prc_info = std::upper_bound(prices.begin(), prices.end(), to_find,
[](double value, const PriceInfo& info)
{
return value < info.price;
});
-
算法复杂度: logn
std::equal_range
-
Returns a range containing all elements equivalent to value in the range [first, last). 要求容器有序 Possible implementation: template<class ForwardIt, class T>
std::pair<ForwardIt, ForwardIt>
equal_range(ForwardIt first, ForwardIt last, const T& value) {
return std::make_pair(std::lower_bound(first, last, value),
std::upper_bound(first, last, value));
}
-
comp: binary predicate which returns true if the first argument is less than the second. -
算法复杂度: 2 * logn
std::binary_search
-
二分法查找element equivalent to value, 要求容器有序, 不会改变容器顺序
Possible implementation: template<class ForwardIt, class T>
bool binary_search(ForwardIt first, ForwardIt last, const T& value)
{
first = std::lower_bound(first, last, value);
return (!(first == last) && !(value < *first));
}
-
comp: binary predicate which returns true if the first argument is less than the second. -
算法复杂度: logn
std::transform
-
将一个容器中的元素施加某种算法后, 并作用于另一个容器上 -
unary_op/binary_op: std::transform(s.cbegin(), s.cend(),
s.begin(), // write to the same location
[](unsigned char c) { return std::toupper(c); });
std::transform(s.cbegin(), s.cend(), std::back_inserter(ordinals),
[](unsigned char c) { return c; });
std::transform(ordinals.cbegin(), ordinals.cend(), ordinals.cbegin(),
ordinals.begin(), std::plus<>{});
-
算法复杂度: n
std::unique
-
去除器中相邻的两个equivalent elements中的一个, 通常与erase联合使用, 完成真正意义上的删除, 不要求容器有序 left_boundary.erase(std::unique(left_boundary.begin(), left_boundary.end()),
left_boundary.end());
-
BinaryPredicate: binary predicate which returns true if the elements should be treated as equal. -
算法复杂度: n
std::remove/std::remove_if
-
去除容器中满足特定条件的元素, 通常与erase联合使用, 完成真正意义上的删除, 不要求容器有序 auto noSpaceEnd = std::remove(str1.begin(), str1.end(), ' ');
str1.erase(noSpaceEnd, str1.end());
-
UnaryPredicate: unary predicate which returns true if the element should be removed. str2.erase(std::remove_if(str2.begin(),
str2.end(),
[](unsigned char x){return std::isspace(x);}),
str2.end());
-
算法复杂度: n
std::for_each
-
对一个容器循环调用某个函数 std::for_each(nums.begin(), nums.end(), [](int &n){ n++; });
因为c++11引入了for(auto var : vars)基于范围的for循环语法, 使得for_each的语义表达相形见绌了许多, 大多数情况可以不用for_each -
算法复杂度: n
std::min_element/std::max_element
-
找到容器中最大/最小元素, 默认使用<比较 -
comp: comparison function object (i.e. an object that satisfies the requirements of Compare) which returns true if the first argument is less than the second. result = std::max_element(v.begin(), v.end(), [](int a, int b) {
return std::abs(a) < std::abs(b);
});
-
算法复杂度: n
|