std algorithm 01-seq operations

c++标准库算法库中几个有用的函数

序列恒定操作

batch operation

for_each, 主要针对容器的begin， end做一个func的操作。返回值会被ignore, 比较适合对整个容器的每个值做操作，要注意的是不能对容器做缩容

template< class InputIt, class UnaryFunc >
UnaryFunc for_each( InputIt first, InputIt last, UnaryFunc f );

template<class InputIt, class UnaryFunc>
constexpr UnaryFunc for_each(InputIt first, InputIt last, UnaryFunc f)
{
  for (; first != last; ++first)
      f(*first);

  return f; // implicit move since C++11
}

用法类似

#include <algorithm>
#include <iostream>
#include <vector>

int main()
{
  std::vector<int> v{3, -4, 2, -8, 15, 267};

  auto print = [](const int& n) { std::cout << n << ' '; };

  std::cout << "before:\t";
  std::for_each(v.cbegin(), v.cend(), print);
  std::cout << '\n';

  // increment elements in-place
  std::for_each(v.begin(), v.end(), [](int &n) { n++; });

  std::cout << "after:\t";
  std::for_each(v.cbegin(), v.cend(), print);
  std::cout << '\n';

  struct Sum
  {
    void operator()(int n) { sum += n; }
    int sum {0};
  };

  // invoke Sum::operator() for each element
  Sum s = std::for_each(v.cbegin(), v.cend(), Sum());    
  std::cout << "sum:\t" << s.sum << '\n';
}

search operation

首先常用的就三个

template< class InputIt, class UnaryPred >
bool all_of( InputIt first, InputIt last, UnaryPred p );

template< class InputIt, class UnaryPred >
bool any_of( InputIt first, InputIt last, UnaryPred p );

template< class InputIt, class UnaryPred >
bool none_of( InputIt first, InputIt last, UnaryPred p );

上述三个推荐用const iterator，func记得用value type或者const&

随后是find的三个操作, 这里也同样推荐const it，func记得用value type或者const&

template< class InputIt, class T >
InputIt find( InputIt first, InputIt last, const T& value );

template< class InputIt, class UnaryPred >
InputIt find_if( InputIt first, InputIt last, UnaryPred p );

template< class InputIt, class UnaryPred >
InputIt find_if_not( InputIt first, InputIt last, UnaryPred q );

std::find 用于在指定范围内查找与给定值相等的第一个元素

std::find_if 用于在指定范围内查找满足特定条件的第一个元素。它接受一个一元谓词（函数或函数对象）作为判断条件。

std::vector<int> vec = {1, 2, 3, 4, 5};
auto it = std::find_if(vec.begin(), vec.end(), [](int n) { return n > 3; });
if (it != vec.end()) {
  std::cout << "First number greater than 3: " << *it << std::endl;
}

std::find_if_not 与 std::find_if 相反，它查找第一个不满足给定条件的元素。

Modifying sequence operations

这里的很多操作都可以配合back_inserter之类的iterator使用

copy operation

#include <algorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <vector>
 
