C++ Boost Algorithm算法超詳細精講

更新時間：2022年10月31日 13:59:26 作者：無水先生

Boost.Algorithm 提供了補充標準庫算法的算法。與 Boost.Range 不同，Boost.Algorithm 沒有引入新概念。 Boost.Algorithm 定義的算法類似于標準庫中的算法

一、說明Boost.Algorithm

請注意，其他 Boost 庫提供了許多算法。例如，您會在 Boost.StringAlgorithms 中找到處理字符串的算法。 Boost.Algorithm 提供的算法不受特定類的約束，例如 std::string。與標準庫中的算法一樣，它們可以與任何容器一起使用。

二、示例

示例 29.1。使用 boost::algorithm::one_of_equal() 測試一個值

#include <boost/algorithm/cxx11/one_of.hpp>
#include <array>
#include <iostream>
using namespace boost::algorithm;
int main()
{
  std::array<int, 6> a{{0, 5, 2, 1, 4, 3}};
  auto predicate = [](int i){ return i == 4; };
  std::cout.setf(std::ios::boolalpha);
  std::cout << one_of(a.begin(), a.end(), predicate) << '\n';
  std::cout << one_of_equal(a.begin(), a.end(), 4) << '\n';
}

boost::algorithm::one_of() 測試一個條件是否只滿足一次。要測試的條件作為謂詞傳遞。在示例 29.1 中，對 boost::algorithm::one_of() 的調用返回 true，因為數字 4 在 a 中僅存儲一次。

要測試容器中的元素是否相等，請調用 boost::algorithm::one_of_equal()。你沒有傳遞謂詞。相反，您傳遞一個值以與 boost::algorithm::one_of_equal() 進行比較。在示例 29.1 中，對 boost::algorithm::one_of_equal() 的調用也返回 true。

boost::algorithm::one_of() 是對 std::all_of()、std::any_of() 和 std::none_of() 算法的補充，這些算法是使用 C++11 添加到標準庫中的。但是，Boost.Algorithm 為開發(fā)環(huán)境不支持 C++ 的開發(fā)人員提供了函數 boost::algorithm::all_of()、boost::algorithm::any_of() 和 boost::algorithm::none_of() 11.您可以在頭文件 boost/algorithm/cxx11/all_of.hpp、boost/algorithm/cxx11/any_of.hpp 和 boost/algorithm/cxx11/none_of.hpp 中找到這些算法。

Boost.Algorithm 還定義了以下函數：boost::algorithm::all_of_equal()、boost::algorithm::any_of_equal() 和 boost::algorithm::none_of_equal()。

Boost.Algorithm 提供了更多來自 C++11 標準庫的算法。例如，您可以訪問 boost::algorithm::is_partitioned()、boost::algorithm::is_permutation()、boost::algorithm::copy_n()、boost::algorithm::find_if_not() 和 boost::算法::iota()。這些函數的工作方式與 C++11 標準庫中的同名函數類似，并且是為不使用 C++11 的開發(fā)人員提供的。但是，Boost.Algorithm 提供了一些對 C++11 開發(fā)人員也很有用的函數變體。

示例 29.2。 C++11 算法的更多變體

#include <boost/algorithm/cxx11/iota.hpp>
#include <boost/algorithm/cxx11/is_sorted.hpp>
#include <boost/algorithm/cxx11/copy_if.hpp>
#include <vector>
#include <iterator>
#include <iostream>
using namespace boost::algorithm;
int main()
{
  std::vector<int> v;
  iota_n(std::back_inserter(v), 10, 5);
  std::cout.setf(std::ios::boolalpha);
  std::cout << is_increasing(v) << '\n';
  std::ostream_iterator<int> out{std::cout, ","};
  copy_until(v, out, [](int i){ return i > 12; });
}

Boost.Algorithm 在頭文件 boost/algorithm/cxx11/iota.hpp 中提供了 C++11 算法 boost::algorithm::iota()。此函數生成順序遞增的數字。它需要兩個迭代器用于容器的開頭和結尾。然后容器中的元素會被順序增加的數字覆蓋。

示例 29.2 使用 boost::algorithm::iota_n() 代替 boost::algorithm::iota()。此函數需要一個迭代器將數字寫入。要生成的數字數量作為第三個參數傳遞給 boost::algorithm::iota_n()。

boost::algorithm::is_increasing() 和 boost::algorithm::is_sorted() 在頭文件 boost/algorithm/cxx11/is_sorted.hpp 中定義。 boost::algorithm::is_increasing() 與 boost::algorithm::is_sorted() 具有相同的功能，但函數名稱更清楚地表示該函數檢查值是否按升序排列。頭文件還定義了相關的函數 boost::algorithm::is_decreasing()。

