Boost库学习笔记（二）算法模块-C++11标准

一、综述

Boost.Algorithm是一系列人通用推荐算法的集合，虽然有用的通用算法很多，但是为了保证质量和体积，并不会将太多通用算法通过审查测试添加进来。

Boost.Algorithm依赖Boost.Range, Boost.Assert, Boost.Array, Boost.TypeTraits, and Boost.StaticAssert.

二、搜索算法

Boyer-Moore搜索

**包含头文件：**boyer_moore.hpp

**功能：**完成在一个序列中搜索值

其为1977年十月在ACM大会上提出的算法，属于字符串部分匹配的标准范例，是一种非常有效的字符串匹配算法。Boyer-Moore算法需要两个匹配表来使得算法的表现更好，，这两个表是取决于要搜索的模式。

被搜索的字串被称为“模式”，搜索序列称为“语料库”

接口：

其接口有两种：

一种是对象接口

template <typename patIter>
class boyer_moore {
public:
    boyer_moore ( patIter first, patIter last );
    ~boyer_moore ();
    template <typename corpusIter>
    pair<corpusIter, corpusIter> operator () ( corpusIter corpus_first, corpusIter corpus_last );
    };

另外一种是程序接口：

template <typename patIter, typename corpusIter>
pair<corpusIter, corpusIter> boyer_moore_search (
        corpusIter corpus_first, corpusIter corpus_last,
        patIter pat_first, patIter pat_last );

基于对象的接口构建用构造函数构造所需表，用（）运算符重载的方式执行搜索工作。基于程序的接口构建与执行都在接口程序中一步实现。每一种接口都需要传入两对迭代器，模式的迭代器（patIter）和语料库的迭代器（corpusIter），要求迭代器的值类型要相同。

输入：两对迭代器，模式迭代器和语料库迭代器（patIter和corpusIter）

输出：一对指向模式在语料库中的起始和结束位置的迭代器，如果模式为空，返回语料库迭代器的起始到起始（corpus_first, corpus_first），如果模式没有匹配到，返回迭代器的最后索引到最后索引（corpus_last, corpus_last）

Boyer-Moore-Horspool Search算法

包含头文件： 'boyer_moore_horspool.hpp

功能： 完成在一个序列中搜索值

1980年提出的Boyer-Moore增强算法，在内部表处理更加节省空间，并且在最坏情况下有更好的表现。

接口：

接口有两种：

一种是基于对象的接口：

template <typename patIter>
class boyer_moore_horspool {
public:
    boyer_moore_horspool ( patIter first, patIter last );
    ~boyer_moore_horspool ();
    template <typename corpusIter>
    pair<corpusIter, corpusIter> operator () ( corpusIter corpus_first, corpusIter corpus_last );
    };

另外一种是关联程序的接口：

template <typename patIter, typename corpusIter>
pair<corpusIter, corpusIter> boyer_moore_horspool_search (
        corpusIter corpus_first, corpusIter corpus_last,
        patIter pat_first, patIter pat_last );

输入：两对迭代器，模式迭代器和语料库迭代器（patIter和corpusIter）

Knuth-Morris-Pratt算法

**包含头文件：**knuth_morris_pratt.hpp

**功能：**完成在一个序列中搜索值

这个算法的基本前提是如果没有匹配，需要模式提供信息来决定继续匹配的起点，跳过语料库中的一些元素，这靠构建一个具有匹配模式的每个元素的一个实体的表来实现。算法1974年被证实，1977年发布。

接口：

接口有两种：

一种基于对象的接口：

template <typename patIter>
class knuth_morris_pratt {
public:
    knuth_morris_pratt ( patIter first, patIter last );
    ~knuth_morris_pratt ();
    template <typename corpusIter>
    pair<corpusIter, corpusIter> operator () ( corpusIter corpus_first, corpusIter corpus_last );
    };

另一种是关联程序的接口：

template <typename patIter, typename corpusIter>
pair<corpusIter, corpusIter> knuth_morris_pratt_search (
        corpusIter corpus_first, corpusIter corpus_last,
        patIter pat_first, patIter pat_last );

