• 侯捷 C++ STL标准库和泛型编程 —— 6 算法 + 7 仿函数

    6 算法

    算法的标准样式：需要传进去两个指针

    image-20230903084435290

    6.1 算法源码

    6.1.1 accumulate

    两个版本：

    1. 元素累加到 init 上

      template <class InputIterator, class T>
T accumulate(InputIterator first, InputIterator last, T init)
{
	for (; first != last; ++first)
		init = init + *first; // 累加到init
	return init;
}

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7

    2. 元素累运算到 init 上

      template <class InputIterator, class T, class BinaryOperation>
T accumulate(InputIterator first, InputIterator last, T init, BinaryOperation binary_op)
{
	for (; first != last; ++first)
		init = binary_op(init, *first); // 累运算到init上
	return init;
}

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7

      这里可以用任意的二元操作（可以是函数，也可以是仿函数）

    测试：

    #include      // std::cout
#include    // std::minus
#include       // std::accumulate

// 函数
int myfunc (int x, int y) {return x+2*y;}

// 仿函数
struct myclass {
	int operator()(int x, int y) {return x+3*y;}
} myobj;

void test_accumulate()
{
  cout << "\ntest_accumulate().......... \n";	
  int init = 100;
  int nums[] = {10,20,30};

  cout << "using default accumulate: ";
  cout << accumulate(nums,nums+3,init);  //160
  cout << '\n';

  cout << "using functional's minus: ";
  cout << accumulate(nums, nums+3, init, minus<int>()); //40
  cout << '\n';

  cout << "using custom function: ";
  cout << accumulate(nums, nums+3, init, myfunc);	//220
  cout << '\n';

  cout << "using custom object: ";
  cout << accumulate(nums, nums+3, init, myobj);	//280
  cout << '\n';
}															 

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    6.1.2 for_each

    让范围里的所有元素都依次做同一件事情

    Function 可以是函数也可以是仿函数

    template <class InputIterator, class Function>
Function for_each(InputIterator first, InputIterator last, Function f)
{
	for (; first != last; ++first) {
		f(*first);
	}
	return f;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    与C++11中的 range-based for statement 差不多

    6.1.3 replace…

    • replace：范围内的所有等于 old_value 的，都被 new_value 取代

      template <class ForwardIterator, class T>
void replace(ForwardIterator first, ForwardIterator last,
	const T& old_value, const T& new_value)
{
	for (; first != last; ++first)
	{
		if (*first == old_value) *first = new_value;	
	}
}

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9

    • replace_if：范围内所有满足 pred() 为 true 的元素都被 new_value 取代

      template <class ForwardIterator,class Predicate, class T>
void replace_if(ForwardIterator first, ForwardIterator last,
	Predicate pred, const T& new_value)
{
	for (; first != last; ++first)
	{
		if (pred(*first)) *first = new_value;
	}
}

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9

    • replace_copy：范围内的元素全部 copy 到新地方，其中所有等于 old_value 的，都被替代为 new_value

      template <class InputIterator, class OutputIterator, class T>
OutputIterator replace_copy(InputIterator first, InputIterator last,
	OutputIterator result, const T& old_value, const T& new_value)
{
	for (; first != last; ++first, ++result)
	{
		*result = (*first == old_value) ? new_value : *first;
	}
	return result;
}

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
    6.1.4 count…

    • count：在范围中计数值等于 value 的个数

      template <class InputIterator, class T>
typename iterator_traits<InputIterator>::difference_type // 返回类型
count (InputIterator first, InputIterator last, const T& value)
{
	typename iterator_traits<InputIterator>::difference_type n = 0;
	for (; first != last; ++first)
	{
		if (*first == value) ++n;
	}
	return n;
}

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11

    • count_if：在范围中计数满足条件 pred() 的个数

      template <class InputIterator, class Predicate>
typename iterator_traits<InputIterator>::difference_type // 返回类型
count_if (InputIterator first, InputIterator last, Predicate pred)
{
	typename iterator_traits<InputIterator>::difference_type n = 0;
	for (; first != last; ++first)
	{
		if (pred(*first)) ++n;
	}
	return n;
}

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11
    • 容器不带成员函数 count()：array，vector，forward_list，deque
    • 容器自带成员函数 count()：set / multiset，map / multimap，unordered_set / unordered_multiset，unordered_map / unorderd_multimap —— 所有关联式容器
    6.1 5 find…

    • find：在范围内找到值等于 value 的元素

      template <class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T& value)
{
	while (first != last && *first != value) ++first;
	return first;
}

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6

    • find_if：在范围内找到满足 pred() 的元素

      template <class InputIterator, class Predicate>
