STL 算法

概述

算法中包含很多对容器进行处理的算法，使用迭代器来标识要处理的数据或数据段、以及结果的存放位置，有的函数还作为对象参数传递给另一个函数，实现数据的处理。这些算法可以操作在多种容器类型上, 所以称为“泛型”，泛型算法不是针对容器编写，而只是单独依赖迭代器和迭代器操作实现。而且算法库中的算法都是普通函数（自由函数）。

算法的分类

非修改式的算法：for_each、count、find
修改式的算法： copy、remove、remove_if、replace
排序算法： sort
二分搜索算法： lower_bound
集合操作： set_intersection
堆操作： make_heap、push_heap、pop_heap
取最大值最小值： max、min
数值操作： accumulate
未初始化的内存操作： uninitialized_copy

一元函数以及一元断言/一元谓词

一元函数：函数的参数只有一个；
一元断言/一元谓词：函数的参数只有一个，并且返回类型是 bool 类型。
二元函数：函数的参数有两个；
二元断言/二元谓词：函数的参数两个，并且返回类型是 bool 类型。

非修改式算法 `for_each`

// # if __cplusplus > 201703L
// #  define _GLIBCXX20_CONSTEXPR constexpr

/**
   *  @brief Apply a function to every element of a sequence.
   *  @ingroup non_mutating_algorithms
   *  @param  __first  An input iterator.
   *  @param  __last   An input iterator.
   *  @param  __f      A unary function object.
   *  @return   @p __f
   *
   *  Applies the function object @p __f to each element in the range
   *  @p [first,last).  @p __f must not modify the order of the sequence.
   *  If @p __f has a return value it is ignored.
  */
template<typename _InputIterator, typename _Function>
_GLIBCXX20_CONSTEXPR
_Function
for_each(_InputIterator __first, _InputIterator __last, _Function __f)
{
  // concept requirements
  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
    __glibcxx_requires_valid_range(__first, __last);
  for (; __first != __last; ++__first)
    __f(*__first);
  return __f; // N.B. [alg.foreach] says std::move(f) but it's redundant.
}

for_each(vec.begin(), vec.end(), [](int &value) -> void {
  ++value;
  cout << value << "  ";
});

修改式算法 `remove_if`

bool func(int value) {
  return value > 6;
}

int main() {
  vector<int> vec = {1, 3, 5, 8, 6, 4, 7, 9};
  for_each(vec.begin(), vec.end(), [](int &value) {
    cout << value << "  ";
  });
  cout << endl;

  // 将所有大于 6 的元素删除
  cout << endl << "执行remove_if操作之后" << endl;
  // remove_if 不能将满足条件的元素直接删除，但是会返回待删除元素的首迭代器
  // 然后再配合容器的 erase 操作，才可以达到删除的满足条件的效果
  auto it = remove_if(vec.begin(), vec.end(), func);
  vec.erase(it, vec.end());
  for_each(vec.begin(), vec.end(), [](int &value) {
    cout << value << "  ";
  });
  cout << endl;
  return 0;
}

/**
   *  @brief Remove elements from a sequence using a predicate.
   *  @ingroup mutating_algorithms
   *  @param  __first  A forward iterator.
   *  @param  __last   A forward iterator.
   *  @param  __pred   A predicate.
   *  @return   An iterator designating the end of the resulting sequence.
   *
   *  All elements for which @p __pred returns true are removed from the range
   *  @p [__first,__last).
   *
   *  remove_if() is stable, so the relative order of elements that are
   *  not removed is unchanged.
   *
   *  Elements between the end of the resulting sequence and @p __last
   *  are still present, but their value is unspecified.
  */
template<typename _ForwardIterator, typename _Predicate>
_GLIBCXX20_CONSTEXPR
inline _ForwardIterator
remove_if(_ForwardIterator __first, _ForwardIterator __last,
          _Predicate __pred)
{
  // concept requirements
  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIterator>)
    __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, typename iterator_traits<_ForwardIterator>::value_type>)
    __glibcxx_requires_valid_range(__first, __last);

  return std::__remove_if(__first, __last,
                          __gnu_cxx::__ops::__pred_iter(__pred));
}