输入：两对迭代器，模式迭代器和语料库迭代器（patIter和corpusIter）

以上三种搜索算法，都不能用于std::search的比较并且在Boost的1.62.0的发行版之后，迭代器返回两个索引

旧：

iterator foo = searcher(a, b);

新：

iterator foo = searcher(a, b).first;

三、C++11算法模块

all_of

包含头文件： boost/algorithm/cxx11/all_of.hpp

功能： 此算法测试序列中的所有元素是否符合某种指定的属性，算法有两种用法

一种all_of是给定一个序列和一个断言，如果序列中的元素都符合这个断言，就返回true
另一种all_of_equal是给定一个序列和一个值，如果序列中的元素都与这个值相同，就返回true

接口：

all_of

输入：两个界定起止的迭代器和一个断言函数；或者一个范围参数，boost会使用Boost.Range来遍历，另外还有个断言函数
输出：true或者false

namespace boost { namespace algorithm {
template<typename InputIterator, typename Predicate>
  bool all_of ( InputIterator first, InputIterator last, Predicate p );
template<typename Range, typename Predicate>
  bool all_of ( const Range &r, Predicate p );
}}

all_of_equal

输入：两个界定起止的迭代器和一个对比值；或者一个范围参数，boost会使用Boost.Range来遍历，另外还有个对比值
输出：true或者false

namespace boost { namespace algorithm {
template<typename InputIterator, typename V>
  bool all_of_equal ( InputIterator first, InputIterator last, V const &val );
template<typename Range, typename V>
  bool all_of_equal ( const Range &r, V const &val );
}}

实例：

#include <iostream>
#include <iterator>
#include <algorithm>
#include <boost/algorithm/cxx11/all_of.hpp>
#include <vector>
bool isOdd(int i) { return i % 2 == 1; }
bool lessThan10(int i) { return i < 10; }
using namespace boost::algorithm;
int main()
{
    std::vector<int> c{0, 1, 2, 3, 14, 15}; 
    if (all_of(c, isOdd)) {
        std::cout << "c's elements is all odd." <<std::endl;
    }
    else{
        std::cout << "c's elements is not all odd." << std::endl;
    }
    //std c++11 also has all_of
    if (boost::algorithm::all_of(c.begin(), c.end(), lessThan10)) {
        std::cout << "c's elements is all less than 10." << std::endl;
    }
    else {
        std::cout << "c's elements is not all less than 10." << std::endl;
    }
    if (boost::algorithm::all_of(c.begin(), c.begin() + 3, lessThan10)) {
        std::cout << "c's elements[0,3) is all less than 10." << std::endl;
    }
    else{
        std::cout << "c's elements[0,3) is not all less than 10." << std::endl;
    }
    if (boost::algorithm::all_of(c.end(), c.end(), isOdd)) {
        std::cout << "When passed empty range return true." << std::endl;
    }
    if (all_of_equal(c, 3)) {
        std::cout << "c's elements is all equal to 3." << std::endl;
    }
    else{
        std::cout << "c's elements is not all equal to 3." << std::endl;
    }
    if (all_of_equal(c.begin() + 3, c.begin() + 4, 3)) {
        std::cout << "c's elements[3] is all equal to 3." << std::endl;
    }
    else{
        std::cout << "c's elements[3] is not all equal to 3." << std::endl;
    }
    if (all_of_equal(c.begin(), c.begin(), 99)) {
        std::cout << "When passed empty range return true." << std::endl;
    }
}

any_of

包含头文件： boost/algorithm/cxx11/any_of.hpp

功能： 此算法测试序列中的元素是否有符合某种指定的属性，算法有两种用法

一种any_of是给定一个序列和一个断言，如果序列中的元素有符合这个断言的，就返回true
另一种any_of_equal是给定一个序列和一个值，如果序列中的元素有与这个值相同的，就返回true

接口：

any_of

输入：两个界定起止的迭代器和一个断言函数；或者一个范围参数，boost会使用Boost.Range来遍历，另外还有个断言函数
输出：true或者false