InputIterator find_if(InputIterator first, InputIterator last, Predicate pred)
{
	while (first != last && !pred(*first)) ++first;
	return first;
}

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6

    都是循序查找，效率低

    • 容器不带成员函数 find()：array，vector，forward_list，deque
    • 容器自带成员函数 find()：set / multiset，map / multimap，unordered_set / unordered_multiset，unordered_map / unorderd_multimap —— 所有关联式容器
    6.1.6 sort

    源码复杂

    测试：

    // 函数
bool myfunc (int i,int j) { return (i<j); }

//仿函数
struct myclass {
  bool operator() (int i,int j) { return (i<j);}
} myobj;

// 定义向量
int myints[] = {32,71,12,45,26,80,53,33};
vector<int> myvec(myints, myints+8);          // 32 71 12 45 26 80 53 33

// 用默认的比较(operator <)
sort(myvec.begin(), myvec.begin()+4);         //(12 32 45 71)26 80 53 33

// 用自己的函数作比较
sort(myvec.begin()+4, myvec.end(), myfunc); 	// 12 32 45 71(26 33 53 80)

// 用自己的仿函数作比较
sort(myvec.begin(), myvec.end(), myobj);      //(12 26 32 33 45 53 71 80)


// 用反向迭代器 reverse iterator 和默认的比较(operator <)
sort(myvec.rbegin(), myvec.rend());           // 80 71 53 45 33 32 26 12

// 用显式默认比较(operator <)
sort(myvec.begin(), myvec.end(), less<int>()); // 12 26 32 33 45 53 71 80   

// 使用另一个比较标准(operator >)
sort(myvec.begin(), myvec.end(), greater<int>()); // 80 71 53 45 33 32 26 12     

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 容器不带成员函数 sort()：array，vector，deque，所有关联式容器（本身就排好序了）
    • 容器自带成员函数 sort()：list，forward_list（只能用自带）

    reverse iterator：

    image-20230903101250832

    其中用的是 reverse_iterator —— iterator adapter

    6.1.7 binary_search

    二分查找是否存在目标元素（并不给予位置），使用前必须先排序；其主要使用 lower_bound() 来找到能放入 val 的最低位置，再判断该元素是否存在

    template <class ForwardIterator, class T>
bool binary_search(ForwardIterator first, ForwardIterator last, const T& value)
{
	first = lower_bound(first, last, value);
	return (first != last && !(value < *first));
    // first == last 就是序列中所有元素都小于value
    // first == last 时，*first是没有值的，所以需要先检查
    // value < *first 就是序列中没有等于value的
    
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    lower_bound()：用于在有序序列中查找==第一个大于等于==该值的元素（包括目标值本身），并返回一个指向该位置的迭代器

    • 如果目标值在序列中多次出现，返回第一个出现的位置
    • 如果目标值在序列中不存在，它将返回指向比目标值大的第一个元素位置，或者返回 last

    upper_bound()：用于在有序序列中查找==第一个大于==该值的元素（不包括目标值本身），并返回一个指向该位置的迭代器

    • 如果目标值在序列中多次出现，返回第一个大于目标值的位置
    • 如果目标值在序列中不存在，它将返回与 lower_bound() 一样的位置
    image-20230903112748261

    一样是前闭后开的原则，且他们都用的是二分查找的方法

    7 仿函数

    仿函数专门为算法服务，设计成一个函数/仿函数是为了能传入算法

    image-20230904081042763

    STL中的每个仿函数都继承了 binary_function / unary_function—— 融入到STL中

    STL规定每个 Adaptable Function（之后可以改造的函数）都应该继承其中一个（因为之后 Function Adapter 将会提问）

    // 一个操作数的操作，例如“!”
template <class Arg, class Result>
struct unary_function
{
	typedef Arg argument_type;
	typedef Result result_type;
};

// 两个操作数的操作，例如“+”
template <class Arg1, class Arg2, class Result>
struct binary_function
{
	typedef Arg1 first_argument_type;
	typedef Arg2 second_argument_type;
	typedef Result result_type;
};

// 理论大小都是0，实际上可能是1（如果有人继承，那就一定是0）

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    防函数是我们自己可能会写的，所以自己写的时候，如果想要融入STL，就要继承上面的两个之一

  • 相关阅读:
    数据结构--》连接世界的无限可能—— 图
    【SA8295P 源码分析 (四)】23 - QNX Ethernet MAC 驱动 之 emac1_config.conf 配置文件解析
    使用HTML制作静态网站作业——我的校园运动会(HTML+CSS)
    Webview+AppbarLayout上下滑动冲突
    17秒短视频竟引爆B站，吸引无数UP主、品牌轮番二创！
    【C++】宏函数的巧用
    Xception --tensorflow2.x
    dpdk环境搭建
    EDF文件格式/规格说明
    嵌入式C 语言中的三块技术难点
  • 原文地址：https://blog.csdn.net/WJwwwwwww/article/details/133513074