在示例 29.2 中，v 直接傳遞給 boost::algorithm::is_increasing()。 Boost.Algorithm 提供的所有函數都有一個基于范圍操作的變體。容器可以直接傳遞給這些函數。

boost::algorithm::copy_until() 在 boost/algorithm/cxx11/copy_if.hpp 中定義。這是 std::copy() 的另一個變體。 Boost.Algorithm 還提供了 boost::algorithm::copy_while()。

示例 29.2 作為 boost::algorithm::is_increasing() 的結果顯示為 true，并且 boost::algorithm::copy_until() 將數字 10、11 和 12 寫入標準輸出。

示例 29.3。來自 Boost.Algorithm 的 C++14 算法

#include <boost/algorithm/cxx14/equal.hpp>
#include <boost/algorithm/cxx14/mismatch.hpp>
#include <vector>
#include <iostream>
using namespace boost::algorithm;
int main()
{
  std::vector<int> v{1, 2};
  std::vector<int> w{1, 2, 3};
  std::cout.setf(std::ios::boolalpha);
  std::cout << equal(v.begin(), v.end(), w.begin(), w.end()) << '\n';
  auto pair = mismatch(v.begin(), v.end(), w.begin(), w.end());
  if (pair.first != v.end())
    std::cout << *pair.first << '\n';
  if (pair.second != w.end())
    std::cout << *pair.second << '\n';
}

除了來自 C++11 標準庫的算法，Boost.Algorithm 還定義了很可能會添加到 C++14 標準庫中的算法。示例 29.3 使用了其中兩個函數的新變體，boost::algorithm::equal() 和 boost::algorithm::mismatch()。與自 C++98 以來已成為標準庫一部分的同名函數相比，將四個迭代器（而不是三個）傳遞給這些新函數。示例 29.3 中的算法不期望第二個序列包含與第一個序列一樣多的元素。

boost::algorithm::equal() 返回一個 bool，boost::algorithm::mismatch() 返回一個 std::pair 中的兩個迭代器。第一個和第二個是指第一個和第二個序列中第一個不匹配的元素。這些迭代器也可以引用序列的結尾。

示例 29.3 將 false 和 3 寫入標準輸出。 false 是 boost::algorithm::equal() 的返回值，3 w 中的第三個元素。因為 v 和 w 中的前兩個元素相等，所以 boost::algorithm::mismatch() 首先返回到 v 末尾的迭代器，然后返回到 w 的第三個元素的迭代器。因為 first 指的是 v 的結尾，所以迭代器沒有被取消引用，也沒有輸出。

示例 29.4。使用 boost::algorithm::hex() 和 boost::algorithm::unhex()

#include <boost/algorithm/hex.hpp>
#include <vector>
#include <string>
#include <iterator>
#include <iostream>
using namespace boost::algorithm;
int main()
{
  std::vector<char> v{'C', '+', '+'};
  hex(v, std::ostream_iterator<char>{std::cout, ""});
  std::cout << '\n';
  std::string s = "C++";
  std::cout << hex(s) << '\n';
  std::vector<char> w{'4', '3', '2', 'b', '2', 'b'};
  unhex(w, std::ostream_iterator<char>{std::cout, ""});
  std::cout << '\n';
  std::string t = "432b2b";
  std::cout << unhex(t) << '\n';
}

Example29.4

示例 29.4 使用了兩個函數 boost::algorithm::hex() 和 boost::algorithm::unhex()。這些函數是根據數據庫系統(tǒng) MySQL 中的同名函數設計的。它們將字符轉換為十六進制值或將十六進制值轉換為字符。

示例 29.4 將帶有字符“C”、“+”和“+”的向量 v 傳遞給 boost::algorithm::hex()。此函數需要一個迭代器作為第二個參數來寫入十六進制值。該示例將“C”的 43 和“+”的兩個實例的 2B（兩次）寫入標準輸出。對 boost::algorithm::hex() 的第二次調用執(zhí)行相同的操作，只是“C++”作為字符串傳遞，而“432B2B”作為字符串返回。

boost::algorithm::unhex() 與 boost::algorithm::hex() 相反。如果示例 29.4 中的數組 w 使用六個十六進制值傳遞，則三對值中的每一對都被解釋為 ASCII 碼。當六個十六進制值作為字符串傳遞時，第二次調用 boost::algorithm::unhex() 也會發(fā)生同樣的情況。在這兩種情況下，C++ 都被寫入標準輸出。

Boost.Algorithm 提供了更多的算法。例如，有幾種字符串匹配算法可以有效地搜索文本。該文檔包含所有可用算法的概述。