前言:
此刻各位老铁们对“std容器算法”大致比较注重,我们都想要学习一些“std容器算法”的相关资讯。那么小编也在网上搜集了一些有关“std容器算法””的相关文章,希望兄弟们能喜欢,小伙伴们一起来学习一下吧!本演示文稿的主要要点之一是不使用原始循环。相反,更喜欢使用现有的算法或编写“包装”此类循环的函数。我对此想法很好奇,并搜索了不错的代码示例。这是我在C ++ std库中使用算法的简短列表,这可能有助于编写更好的代码。
当然。在原始的“ C ++ Seasoning”演讲中,我无法跳过两个突出的例子:slide and collect。
插入排序
仅用两行代码!
for (auto i = start; i != end; ++i) std::rotate(std::upper_bound(start, i, *i), i, std::next(i));怎么运行的?
Rotate(first, middle, last)-取一个范围[first, last)并旋转它,以便该middle元素成为该范围中的第一个元素。
upper_bound-返回指向范围[first,last)大于的第一个元素的迭代器val。该范围应已排序(或至少已分区)。
这两个元素如何组合成插入类型?
std::upper_bound(start, i, *i)返回第一个元素的位置大于*i。然后,移动范围,使i-th元素成为第一位。
让我们看一个例子:
挺棒的!
快速分类
在堆栈溢出中发现:
template<class FwdIt, class Compare = std::less<>>void quickSort(FwdIt first, FwdIt last, Compare cmp = Compare{}){ auto const N = std::distance(first, last); if (N <= 1) return; auto const pivot = std::next(first, N / 2); std::nth_element(first, pivot, last, cmp); quickSort(first, pivot, cmp); quickSort(pivot, last, cmp); }怎么运行的?
我不会描述快速排序算法...您应该已经知道它是如何工作的!在此实现std::nth_element中,用于完成大部分工作。此函数对范围进行部分排序,以便将给定的n-th元素放置在适当的位置。元素之前的所有n-th元素都小于或等于元素之后的n-th元素。
滑动
肖恩·帕特恩(Sean Parent)的演讲示例:
template <typename It> auto slide(It f, It l, randIter p) -> std::pair<It, It>{ if (p < f) return { p, std::rotate(p, f, l) }; if (l < p) return { std::rotate(f, l, p), p }; return { f, l };}怎么运行的?
例如,您可以想象UI对话框上的项目列表。用户选择一个连续范围,然后算法采用该范围并将其移至列表的其他位置。
此功能使用std::rotate:向前或向后移动元素。它返回两个迭代器-新序列的开始和结束。在C ++ 11中std::rotate获得了新版本,现在可以将迭代器返回到pelement 的新位置。如果您对返回此迭代器对不感兴趣,则可以进一步简化此代码。
实施说明:
在GCC 4.9(及更低版本)std::rotate中,不返回迭代器,而仅返回void。因此,当前,此代码将无法在此处运行。
收集
肖恩·潘特(Sean Parent)演讲的另一个例子:
template <typename BiIt, typename UnPred> auto gather(BiIt f, BiIt l, BiIt p, UnPred s) -> std::pair <BiIt, BiIt>{ return { stable_partition(f, p, not1(s)), stable_partition(p, l, s) };}怎么运行的?
它的用例可以类似于slide:选择元素-使用谓词s(因此不需要此连续范围),然后将这些元素收集到一个范围中并将该范围移动到周围p。它返回所选范围的开始和结束。
UnPred是一个谓词,它返回是否选择给定元素。
std::stable_partition:来自cppreference
对给定范围内的元素进行重新排序,使谓词返回的所有元素都在谓词返回true的元素之前false。保留元素的相对顺序。
std::stable_partition 使用两次:
实施说明:
std::not1无法正确使用代码,因此建议使用简单的lambda。在Sean的评论中阅读更多内容。
弦装饰
发现在堆栈溢出
std::string trim(const std::string &s) { return trimLeft(trimRight(s));}std::string trimLeft(const std::string &s) { auto temp = s; temp.erase(std::begin(temp), std::find_if(std::begin(temp), std::end(temp), [](char c){return !std::isspace(c, std::locale()); })); return temp;}std::string trimRight(const std::string &s) { auto temp = s; temp.erase(std::find_if(std::rbegin(temp), std::rend(temp), [](char c){return !std::isspace(c, std::locale()); }).base(), std::end(temp)); return temp;}怎么运行的?
标准库的另一个漂亮用法:
为了修剪字符串,我们从右到左修剪(这是一个发现!)向左修剪:std::find_if将迭代器返回到字符串中的第一个非空格字符。然后我们删除那些字符。修剪右:也使用,std::find_if但是这次我们使用反向迭代器
注意:您还可以使用升压字符串算法使生活更轻松。
该代码的作用是什么?
while (std::next_permutation(start, end));
简单,一行代码...应该不错!但...
答:这是对容器进行排序的另一种“绝佳”方法-排列排序!但是请不要在家中使用它:)
复杂度:O((n + 1)!)
该算法是Bogosort和其他类似“排序”算法的变体。在Wiki上阅读更多内容。正如victor_zverovich所注意到的,在Bogosort中,下一个排列是随机选择的,但是std :: next_permutation在字典上提供了下一个排列上更大的排列。
总结
我已经展示了几个我认为不错的代码示例,这些示例中大量使用了C ++标准库中的算法。也许下一次,当我要编写一些丑陋的代码时,我会停下来思考一会儿,也许可以调用一些现有的算法/函数。
你知道一些更有趣的例子吗?
欢迎讨论
标签: #std容器算法