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

本演示文稿的主要要點之一是不使用原始循環

當然。在原始的“ C ++ Seasoning”演講中，我無法跳過兩個突出的例子：slide and collect。

插入排序

僅用兩行代碼！

<code>for (auto i = start; i != end; ++i)
    std::rotate(std::upper_bound(start, i, *i), i, std::next(i));
/<code>

怎麼運行的？

Rotate(first, middle, last)-取一個範圍[first, last)並旋轉它，以便該middle元素成為該範圍中的第一個元素。

upper_bound-返回指向範圍[first,last)大於的第一個元素的迭代器val。該範圍應已排序（或至少已分區）。

這兩個元素如何組合成插入類型？

std::upper_bound(start, i, *i)返回第一個元素的位置大於*i。然後，移動範圍，使i-th元素成為第一位。

讓我們看一個例子：

挺棒的！

快速分類

在堆棧溢出中發現：

<code>template<class>>
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); 
}
/<class>/<code>

怎麼運行的？

我不會描述快速排序算法...您應該已經知道它是如何工作的！在此實現std::nth_element中，用於完成大部分工作。此函數對範圍進行部分排序，以便將給定的n-th元素放置在適當的位置。元素之前的所有n-th元素都小於或等於元素之後的n-th元素。

滑動

肖恩·帕特恩（Sean Parent）的演講示例：

<code>template <typename> 
auto slide(It f, It l, randIter p) -> std::pair
{
    if (p < f) return { p, std::rotate(p, f, l) }; 

    if (l < p) return { std::rotate(f, l, p), p };
    return { f, l };
}
/<typename>/<code>

怎麼運行的？

例如，您可以想象UI對話框上的項目列表。用戶選擇一個連續範圍，然後算法採用該範圍並將其移至列表的其他位置。

• 此功能使用std::rotate：向前或向後移動元素。
• 它返回兩個迭代器-新序列的開始和結束。在C ++ 11中std::rotate獲得了新版本，現在可以將迭代器返回到pelement 的新位置。
• 如果您對返回此迭代器對不感興趣，則可以進一步簡化此代碼。

實施說明：

• 在GCC 4.9（及更低版本）std::rotate中，不返回迭代器，而僅返回void。因此，當前，此代碼將無法在此處運行。

收集

肖恩·潘特（Sean Parent）演講的另一個例子：

<code>template <typename> 
auto gather(BiIt f, BiIt l, BiIt p, UnPred s) -> std::pair <biit>
{
    return { stable_partition(f, p, not1(s)), 
             stable_partition(p, l, s) };
}
/<biit>/<typename>/<code>

怎麼運行的？

它的用例可以類似於slide：選擇元素-使用謂詞s（因此不需要此連續範圍），然後將這些元素收集到一個範圍中並將該範圍移動到周圍p。它返回所選範圍的開始和結束。

UnPred是一個謂詞，它返回是否選擇給定元素。

std::stable_partition：來自cppreference

對給定範圍內的元素進行重新排序，使謂詞返回的所有元素都在謂詞返回true的元素之前false。保留元素的相對順序。

std::stable_partition 使用兩次：

實施說明：

• std::not1無法正確使用代碼，因此建議使用簡單的lambda。在Sean的評論中閱讀更多內容。

弦裝飾

發現在堆棧溢出

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

怎麼運行的？

標準庫的另一個漂亮用法：

• 為了修剪字符串，我們從右到左修剪（這是一個發現！）
• 向左修剪：std::find_if將迭代器返回到字符串中的第一個非空格字符。然後我們刪除那些字符。
• 修剪右：也使用，std::find_if但是這次我們使用反向迭代器

注意：您還可以使用升壓字符串算法使生活更輕鬆。

該代碼的作用是什麼？

<code>while (std::next_permutation(start, end));
/<code>

簡單，一行代碼...應該不錯！但...

答：這是對容器進行排序的另一種“絕佳”方法-排列排序！但是請不要在家中使用它:)

複雜度：O（（n + 1）！）

該算法是Bogosort和其他類似“排序”算法的變體。在Wiki上閱讀更多內容。正如victor_zverovich所注意到的，在Bogosort中，下一個排列是隨機選擇的，但是std :: next_permutation在字典上提供了下一個排列上更大的排列。

總結

我已經展示了幾個我認為不錯的代碼示例，這些示例中大量使用了C ++標準庫中的算法。也許下一次，當我要編寫一些醜陋的代碼時，我會停下來思考一會兒，也許可以調用一些現有的算法/函數。

你知道一些更有趣的例子嗎？

歡迎討論

閱讀更多 我臉上有bug 的文章

關鍵字: 最佳 示例 算法