namespace boost { namespace algorithm {
template<typename InputIterator, typename Predicate>
  bool any_of ( InputIterator first, InputIterator last, Predicate p );
template<typename Range, typename Predicate>
  bool any_of ( const Range &r, Predicate p );
}}

any_of_equal

输入：两个界定起止的迭代器和一个对比值；或者一个范围参数，boost会使用Boost.Range来遍历，另外还有个对比值
输出：true或者false

namespace boost { namespace algorithm {
template<typename InputIterator, typename V>
  bool any_of_equal ( InputIterator first, InputIterator last, V const &val );
template<typename Range, typename V>
  bool any_of_equal ( const Range &r, V const &val );
}}

实例：

#include <iostream>
#include <iterator>
#include <algorithm>
#include <boost/algorithm/cxx11/any_of.hpp>
#include <vector>
bool isOdd(int i) { return i % 2 == 1; }
bool lessThan10(int i) { return i < 10; }
using namespace boost::algorithm;
int main()
{
    std::vector<int> c{0, 1, 2, 3, 14, 15}; 
    if (any_of(c, isOdd)) {
        std::cout << "c's elements is any odd." <<std::endl;
    }
    else{
        std::cout << "c's elements is not any odd." << std::endl;
    }
    if (boost::algorithm::any_of(c.begin(), c.end(), lessThan10)) {
        std::cout << "c's elements is any less than 10." << std::endl;
    }
    else {
        std::cout << "c's elements is not any less than 10." << std::endl;
    }
    if (boost::algorithm::any_of(c.begin(), c.begin() + 3, lessThan10)) {
        std::cout << "c's elements[0,3) is any less than 10." << std::endl;
    }
    else{
        std::cout << "c's elements[0,3) is not any less than 10." << std::endl;
    }
    if (boost::algorithm::any_of(c.end(), c.end(), isOdd)) {
        std::cout << "When passed empty range return fasle." << std::endl;
    }
    if (any_of_equal(c, 3)) {
        std::cout << "c's elements is any equal to 3." << std::endl;
    }
    else{
        std::cout << "c's elements is not any equal to 3." << std::endl;
    }
    if (any_of_equal(c.begin() + 3, c.begin() + 4, 3)) {
        std::cout << "c's elements[3] is any equal to 3." << std::endl;
    }
    else{
        std::cout << "c's elements[3] is not any equal to 3." << std::endl;
    }
    if (any_of_equal(c.begin(), c.begin(), 99)) {
        std::cout << "When passed empty range return fasle." << std::endl;
    }
}

none_of

包含头文件： boost/algorithm/cxx11/none_of.hpp

功能： 验证一个序列中是否都不具有某种属性。算法有两种用法：

一种none_of是给定一个序列和一个断言，如果序列中的元素都不符合这个断言，就返回true
另一种none_of_equal是给定一个序列和一个值，如果序列中的元素都与这个值不同，就返回true

接口：

none_of

输入：两个界定起止的迭代器和一个断言函数；或者一个范围参数，boost会使用Boost.Range来遍历，另外还有个断言函数
输出：true或者false

namespace boost { namespace algorithm {
template<typename InputIterator, typename Predicate>
  bool none_of ( InputIterator first, InputIterator last, Predicate p );
template<typename Range, typename Predicate>
  bool none_of ( const Range &r, Predicate p );
}}

none_of_equal

输入：两个界定起止的迭代器和一个对比值；或者一个范围参数，boost会使用Boost.Range来遍历，另外还有个对比值
输出：true或者false

namespace boost { namespace algorithm {
template<typename InputIterator, typename V>
  bool none_of_equal ( InputIterator first, InputIterator last, V const &val );
template<typename Range, typename V>
  bool none_of_equal ( const Range &r, V const &val );
}}

实例：