int main()
{
    std::vector<int> from_vector(10);
    std::iota(from_vector.begin(), from_vector.end(), 0);
 
    std::vector<int> to_vector;
    std::copy(from_vector.begin(), from_vector.end(),
              std::back_inserter(to_vector));
// or, alternatively,
//  std::vector<int> to_vector(from_vector.size());
//  std::copy(from_vector.begin(), from_vector.end(), to_vector.begin());
// either way is equivalent to
//  std::vector<int> to_vector = from_vector;
 
    std::cout << "to_vector contains: ";
 
    std::copy(to_vector.begin(), to_vector.end(),
              std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
 
    std::cout << "odd numbers in to_vector are: ";
 
    std::copy_if(to_vector.begin(), to_vector.end(),
                 std::ostream_iterator<int>(std::cout, " "),
                 [](int x) { return x % 2 != 0; });
    std::cout << '\n';
 
    std::cout << "to_vector contains these multiples of 3: ";
 
    to_vector.clear();
    std::copy_if(from_vector.begin(), from_vector.end(),
                 std::back_inserter(to_vector),
                 [](int x) { return x % 3 == 0; });
 
    for (const int x : to_vector)
        std::cout << x << ' ';
    std::cout << '\n';
}

Transformation operations

transform用于对一个范围内的元素进行转换操作，并将结果存储到另一个范围。这个函数有两个主要版本：一元操作和二元操作

1. 一元操作版本的 std::transform

语法：

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

这个版本对输入范围 [first1, last1) 中的每个元素应用一元操作 unary_op，并将结果存储到以 d_first 开始的输出范围。

用法示例：

std::vector<int> input = {1, 2, 3, 4, 5};
std::vector<int> output(input.size());

std::transform(input.begin(), input.end(), output.begin(),
               [](int i) { return i * i; });
// output 现在包含 {1, 4, 9, 16, 25}

1. 二元操作版本的 std::transform

语法：

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

这个版本对两个输入范围的对应元素应用二元操作 binary_op，并将结果存储到输出范围。

用法示例：

std::vector<int> v1 = {1, 2, 3, 4, 5};
std::vector<int> v2 = {10, 20, 30, 40, 50};
std::vector<int> result(v1.size());

std::transform(v1.begin(), v1.end(), v2.begin(), result.begin(),
               [](int a, int b) { return a + b; });
// result 现在包含 {11, 22, 33, 44, 55}

std::transform 的主要特点和使用注意事项：

1. 灵活性：可以用于各种转换操作，从简单的数学运算到复杂的自定义逻辑。

2. 就地转换：输出范围可以与输入范围相同，实现就地转换。

   std::transform(vec.begin(), vec.end(), vec.begin(),
                  [](int i) { return i * 2; });
   

3. 与其他容器和算法的兼容性：可以与不同类型的容器和其他 STL 算法结合使用。

4. 性能：通常比手动循环更高效，尤其是在编译器优化的情况下。

5. 返回值：函数返回指向输出范围末尾的迭代器。

6. 输入和输出类型可以不同：

   std::vector<std::string> names = {"Alice", "Bob", "Charlie"};
   std::vector<size_t> name_lengths(names.size());
   std::transform(names.begin(), names.end(), name_lengths.begin(),
                  [](const std::string& s) { return s.length(); });
   

7. 与 std::back_inserter 结合使用：可以动态增长输出容器。

   std::vector<int> input = {1, 2, 3, 4, 5};
   std::vector<int> output;
   std::transform(input.begin(), input.end(), std::back_inserter(output),
                  [](int i) { return i * i; });
   

8. 在并行算法中的应用：C++17 引入了并行版本的 std::transform，可以利用多核处理器提高性能。

9. 错误处理：transform 不进行边界检查，确保输出范围足够大是调用者的责任。

Generation operations

细介绍一下这四个算法函数:fill、fill_n、generate和generate_n, 主要用于填充或生成容器中的元素。

1. std::fill

std::fill用于将一个值填充到指定范围内的所有元素。

语法:

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

用法示例:

std::vector<int> v(5);
std::fill(v.begin(), v.end(), 10);
// v 现在包含 {10, 10, 10, 10, 10}

1. std::fill_n

std::fill_n类似于fill,但它填充指定数量的元素,而不是一个范围。

语法:

template< class OutputIt, class Size, class T >
OutputIt fill_n( OutputIt first, Size count, const T& value );

用法示例:

std::vector<int> v(5);
std::fill_n(v.begin(), 3, 10);
// v 现在包含 {10, 10, 10, 0, 0}

1. std::generate

std::generate用于使用一个生成器函数填充一个范围内的元素。

语法:

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

用法示例:

std::vector<int> v(5);
int i = 0;
std::generate(v.begin(), v.end(), [&i]{ return i++; });
// v 现在包含 {0, 1, 2, 3, 4}

1. std::generate_n

std::generate_n类似于generate,但它生成指定数量的元素,而不是一个范围。

语法:

template< class OutputIt, class Size, class Generator >
OutputIt generate_n( OutputIt first, Size count, Generator gen );

用法示例:

std::vector<int> v(5);
int i = 0;
std::generate_n(v.begin(), 3, [&i]{ return i++; });
// v 现在包含 {0, 1, 2, 0, 0}

这些函数的主要特点和使用注意事项:

1. 灵活性:
   • fill 和 fill_n 用于填充相同的值
   • generate 和 generate_n 可以使用自定义函数生成不同的值
2. 范围 vs 数量:
   • fill 和 generate 操作一个范围 [first, last)
   • fill_n 和 generate_n 操作指定数量的元素
3. 返回值:
   • fill 和 generate 没有返回值 (void)
   • fill_n 和 generate_n 返回指向最后一个被填充或生成元素之后的迭代器

4. 性能:这些函数通常比手动循环更高效,特别是在编译器优化的情况下

5. 安全性:fill_n 和 generate_n 不检查容器大小,使用时需要确保有足够的空间

6. 与其他STL功能的结合:

   std::vector<int> v;
   std::generate_n(std::back_inserter(v), 5, []{ return rand(); });
   

7. 应用场景:
   • 初始化容器
   • 重置容器内容
   • 生成测试数据
   • 创建特定模式的序列

8. 与C++11 lambda表达式的结合:特别适合与lambda表达式一起使用,使得生成复杂序列变得简单

9. 对自定义类型的支持:这些函数可以用于任何满足要求的容器和自定义类型

Removing operations

这些操作主要用于从容器中移除特定元素,但需要注意的是,它们并不实际从容器中删除元素,而是重新排列元素。主要的移除操作包括:

1. std::remove 和 std::remove_if

这两个函数用于移除满足特定条件的元素。

std::remove 语法:

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

std::remove_if 语法:

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

用法示例:

std::vector<int> v = {1, 2, 3, 2, 5, 2, 6};
auto new_end = std::remove(v.begin(), v.end(), 2);
v.erase(new_end, v.end());
// v 现在包含 {1, 3, 5, 6}

std::vector<int> v2 = {1, 2, 3, 4, 5, 6};
auto new_end2 = std::remove_if(v2.begin(), v2.end(), [](int n){ return n % 2 == 0; });
v2.erase(new_end2, v2.end());
// v2 现在包含 {1, 3, 5}

1. std::unique 和 std::unique_copy

这些函数用于移除连续重复的元素,只保留第一个。

std::unique 语法:

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

std::unique_copy 语法:

template< class InputIt, class OutputIt >
OutputIt unique_copy( InputIt first, InputIt last, OutputIt d_first );

用法示例:

std::vector<int> v = {1, 2, 2, 3, 3, 3, 4, 5, 5};
// ranges::sort(v)
auto new_end = std::unique(v.begin(), v.end());
v.erase(new_end, v.end());
// v 现在包含 {1, 2, 3, 4, 5}

std::vector<int> source = {1, 2, 2, 3, 3, 3, 4, 5, 5};
std::vector<int> dest;
std::unique_copy(source.begin(), source.end(), std::back_inserter(dest));
// dest 现在包含 {1, 2, 3, 4, 5}

1. std::remove_copy 和 std::remove_copy_if

这些函数将不满足移除条件的元素复制到新的范围。

std::remove_copy 语法:

template< class InputIt, class OutputIt, class T >
OutputIt remove_copy( InputIt first, InputIt last, OutputIt d_first, const T& value );

std::remove_copy_if 语法:

template< class InputIt, class OutputIt, class UnaryPredicate >
OutputIt remove_copy_if( InputIt first, InputIt last, OutputIt d_first, UnaryPredicate p );

用法示例:

std::vector<int> source = {1, 2, 3, 2, 5, 2, 6};
std::vector<int> dest;
std::remove_copy(source.begin(), source.end(), std::back_inserter(dest), 2);
// dest 现在包含 {1, 3, 5, 6}

std::vector<int> source2 = {1, 2, 3, 4, 5, 6};
std::vector<int> dest2;
std::remove_copy_if(source2.begin(), source2.end(), std::back_inserter(dest2), 
                    [](int n){ return n % 2 == 0; });
// dest2 现在包含 {1, 3, 5}

使用这些操作时的注意事项:

1. 这些操作不会改变容器的大小。它们只是重新排列元素,将”要保留”的元素移到前面。

2. 通常需要配合erase()使用来真正删除元素。这就是所谓的”erase-remove idiom”。

3. 对于关联容器(如set,map),应使用它们的成员函数(如erase())而不是这些算法。

4. 这些操作通常比手动实现更高效,特别是在大型容器上。

5. 对于unique操作,输入范围通常需要先排序。

6. 这些操作返回一个迭代器,指向最后一个未被移除的元素之后的位置。

7. remove_copy和remove_copy_if很有用,因为它们不修改原始容器。