template<typename _ForwardIterator, typename _Predicate>
_GLIBCXX20_CONSTEXPR
_ForwardIterator
__remove_if(_ForwardIterator __first, _ForwardIterator __last _Predicate __pred)
{
  __first = std::__find_if(__first, __last, __pred);
  if (__first == __last)
    return __first;
  _ForwardIterator __result = __first;
  ++__first;
  for (; __first != __last; ++__first)
    if (!__pred(__first))
    {
      *__result = _GLIBCXX_MOVE(*__first);
      ++__result;
    }
  return __result;
}

`vector` 的 `push_back` 操作导致迭代器失效

vector<int> vec;
vec.push_back(100);

bool flag = true;
for (auto it = vec.begin(); it != vec.end(); ++it) {
  cout << *it << "  ";// 读
  if (flag) {
    // 在执行 push_back 的时候，底层已经发生了扩容，导致迭代器
    // it 指向的还是老的空间，所以此时迭代器已经失效了
    // 解决方案：重置迭代器的位置（更新迭代器）
    vec.push_back(200);// 写
    it = vec.begin();// 更新迭代器
    flag = false;
  }
}
cout << endl;

`bind1st` 与 `bind2nd`

对于二元断言 Func 而言如果现在可以固定第过个参数 Args2，将其固定为 6，那么此处要想删除大于 6 的元素，那么 Func 的实现就是 Args1 > 6，也就表明 Func 具备大于符号的含义，也就是 std:: greater;

如果现在可以固定第一个参数 Args1，将其固定为 6，那么此处要想删除大于 6 的元素，那么 Func 的实现就是 6 > Args2, 也就表明 Func 具备小于符号的含义，也就是 std:: less;

bind1st 可以固定二元函数对象 f 的第一个参数，将其固定为 x

bind2nd 可以固定二元函数对象 f 的第二个参数，将其固定为 x

// 将所有大于 6 的元素删除
cout << endl << "执行 remove_if 操作之后" << endl;
auto it = remove_if(vec.begin(), vec.end(), bind2nd(std::greater<int>(), 6));

bind2nd 绑定了二元函数对象 std::greater 的右操作数 rhs = 6，而 greater 的实现是 return lhs > rhs = 6，也就是将大于 6 的删除。

`bind`

模板形式

绑定函数的类型

int add(int x, int y) {
  cout << "int add(int, int)" << endl;
  return x + y;
}

int multiply(int x, int y, int z) {
  cout << "int multiply(int, int, int)" << endl;
  return x * y * z;
}

class Example {
 public:
  // Example * const this
  int add(/* this */int x, int y) {
    cout << "int Example::add(int, int)" << endl;
    return x + y;
  }
};


int main(int argc, char *argv[]) {
  // 绑定普通的二元函数
  auto f = bind(&add, 1, 2);
  cout << "f() = " << f() << endl;
  // f() = int add(int, int) 3

  cout << endl << endl;
  // 绑定普通的三元函数
  auto f2 = bind(&multiply, 3, 4, 5);
  cout << "f2() = " << f2() << endl;
  // f2() = int multiply(int, int, int) 60

  cout << endl << endl;
  Example ex;
  // 绑定成员函数，但是非静态成员
  // 函数的 this 指针不要忘了
  auto f3 = bind(&Example::add, &ex, 10, 30);
  cout << "f3() = " << f3() << endl;
  // f3() = int Example::add(int, int) 40

  return 0;
}

引用折叠

引用折叠（reference collapsing）是指在模板编程中，编译器如何处理嵌套的模板参数引用的情况。引用折叠允许通过一系列引用来访问模板参数的类型，即使这些引用是嵌套的。

在 C++11 及以后的版本中，引入了引用折叠的规则，以便在模板参数中使用引用时，能够简化类型表达式。引用折叠主要发生在以下几种情况：

T& 和 T&：如果两个引用类型相同，它们会折叠成单个引用。 T& & -> T&
T& 和 T&&：左值引用和右值引用相遇时，右值引用会被转换为左值引用。 T& && -> T&
T&& 和 T&：右值引用和左值引用相遇时，左值引用会被忽略。 T& && -> T&
T&& 和 T&&：两个右值引用相遇时，它们会折叠成单个右值引用。 T&& && -> T&&

这些规则在模板参数推导时非常有用，因为它们允许编译器正确地推导出模板参数的类型，即使这些类型是通过引用传递的。

函数指针