#include <iostream>
#include <iterator>
#include <algorithm>
#include <boost/algorithm/cxx11/none_of.hpp>
#include <vector>
bool isOdd(int i) { return i % 2 == 1; }
bool lessThan10(int i) { return i < 10; }
using namespace boost::algorithm;
int main()
{
    std::vector<int> c{0, 1, 2, 3, 14, 15}; 
    if (none_of(c, isOdd)) {
        std::cout << "c's elements is none odd." <<std::endl;
    }
    else{
        std::cout << "c's elements is not none odd." << std::endl;
    }
    if (boost::algorithm::none_of(c.begin(), c.end(), lessThan10)) {
        std::cout << "c's elements is none less than 10." << std::endl;
    }
    else {
        std::cout << "c's elements is not none less than 10." << std::endl;
    }
    if (boost::algorithm::none_of(c.begin() + 4,c.end(), lessThan10)) {
        std::cout << "c's elements[4:) is none less than 10." << std::endl;
    }
    else{
        std::cout << "c's elements[4:) is not none less than 10." << std::endl;
    }
    if (boost::algorithm::none_of(c.end(), c.end(), isOdd)) {
        std::cout << "When passed empty range return true." << std::endl;
    }
    if (none_of_equal(c, 3)) {
        std::cout << "c's elements is none equal to 3." << std::endl;
    }
    else{
        std::cout << "c's elements is not none equal to 3." << std::endl;
    }
    if (none_of_equal(c.begin(), c.begin() + 3, 3)) {
        std::cout << "c's elements[3] is none equal to 3." << std::endl;
    }
    else{
        std::cout << "c's elements[3] is not none equal to 3." << std::endl;
    }
    if (none_of_equal(c.begin(), c.begin(), 99)) {
        std::cout << "When passed empty range return true." << std::endl;
    }
}

one_of

包含头文件： boost/algorithm/cxx11/one_of.hpp

功能： 验证一个序列中是否准确的有一个具有某种属性。算法有两种用法：

一种one_of是给定一个序列和一个断言，如果序列中的元素精确的有一个符合这个断言，就返回true
另一种one_of_equal是给定一个序列和一个值，如果序列中的元素恰巧有一个与这个值相同，就返回true

接口：

one_of

输入：两个界定起止的迭代器和一个断言函数；或者一个范围参数，boost会使用Boost.Range来遍历，另外还有个断言函数
输出：true或者false

namespace boost { namespace algorithm {
template<typename InputIterator, typename Predicate>
  bool one_of ( InputIterator first, InputIterator last, Predicate p );
template<typename Range, typename Predicate>
  bool one_of ( const Range &r, Predicate p );
}}

none_of_equal

输入：两个界定起止的迭代器和一个对比值；或者一个范围参数，boost会使用Boost.Range来遍历，另外还有个对比值
输出：true或者false

namespace boost { namespace algorithm {
template<typename InputIterator, typename V>
  bool one_of_equal ( InputIterator first, InputIterator last, V const &val );
template<typename Range, typename V>
  bool one_of_equal ( const Range &r, V const &val );
}}

实例：

#include <iostream>
#include <iterator>
#include <algorithm>
#include <boost/algorithm/cxx11/one_of.hpp>
#include <vector>
bool isOdd(int i) { return i % 2 == 1; }
bool lessThan10(int i) { return i < 10; }
using namespace boost::algorithm;
int main()
{
    std::vector<int> c{0, 1, 2, 3, 14, 15}; 
    if (one_of(c, isOdd)) {
        std::cout << "c's elements is one odd." <<std::endl;
    }
    else{
        std::cout << "c's elements is not one odd." << std::endl;
    }
    if (boost::algorithm::one_of(c.begin(), c.end(), lessThan10)) {
        std::cout << "c's elements is one less than 10." << std::endl;
    }
    else {
        std::cout << "c's elements is not one less than 10." << std::endl;
    }
    if (boost::algorithm::one_of(c.begin() + 3, c.end(), lessThan10)) {
        std::cout << "c's elements[4:) is one less than 10." << std::endl;
    }
    else{
        std::cout << "c's elements[4:) is not one less than 10." << std::endl;
    }
    if (boost::algorithm::one_of(c.end(), c.end(), isOdd)) {
        std::cout << "When passed empty range return false." << std::endl;
    }
    if (one_of_equal(c, 3)) {
        std::cout << "c's elements is one equal to 3." << std::endl;
    }
    else{
        std::cout << "c's elements is not one equal to 3." << std::endl;
    }
    if (one_of_equal(c.begin(), c.begin() + 3, 3)) {
        std::cout << "c's elements[3] is one equal to 3." << std::endl;
    }
    else{
        std::cout << "c's elements[3] is not one equal to 3." << std::endl;
    }
    if (one_of_equal(c.begin(), c.begin(), 99)) {
        std::cout << "When passed empty range return false." << std::endl;
    }
}

