65.9K
CodeProject 正在变化。 阅读更多。
Home

前 5 个漂亮的 C++ std 算法示例

Bartlomiej Filipek
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.86/5 (58投票s)

2014 年 12 月 16 日

CPOL

4分钟阅读

viewsIcon

132935

downloadIcon

650

使用 C++ 标准库中的算法编写的精美代码示例。大量使用了现代 C++。

前段时间，我看了 CppCon 2013 上一个富有启发性的演讲：Sean Parent 的“C++ Seasoning”。这次演讲的主要观点之一是不要使用原始循环。取而代之的是，优先使用现有算法或编写“封装”这些循环的函数。我对这个想法感到好奇，并搜索了一些好的代码示例。这里是我从 C++ std 库中使用的算法的简短列表，希望能帮助你写出更好的代码。

当然。我不能跳过原始“C++ Seasoning”演讲中的两个突出示例：slide 和 gather。

计划

插入排序

仅用两行代码！

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 元素成为第一个。

让我们看一个例子

相当不错！

快速排序

来自 Stack Overflow

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 first, It last, It pos) -> std::pair<It, It>
{
    if (pos < first) return { pos, std::rotate(pos, frist, last) };
    if (last < pos) return { std::rotate(first, last, pos), pos };
    return { first, llast };
}

它是如何工作的？

例如，你可以想象一个 UI 对话框中的项目列表。用户选择一个连续的范围，然后算法将该范围移动到列表中的其他某个位置。

  • 此函数使用 std::rotate：向前或向后移动元素。
  • 它返回两个迭代器——新序列的开始和结束。在 C++11 中，std::rotate 有了一个新版本，现在可以返回 p 元素新位置的迭代器。
  • 如果你对返回这个迭代器对不感兴趣，你可以进一步简化这段代码。

实现说明

  • 在 GCC 4.9（及更早版本）中，std::rotate 不返回迭代器，只返回 void。所以目前，这段代码在那里将无法工作。

Gather (收集)

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 的评论中了解更多信息。

字符串去空格

来自 Stack Overflow

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;
}

它是如何工作的？

标准库的另一个精美用法

  • 为了修剪 string，我们先从右边修剪，然后从左边修剪（多么伟大的发现！）
  • 左修剪：std::find_if 返回字符串中第一个非空格字符的迭代器。然后我们删除这些字符。
  • 右修剪：也使用 std::find_if，但这次我们使用反向迭代器。

注意：你也可以使用 boost string 算法让生活更轻松。

奖励 :)

这段代码做了什么？

while (std::next_permutation(start, end));

简单，一行代码……应该很不错！但是……

答案：这是对容器进行排序的另一种“奇妙”的方法——置换排序！但请不要在家尝试。 :)

复杂度：O((n+1)!)

该算法是 Bogosort 和其他类似“排序”算法的一个变种。在 wiki 上了解更多。正如 victor_zverovich 所指出的，在 Bogosort 中，下一个置换是随机选择的，而 std::next_permutation 给出下一个字典序更大的置换。

总结

我展示了几个我认为不错的代码示例，其中大量使用了 C++ 标准库中的算法。也许下次，当我写一些丑陋的代码时，我会停下来，思考一分钟，看看是否有现有的算法/函数可以替代。

你知道更多有趣的例子吗？我的列表绝对不包含所有例子！

资源

© . All rights reserved.