/* func1(); */
// 函数指针的定义形式
// typedef int(*)() pFunc; // error, 语法是错的
typedef int(*pFunc)(); // ok，C 语言的写法
// using pFunc = int(*)(); // ok，C++11 的

// typedef int A;
// using A = int;

// 回调函数是被动调用的，会先注册给函数指针，然后由函数指针进行调用
// 函数指针可以将指向的回调函数延迟调用
pFunc f = &func1; // 回调函数的注册
cout << "111-11" << endl;
cout << "f() = " << f() << endl; // 回调函数的执行

cout << endl;
pFunc f2 = func2;
cout << "f2() = " << f2() << endl;

cout << endl;
// 函数的指针的类型不匹配，所以就不能这么使用
// pFunc f3 = func3; // error
return 0;

占位符

void func(int x1, int x2, int x3, const int &x4, int x5) {
  cout << "x1 = " << x1 << endl
       << "x2 = " << x2 << endl
       << "x3 = " << x3 << endl
       << "x4 = " << x4 << endl
       << "x5 = " << x5 << endl;
}

int main(int argc, char *argv[]) {
  int number = 100;
  // 占位符整体代表的是形参的位置
  // 占位符中的数字代表的是实参的位置
  // 实参的个数一定要大于等于占位符中数字的最大值
  // bind 的默认采用值传递
  // 引用的包装器 std::ref = reference
  // 引用的包装器 std::cref = const reference
  using namespace std::placeholders;
  auto f = bind(func, 1, _4, _3, std::cref(number), number);
  number = 200;
  f(2, 30, 400, 5000, 6666);// 多余的参数直接丢掉
  return 0;
}

`function`

// 函数形态（类型、标签）: 函数的返回类型 + 参数列表
// add 的类型：int(int, int)
// f 的类型: int()
/* auto f = bind(&add, 1, 2); */
function<int()> f = bind(&add, 1, 2);
cout << "f() = " << f() << endl;
// f() = int add(int, int) 3

cout << endl << endl;
// multiply 的类型：int(int, int, int)
// f2 的类型:int()
function<int()> f2 = bind(&multiply, 3, 4, 5);
cout << "f2() = " << f2() << endl;
// f2() = int multiply(int, int, int) 60
/* f = bind(&multiply, 3, 4, 5); */
/* cout << "f() = " << f() << endl; */

绑定数据成员

class Example {
 public:
  int add(/* this */int x, int y) {
    cout << "int Example::add(int, int)" << endl;
    return x + y;
  }

  int data = 222;
};

data 是 Example 中的数据成员，bind 还可以绑定数据成员。

将成员的名字看成是函数的名字，数据成员的类型就是函数的返回类型，参数列表就是空（隐含的 this 还是有的）。

cout << endl << "bind 绑定数据成员" << endl;
Example ex2;
function<int()> f5 = bind(&Example::data, &ex2);
cout << "f5() = " << f5() << endl;

`bind` 绑定成员函数传参方式

class Example {
 public:
  int add(/* this */int x, int y) {
    cout << "int Example::add(int, int)" << endl;
    return x + y;
  }
};

int main() {
  Example ex;
  auto f = bind(&Example::add, &ex, 10, 30); // 传地址
  cout << "f(&ex) = " << f(&ex) << endl;

  cout << endl;
  auto f2 = bind(&Example::add, ex, 100, 300); // 传对象
  cout << "f2(ex) = " << f2(ex) << endl;
}

传地址与传对象的区别：对象地址的传递就是一个指针的传递，不会出现拷贝操作，但是使用对象传递，会存在拷贝对象操作，对象如果占用内存较大，会浪费空间。

使用对象地址，如果在使用的时候，对象已经销毁了，就有空指针的问题，但是拷贝一份对象，那原对象销毁了，这里采用的是拷贝操作，就不会有影响。

`bind` 与 `function` 的结合使用

class Figure {
 public:
  //纯虚函数
  virtual void display() const = 0;

  virtual double area() const = 0;
};

class Rectangle: public Figure {
 public:
  explicit Rectangle(double length = 0, double width = 0)
      : _length(length), _width(width) {
    cout << "Rectangle(double = 0, double = 0)" << endl;
  }

  void display() const override {
    cout << "Rectangle";
  }

  double area() const override {
    return _length * _width;
  }

  ~Rectangle() {
    cout << "~Rectangle()" << endl;
  }

 private:
  double _length;
  double _width;
};