is_sorted

包含头文件： boost/algorithm/cxx11/is_sorted.hpp

功能： 判断一个序列是否在一些规则下完全有序

如果没有指定断言，默认使用std::less，也即判断序列是否是非递减的

接口：

namespace boost { namespace algorithm {
  template <typename ForwardIterator, typename Pred>
  bool is_sorted ( ForwardIterator first, ForwardIterator last, Pred p );
  template <typename ForwardIterator>
  bool is_sorted ( ForwardIterator first, ForwardIterator last );
  template <typename Range, typename Pred>
  bool is_sorted ( const Range &r, Pred p );
  template <typename Range>
  bool is_sorted ( const Range &r );
}}

实例：

#include <iostream>
#include <iterator>
#include <algorithm>
#include <boost/algorithm/cxx11/is_sorted.hpp>
#include <vector>
bool cmp(int a, int b) { return a > b ? true : false; }
using namespace boost::algorithm;
int main()
{
    std::vector<int> c{0, 1, 2, 3, 14, 15}; 
    bool isSorted = boost::algorithm::is_sorted(c.begin(), c.end());
  if (isSorted)
  {
    std::cout << "c is non-decreasing." << std::endl;
  }
  isSorted = boost::algorithm::is_sorted(c);
  if (isSorted)
  {
    std::cout << "c is non-decreasing." << std::endl;
  }
  c.push_back(5);
  isSorted = boost::algorithm::is_sorted(c.begin(), c.end());
  if (!isSorted)
  {
    std::cout << "c is not sorted." << std::endl;
  }
  std::vector<int> d{ 15, 14, 3, 2, 1, 0 };
  isSorted = boost::algorithm::is_sorted(d.begin(), d.end(), cmp);
  if (isSorted)
  {
    std::cout << "d is decreasing." << std::endl;
  }
  isSorted = boost::algorithm::is_sorted(d, cmp);
  if (isSorted)
  {
    std::cout << "d is decreasing." << std::endl;
  }
}

is_sorted_until

包含头文件： boost/algorithm/cxx11/is_sorted.hpp

功能： 判断局部有序序列。

如果起始索引与终止索引小于2，那么直接返回终止索引。
否则，返回迭代器索引i，[first,i)是有序区。
如果整个序列有序，返回last

简单来说就是返回非有序区的第一个元素的索引。

接口：

namespace boost { namespace algorithm {
  template <typename ForwardIterator, typename Pred>
  FI is_sorted_until ( ForwardIterator first, ForwardIterator last, Pred p );
  template <typename ForwardIterator>
  ForwardIterator is_sorted_until ( ForwardIterator first, ForwardIterator last );
  template <typename Range, typename Pred>
  typename boost::range_iterator<const R>::type is_sorted_until ( const Range &r, Pred p );
  template <typename Range>
  typename boost::range_iterator<const R>::type is_sorted_until ( const Range &r );
}}

实例：

#include <iostream>
#include <iterator>
#include <algorithm>
#include <boost/algorithm/cxx11/is_sorted.hpp>
#include <vector>
using namespace boost::algorithm;
int main()
{
    std::vector<int> c{ 1, 2, 3, 4, 5, 3 };
    auto it = boost::algorithm::is_sorted_until(c.begin(), c.end(), std::less<int>());
    std::cout << "ordered seq:";
    for (auto iter = c.begin(); iter != it; ++iter) {
        std::cout << *iter << " ";
    }
    std::cout << std::endl;
    std::vector<int> d{ 7, 6, 5, 4, 3, 2, 1 };
    auto it1 = boost::algorithm::is_sorted_until(d, std::greater<int>());
    std::cout << "ordered seq:";
    for (auto iter = d.begin(); iter != it1; ++iter) {
        std::cout << *iter << " ";
    }
}

