C++ 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 为开发环境不支持 C++ 的开发人员提供了函数 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 的开发人员提供的。但是，Boost.Algorithm 提供了一些对 C++11 开发人员也很有用的函数变体。

示例 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()。这些函数是根据数据库系统 MySQL 中的同名函数设计的。它们将字符转换为十六进制值或将十六进制值转换为字符。

示例 29.4 将带有字符“C”、“+”和“+”的向量 v 传递给 boost::algorithm::hex()。此函数需要一个迭代器作为第二个参数来写入十六进制值。该示例将“C”的 43 和“+”的两个实例的 2B（两次）写入标准输出。对 boost::algorithm::hex() 的第二次调用执行相同的操作，只是“C++”作为字符串传递，而“432B2B”作为字符串返回。

boost::algorithm::unhex() 与 boost::algorithm::hex() 相反。如果示例 29.4 中的数组 w 使用六个十六进制值传递，则三对值中的每一对都被解释为 ASCII 码。当六个十六进制值作为字符串传递时，第二次调用 boost::algorithm::unhex() 也会发生同样的情况。在这两种情况下，C++ 都被写入标准输出。

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

练习

使用 Boost.Algorithm 中的函数以升序将数字 51 到 56 分配给具有六个元素的数组。将数组中的数字解释为十六进制值，将它们转换为字符并将结果写入标准输出。