面向对象的写法：继承 + 虚函数（纯虚函数），运行时，灵活性强。

基于对象的写法：std:: bind + std:: function, 编译时, 效率高。

C 语言中使用函数指针进行注册回调函数与执行回调函数。

C++ 中使用 std:: bind + std:: function 进行注册与执行回调函数。

class Figure {
 public:
  // 定义出来了两种类型别名
  using DisplayCallback = function<void()>;
  using AreaCallback = function<double()>;
  /**
   * void()
   * virtual void display() const = 0;
   * double()
   * virtual double area() const = 0;
   * void setDisplayCallback(const DisplayCallback &cb) {
   *   _displayCallback = cb;
   * }
   */

  // 回调函数的注册
  void setDisplayCallback(DisplayCallback &&cb) {
    _displayCallback = std::move(cb);
  }

  void setAreaCallback(AreaCallback &&cb) {
    _areaCallback = std::move(cb);
  }

  // 回调函数的执行
  void handleDisplayCallback() const {
    if (_displayCallback) {
      _displayCallback();
    }
  }

  double handleAreaCallback() const {
    if (_areaCallback) {
      return _areaCallback();
    } else {
      return 0.0;
    }
  }

  DisplayCallback _displayCallback;
  AreaCallback _areaCallback;
};

class Rectangle: public Figure {
 public:
  explicit Rectangle(double length = 0, double width = 0)
      : _length(length), _width(width) {
    cout << "Rectangle(double = 0, double = 0)" << endl;
  }

  void display() const override {
    cout << "Rectangle";
  }

  double area() const override {
    return _length * _width;
  }

  ~Rectangle() {
    cout << "~Rectangle()" << endl;
  }

 private:
  double _length;
  double _width;
};

class Rectangle {
 public:
  explicit Rectangle(double length = 0, double width = 0) : _length(length), _width(width) {
    cout << "Rectangle(double = 0, double = 0)" << endl;
  }

  void display(int x, int y) const {
    cout << "Rectangle";
  }

  double area() const {
    return _length * _width;
  }

  ~Rectangle() {
    cout << "~Rectangle()" << endl;
  }

 private:
  double _length;
  double _width;
};

基于对象的使用：

Rectangle rectangle(10, 20);

cout << endl;
Figure fig;
/* function<void()> f = bind(&Rectangle::display, &rectangle, 1, 2); */
/* fig.setDisplayCallback(std::move(f)); */
fig.setDisplayCallback(bind(&Rectangle::display, &rectangle, 1, 2)); // bind 改变 display 的状态
fig.setAreaCallback(bind(&Rectangle::area, &rectangle));
func(fig);

`mem_fn` 成员函数适配器

class Number {
 public:
  Number(size_t data = 0): _data(data) {}

  void print() const {
    cout << _data << "  ";
  }

  //判断是不是偶数
  bool isEven() const {
    return (0 == _data % 2);
  }

  //判断是不是质数
  bool isPrime() const {
    if (1 == _data) {
      return false;
    }

    for (size_t idx = 2; idx <= _data / 2; ++idx) {
      if (0 == _data % idx) {
        return false;
      }
    }

    return true;
  }

  ~Number() = default;

 private:
  size_t _data;
};

int main(int argc, char *argv[]) {
  vector<Number> vec;
  for (size_t idx = 1; idx != 30; ++idx) {
    vec.push_back(Number(idx));
  }

  // for_each 与成员函数 print 并不能很好的适配，需要使用 mem_fn 进行适配
  for_each(vec.begin(), vec.end(), mem_fn(&Number::print));

  cout << endl << endl;
  auto it = remove_if(vec.begin(), vec.end(), mem_fn(&Number::isEven));
  vec.erase(it, vec.end());
  for_each(vec.begin(), vec.end(), mem_fn(&Number::print));
  cout << endl;

  //删除所有的质数
  cout << endl << endl;
  it = remove_if(vec.begin(), vec.end(), mem_fn(&Number::isPrime));
  vec.erase(it, vec.end());
  for_each(vec.begin(), vec.end(), mem_fn(&Number::print));
  cout << endl;
  return 0;
}

STL 算法

概述

算法的分类

一元函数以及一元断言/一元谓词

非修改式算法 for_each

修改式算法 remove_if

vector 的 push_back 操作导致迭代器失效

bind1st 与 bind2nd

bind