一系列的判断有序的包装器函数

接口：

判断升序

namespace boost { namespace algorithm {
  template <typename Iterator>
  bool is_increasing ( Iterator first, Iterator last );
  template <typename R>
  bool is_increasing ( const R &range );
}}

判断降序

namespace boost { namespace algorithm {
  template <typename ForwardIterator>
  bool is_decreasing ( ForwardIterator first, ForwardIterator last );
  template <typename R>
  bool is_decreasing ( const R &range );
}}

判断严格升序

namespace boost { namespace algorithm {
  template <typename ForwardIterator>
  bool is_strictly_increasing ( ForwardIterator first, ForwardIterator last );
  template <typename R>
  bool is_strictly_increasing ( const R &range );
}}

判断严格降序

namespace boost { namespace algorithm {
  template <typename ForwardIterator>
  bool is_strictly_decreasing ( ForwardIterator first, ForwardIterator last );
  template <typename R>
  bool is_strictly_decreasing ( const R &range );
}}

注：以上函数的调用都是包装的is_sorted，所以其复杂度与is_sorted一致。

#include <iostream>
#include <iterator>
#include <algorithm>
#include <boost/algorithm/cxx11/is_sorted.hpp>
#include <vector>
using namespace boost::algorithm;
int main()
{
    std::vector<int> c{ 1, 2, 3, 3, 4, 5 };
    bool isInc = boost::algorithm::is_increasing(c);
    if (isInc) {
        std::cout << "c is Increasing" << std::endl;
    }
    bool isSInc = boost::algorithm::is_strictly_increasing(c);
    if (!isSInc){
        std::cout << "c is not Strictly increasing" << std::endl;
    }
    std::vector<int> d{ 7, 6, 5, 4, 4, 3, 2, 1 };
    bool isDesc = boost::algorithm::is_increasing(d);
    if (isInc) {
        std::cout << "d is decreasing" << std::endl;
    }
    bool isSDesc = boost::algorithm::is_strictly_increasing(d);
    if (!isSInc) {
        std::cout << "d is not Strictly descreasing" << std::endl;
    }
}

is_partitioned

包含头文件： is_partitioned.hpp

功能： 判断序列是否被分割

输入一个序列起始和终止迭代器或者一个序列本身（使用Boost.Range遍历）以及一个断言，输出是否被分割。

接口：

is_partitioned
包含头文件： is_partitioned.hpp
功能： 判断序列是否被分割
输入一个序列起始和终止迭代器或者一个序列本身（使用Boost.Range遍历）以及一个断言，输出是否被分割。
接口：

实例：

#include <iostream>
#include <iterator>
#include <algorithm>
#include <boost/algorithm/cxx11/is_partitioned.hpp>
#include <vector>
bool isOdd(int i) { return i % 2 == 1; }
bool lessThan10(int i) { return i < 10; }
using namespace boost::algorithm;
int main()
{
    std::vector<int> c{ 0, 1, 2, 3, 14, 15 };
    bool oddSplit = boost::algorithm::is_partitioned(c, isOdd);//-- > false
    if (!oddSplit) {
        std::cout << "seq is not partitioned by odd" << std::endl;
    }
    bool lessSplit = boost::algorithm::is_partitioned(c, lessThan10);// -- > true
    if (lessSplit) {
        std::cout << "seq is partitioned by less than 10" << std::endl;
    }
    lessSplit = boost::algorithm::is_partitioned(c.begin(), c.end(), lessThan10);// -- > true
    if (lessSplit) {
        std::cout << "seq is partitioned by less than 10" << std::endl;
    }
    lessSplit = boost::algorithm::is_partitioned(c.begin(), c.begin() + 3, lessThan10);// -- > true
    if (lessSplit) {
        std::cout << "seq is partitioned by less than 10" << std::endl;
    }
    oddSplit = boost::algorithm::is_partitioned(c.end(), c.end(), isOdd);// -- > true  // empty range
    if (oddSplit) {
        std::cout << "empty range always return true." << std::endl;
    }
}

