C++ 常用泛型算法

查找算法

• all_of

  template< class InputIt, class UnaryPredicate >
  bool all_of(InputIt first, InputIt last, UnaryPredicate p );
  检查一元谓词 p 是否对范围 [first, last) 中所有元素返回 true
  
  // 应用：判断一个字符串是不是全部由数字组成
  string st = "01234";
  all_of(st.begin(), st.end(), isdigit());
  

• any_of none_of

template< class InputIt, class UnaryPredicate >
bool all_of(InputIt first, InputIt last, UnaryPredicate p );
检查一元谓词 p 是否对范围 [first, last) 中所有元素返回 true 

template< class InputIt, class UnaryPredicate >
bool any_of(InputIt first, InputIt last, UnaryPredicate p );
检查一元谓词 p 是否对范围 [first, last) 中至少一个元素返回 true 

template< class InputIt, class UnaryPredicate >
bool none_of(InputIt first, InputIt last, UnaryPredicate p );
检查一元谓词 p 是否不对范围 [first, last) 中任何元素返回 true

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <iterator>
#include <functional>
using namespace std;

int main() 
{
    vector<int> v(2, 4, 6, 8, 9, 10. 12, 14);

    if (std::all_of(v.cbegin(), v.cend(), [](int i){    return i % 2 == 0;  }))  
        std::cout << "All numbers are even\n";
    
    if (std::none_of(v.cbegin(), v.cend(), std::bind(std::modulus<int>(), std::placeholders::_1, 2))) 
        std::cout << "None of them are odd\n";
    
    class DivisibleBy 
    {
        public:
            DivisibleBy(int n) : d(n)   {   }
            bool operator()(int n) const    {   return n % d == 0;  }       
        private:
            const int d;
    };

    if (std::any_of(v.cbegin(), v.cend(), DivisibleBy(7))) 
        std::cout << "At least one number is divisible by 7\n";
}

• partition

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
#include <forward_list>
 
template <class ForwardIt>
 void quicksort(ForwardIt first, ForwardIt last)
 {
    if(first == last) 
        return;
    auto pivot = *std::next(first, std::distance(first,last)/2);

    ForwardIt middle1 = std::partition(first, last, 
                         [pivot](const auto& em){ return em < pivot; });
    
    ForwardIt middle2 = std::partition(middle1, last, 
                         [pivot](const auto& em){ return !(pivot < em); });

    quicksort(first, middle1);
    quicksort(middle2, last);
 }
 
int main()
{
    std::forward_list<int> fl = {1, 30, -4, 3, 5, -4, 1, 6, -8, 2, -5, 64, 1, 92};
    std::cout << "\nUnsorted list:\n    ";
    for (int n : fl)
        std::cout << n << ' ';
    std::cout << '\n';  
 
    quicksort(std::begin(fl), std::end(fl));
    std::cout << "Sorted using quicksort:\n    ";
    for(int fi : fl) std::cout << fi << ' ';
    std::cout << '\n';
}

排序

• is_sorted

template< class ForwardIt >
bool is_sorted( ForwardIt first, ForwardIt last );

template< class ForwardIt, class Compare >
bool is_sorted( ForwardIt first, ForwardIt last, Compare comp );

ForwardIt 必须满足 ForwardIterator 的要求。

• is_sorted_until

template< class ForwardIt >
ForwardIt is_sorted_until( ForwardIt first, ForwardIt last );

template< class ForwardIt, class Compare >
ForwardIt is_sorted_until( ForwardIt first, ForwardIt last, Compare comp );

检验范围 [first, last) ，并寻找始于 first 且其中元素已以升序排序的最大范围。
ForwardIt 必须满足 ForwardIterator 的要求。

• sort

template< class RandomIt >
void sort( RandomIt first, RandomIt last );

template< class RandomIt, class Compare >
void sort( RandomIt first, RandomIt last, Compare comp );

RandomIt 必须满足 ValueSwappable 和 RandomAccessIterator 的要求。

最小最大操作

• max

template< class T > 
const T& max( const T& a, const T& b );

template< class T, class Compare >
const T& max( const T& a, const T& b, Compare comp );

template< class T >
T max(std::initializer_list]initializer_list<T> ilist );

template< class T, class Compare >
T max( std::initializer_list<T> ilist, Compare comp );

• max_element

template< class ForwardIt > 
ForwardIt max_element(ForwardIt first, ForwardIt last );

template< class ForwardIt, class Compare >
ForwardIt max_element(ForwardIt first, ForwardIt last, Compare comp );

二分搜索操作（在已排序范围上）

template< class ForwardIt, class T >
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value);

template< class ForwardIt, class T, class Compare >
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp);

ForwardIt 必须满足 ForwardIterator 的要求。
指向首个不小于 value 的元素的迭代器，或若找不到这种元素则为 last 

集合操作

修改序列

• transfrom

template< class InputIt, class OutputIt, class UnaryOperation >
OutputIt transform( InputIt first1, InputIt last1, OutputIt d_first,
                    UnaryOperation unary_op );

template< class InputIt1, class InputIt2, class OutputIt, class BinaryOperation >
OutputIt transform( InputIt1 first1, InputIt1 last1, InputIt2 first2, 
                    OutputIt d_first, BinaryOperation binary_op );

-InputIt, InputIt1, InputIt2 必须满足 InputIterator 的要求。
-OutputIt 必须满足 OutputIterator 的要求。
-ForwardIt1, ForwardIt2, ForwardIt3 必须满足 ForwardIterator 的要求。

#include <algorithm>
#include <cctype>
#include <iostream>
#include <string>
 
int main()
{
    std::string s("hello");
    std::transform(s.begin(), s.end(), s.begin(),
                   [](unsigned char c) -> unsigned char { return std::toupper(c); });
}

• generate

template< class ForwardIt, class Generator >
void generate( ForwardIt first, ForwardIt last, Generator g );

-ForwardIt 必须满足 ForwardIterator 的要求。

#include <algorithm>
#include <iostream>
#include <vector>
 
int main()
{
    std::vector<int> v(5);
    std::generate(v.begin(), v.end(), [n = 0] () mutable { return n++; });
 
    std::cout << "v: ";
    for (auto iv: v)
        std::cout << iv << " ";
    std::cout << "\n";
}

• std::remove 和 std::remove_if

template< class ForwardIt, class T >
ForwardIt remove( ForwardIt first, ForwardIt last, const T& value );

template< class ForwardIt, class UnaryPredicate >
ForwardIt remove_if( ForwardIt first, ForwardIt last, UnaryPredicate p );

-ForwardIt 必须满足 ForwardIterator 的要求。
-解引用 ForwardIt 结果的类型必须满足 MoveAssignable 的要求。
-UnaryPredicate 必须满足 Predicate 的要求。

从 string 移除所有空格，通过迁移所有非空格字符到左侧，再擦除其他内容。这是擦除移除手法的样例。

#include <algorithm>
#include <string>
#include <iostream>
#include <cctype>
 
int main()
{
    std::string str1 = "Text with some   spaces";
    str1.erase(std::remove(str1.begin(), str1.end(), ' '), str1.end());
    std::cout << str1 << '\n';
 
    std::string str2 = "Text\n with\tsome \t  whitespaces\n\n";
    str2.erase(std::remove_if(str2.begin(), 
                              str2.end(),
                              [](unsigned char x){return std::isspace(x);}),
               str2.end());
    std::cout << str2 << '\n';
}