龙空技术网

最佳5个C ++ std算法示例

奇牛编程 1673

前言:

此刻各位老铁们对“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容器算法