is_permutation

包含头文件： is_permutation.hpp

功能： 返回是否第二个序列是否为第一个序列的排列。

输入两个序列，判断第二个序列是否为第一个序列的排列。
输出true或者false

接口：

template< class ForwardIterator1, class ForwardIterator2 >
bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2 );
template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate >
bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1,
                      ForwardIterator2 first2, BinaryPredicate p );
template< class ForwardIterator1, class ForwardIterator2 >
bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2 );
template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate >
bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1,
                      ForwardIterator2 first2, ForwardIterator2 last2,
                      BinaryPredicate p );
template <typename Range, typename ForwardIterator>
bool is_permutation ( const Range &r, ForwardIterator first2 );
template <typename Range, typename ForwardIterator, typename BinaryPredicate>
bool is_permutation ( const Range &r, ForwardIterator first2, BinaryPredicate pred );

实例：(实际执行官网文档和实际在头文件中的接口不同，运行总会由于迭代器报错，此处先用std下的代替)

#include <iostream>
#include <iterator>
#include <algorithm>
#include <boost/algorithm/cxx11/is_permutation.hpp>
#include <vector>
bool isOdd(int i) { return i % 2 == 1; }
bool lessThan10(int i) { return i < 10; }
using namespace boost::algorithm;
int main()
{
    std::vector<int> c1{ 0, 1, 2, 3, 14, 15 };
    std::vector<int> c2{ 15, 14, 3, 1, 2 };
    bool isPer =std::is_permutation(c1.begin(), c1.end(), c2.begin(), c2.end());// -- > false
    if (!isPer) {
        std::cout << "c2 is not c1's permutation" << std::endl;
    }
    isPer = std::is_permutation(c1.begin() + 1, c1.end(), c2.begin(), c2.end());// -- > true
    if (isPer) {
        std::cout << "c2[1:] is c1's permutation" << std::endl;
    }
    isPer =  std::is_permutation(c1.end(), c1.end(), c2.end(), c2.end());// -- > true  // all empty ranges are permutations of each other
    if (isPer) {
        std::cout << "empty range is always return true" << std::endl;
    }
}

partition_point

包含头文件： partition_point.hpp

功能： 返回分区点的迭代器索引

接口：

template<typename ForwardIterator, typename Predicate>
  ForwardIterator partition_point ( ForwardIterator first, ForwardIterator last, Predicate p );
template<typename Range, typename Predicate>
  boost::range_iterator<Range> partition_point ( const Range &r, Predicate p );

实例：

#include <iostream>
#include <iterator>
#include <algorithm>
#include <boost/algorithm/cxx11/partition_point.hpp>
#include <vector>
bool isOdd(int i) { return i % 2 == 1; }
bool lessThan10(int i) { return i < 10; }
using namespace boost::algorithm;
int main()
{
    std::vector<int> c{ 0, 1, 2, 3, 14, 15 };
    auto it1 = boost::algorithm::partition_point(c, lessThan10);// -- > c.begin() + 4  (pointing at 14)
    std::cout << *it1 << std::endl;
    auto it2 = boost::algorithm::partition_point(c.begin(), c.end(), lessThan10);// -- > c.begin() + 4  (pointing at 14)
    std::cout << *it2 << std::endl;
    auto it3 = boost::algorithm::partition_point(c.begin(), c.begin() + 3, lessThan10);// ->c.begin() + 3 (end)
    std::cout << *it3 << std::endl;
    try
    {
        auto it4 = boost::algorithm::partition_point(c.end(), c.end(), isOdd);// -- > c.end()  // empty range
        std::cout << *it4 << std::endl;
    }
    catch (const std::exception&)
    {
        std::cout << "For empty ranges, the partition point is the end of the range." << std::endl;
    }
}

partition_copy

功能： 复制一个序列的子集到一个新的序列

接口：

namespace boost {
  namespace algorithm {
    template<typename InputIterator, typename OutputIterator1, 
             typename OutputIterator2, typename UnaryPredicate> 
      BOOST_CXX14_CONSTEXPR std::pair< OutputIterator1, OutputIterator2 > 
      partition_copy(InputIterator, InputIterator, OutputIterator1, 
                     OutputIterator2, UnaryPredicate);
    template<typename Range, typename OutputIterator1, 
             typename OutputIterator2, typename UnaryPredicate> 
      BOOST_CXX14_CONSTEXPR std::pair< OutputIterator1, OutputIterator2 > 
      partition_copy(const Range &, OutputIterator1, OutputIterator2, 
                     UnaryPredicate);
  }
}

copy_if

功能： 复制一个序列的子集到一个新的序列

接口：

namespace boost {
  namespace algorithm {
    template<typename InputIterator, typename OutputIterator, 
             typename Predicate> 
      BOOST_CXX14_CONSTEXPR OutputIterator 
      copy_if(InputIterator, InputIterator, OutputIterator, Predicate);
    template<typename Range, typename OutputIterator, typename Predicate> 
      BOOST_CXX14_CONSTEXPR OutputIterator 
      copy_if(const Range &, OutputIterator, Predicate);
    template<typename InputIterator, typename OutputIterator, 
             typename Predicate> 
      BOOST_CXX14_CONSTEXPR std::pair< InputIterator, OutputIterator > 
      copy_while(InputIterator, InputIterator, OutputIterator, Predicate);
    template<typename Range, typename OutputIterator, typename Predicate> 
      BOOST_CXX14_CONSTEXPR std::pair< typename boost::range_iterator< const Range >::type, OutputIterator > 
      copy_while(const Range &, OutputIterator, Predicate);
    template<typename InputIterator, typename OutputIterator, 
             typename Predicate> 
      BOOST_CXX14_CONSTEXPR std::pair< InputIterator, OutputIterator > 
      copy_until(InputIterator, InputIterator, OutputIterator, Predicate);
    template<typename Range, typename OutputIterator, typename Predicate> 
      BOOST_CXX14_CONSTEXPR std::pair< typename boost::range_iterator< const Range >::type, OutputIterator > 
      copy_until(const Range &, OutputIterator, Predicate);
  }
}

copy_n

功能： 复制一个序列的元素到一个新的序列

接口：

namespace boost {
  namespace algorithm {
    template<typename InputIterator, typename Size, typename OutputIterator> 
      BOOST_CXX14_CONSTEXPR OutputIterator 
      copy_n(InputIterator, Size, OutputIterator);
  }
}

iota

功能： 将整数转换为字符串。

接口：

namespace boost {
  namespace algorithm {
    template<typename ForwardIterator, typename T> 
      BOOST_CXX14_CONSTEXPR void iota(ForwardIterator, ForwardIterator, T);
    template<typename Range, typename T> 
      BOOST_CXX14_CONSTEXPR void iota(Range &, T);
    template<typename OutputIterator, typename T> 
      BOOST_CXX14_CONSTEXPR OutputIterator 
      iota_n(OutputIterator, T, std::size_t);
  }
}

Boost库学习笔记（二）算法模块-C++11标准

Boost库学习笔记（二）算法模块-C++11标准

一、综述

二、搜索算法

Boyer-Moore搜索

Boyer-Moore-Horspool Search算法

Knuth-Morris-Pratt算法

三、C++11算法模块

all_of

any_of

none_of

one_of

is_sorted

is_sorted_until

一系列的判断有序的包装器函数

is_partitioned

is_permutation

partition_point

partition_copy

copy_if

copy_n

iota

热门文章

最新文章

相关课程

相关电子书

相关实验场景

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

Boost库学习笔记（二）算法模块-C++11标准

Boost库学习笔记（二）算法模块-C++11标准

一、综述

二、搜索算法

Boyer-Moore搜索

Boyer-Moore-Horspool Search算法

Knuth-Morris-Pratt算法

三、C++11算法模块

all_of

any_of

none_of

one_of

is_sorted

is_sorted_until

一系列的判断有序的包装器函数

is_partitioned

is_permutation

partition_point

partition_copy

copy_if

copy_n

iota

热门文章

最新文章

相关课程

相关电子书

相关实验场景