首页 > 代码库 > 【STL源码学习】STL算法学习之一

【STL源码学习】STL算法学习之一

2024-07-06 12:25:30   222人阅读

第一章：引子

STL包含的算法头文件有三个：<algorithm><numeric><functional>,其中最大最常用的是<algorithm>，今天学习的是<algorithm>包含的算法中的第一部分：非修改顺序操作算法。

接下来学习的算法基于C++11标准，较老的IDE会支持不全面或者部分算法不支持。 

第二章：原型解析

 如分类名称体现的信息，本节的所有函数都不会修改序列，并且原理上都是顺序遍历迭代器实现的。

 all_of

函数原型：
template <class InputIterator, class UnaryPredicate>
 bool all_of (InputIterator first, InputIterator last, UnaryPredicate pred);
函数作用：
比较迭代器区间的元素是否都满足pred的条件，就像名字一样，全部满足就返回true，否则返回false。
函数使用：
前闭后开区间[first,last)，first和last为指向同一个容器对象的有效迭代器。
pred应当是一个单参且返回值为bool类型的函数，参数类型和迭代器的实例化类型一致。
使用示例：
bool foobool(int a)
{
if(10 == a)
return true;
return false;
}
void test_all_of()
{
bool bret = false;
vector<int>::iterator itor1;
vector<int>::iterator itor2;
vector<int> ivec(10, 10);
itor1 = ivec.begin();
itor2 = ivec.end();
bret = all_of(itor1, itor2, foobool);
if(bret)
cout << "all_of return true" << endl;
}
any_of
函数原型：
template <class InputIterator, class UnaryPredicate>
 bool any_of (InputIterator first, InputIterator last, UnaryPredicate pred);
函数作用：
和all_of联系起来使用，如果有任何一个迭代器区间的元素满足要求就返回true，否则返回false。
none_of
函数原型：
template <class InputIterator, class UnaryPredicate>
 bool none_of (InputIterator first, InputIterator last, UnaryPredicate pred);
函数作用：
和all_of、any_of联系起来使用，如果区间所有的元素都不满足pred的条件，就返回true，否则false。
for_each
函数原型：
template <class InputIterator, class Function>
  Function for_each (InputIterator first, InputIterator last, Function fn);
函数作用：
对迭代区间的每一个元素都应用函数fn。
函数使用：
前闭后开区间[first,last)，first和last为指向同一个容器对象的有效迭代器。
fun为接收单个参数的函数，返回值不限定，参数类型与迭代器实例类型保持一致。
find
函数原型：
template <class InputIterator, class T>
  InputIterator find (InputIterator first, InputIterator last, const T& val);
函数作用：
迭代器区间[first,last)如果找到指定的元素就返回指向元素的迭代器，否则返回last。
函数使用：
前闭后开区间[first,last)，first和last为指向同一个容器对象的有效迭代器。
find_if
函数原型：
template <class InputIterator, class UnaryPredicate>
  InputIterator find_if (InputIterator first, InputIterator last, UnaryPredicate pred);
函数作用：
迭代器区间[first,last)，如果存在满足pred条件的元素就返回指向该元素的迭代器，否则返回last
函数使用：
前闭后开区间[first,last)，first和last为指向同一个容器对象的有效迭代器。
pred应当是一个单参且返回值为bool类型的函数，参数类型和迭代器的实例化类型一致。
find_if_not
函数原型：
template <class InputIterator, class UnaryPredicate>
  InputIterator find_if_not (InputIterator first, InputIterator last, UnaryPredicate pred);
函数作用：
迭代器区间[first,last)，如果存在不满足pred条件的元素就返回指向该元素的迭代器，否则返回last。
函数使用：
同find_if
find_end
函数原型：
template <class ForwardIterator1, class ForwardIterator2>
  ForwardIterator1 find_end (ForwardIterator1 first1, ForwardIterator1 last1,ForwardIterator2 first2, ForwardIterator2 last2);
template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
  ForwardIterator1 find_end (ForwardIterator1 first1, ForwardIterator1 last1,ForwardIterator2 first2, ForwardIterator2 last2,BinaryPredicate pred);
函数作用：
如果第二组迭代器指向的元素被包含在第一组迭代器中，则返回第一组迭代器中最后一个包含的开始位置，否则返回last1.
好拗口啊，看函数示例好理解一些。
函数有两个重载版本，分别用==和pred进行相等判断。
函数使用：
void test_find_end()
{
int array1[] = {1, 2, 3, 4, 5, 1, 2, 3};
int array2[] = {1, 2, 3};
int* ret = NULL;
ret = find_end(array1, array1+8, array2, array2+3);
if(ret != array1+8)
cout << "find array2 last contained in array1, position is " << ret - array1 << endl;
}
find_first_of
函数原型：
template <class InputIterator, class ForwardIterator>
  ForwardIterator1 find_first_of (InputIterator first1, InputIterator last1, ForwardIterator first2, ForwardIterator last2);
template <class InputIterator, class ForwardIterator, class BinaryPredicate>
  ForwardIterator1 find_first_of (InputIterator first1, InputIterator last1, ForwardIterator first2, ForwardIterator last2,BinaryPredicate pred);
函数作用：
和find_end很类似的作用，返回第二个迭代器区间第一处被包含在第一个迭代器区间的开始位置，成功则返回不等于last1的迭代器，否则返回last1.
adjacent_find
函数原型：
template <class ForwardIterator>
  ForwardIterator adjacent_find (ForwardIterator first, ForwardIterator last);
template <class ForwardIterator, class BinaryPredicate>
  ForwardIterator adjacent_find (ForwardIterator first, ForwardIterator last, BinaryPredicate pred);
函数作用：
查找迭代器区间两个相邻的相等元素，并返回指向第一个相邻元素的迭代器，否则返回last。
count
函数原型：
template <class InputIterator, class T>
 typename iterator_traits<InputIterator>::difference_type
   count (InputIterator first, InputIterator last, const T& val);
函数作用：
返回迭代器区间值等于val的元素的数量。
count_if
函数原型：
template <class InputIterator, class Predicate>
 typename iterator_traits<InputIterator>::difference_type
   count_if (InputIterator first, InputIterator last, UnaryPredicate pred);
函数作用：
返回迭代器区间令pred返回true的元素的数量
mismatch
函数原型：
template <class InputIterator1, class InputIterator2>
 pair<InputIterator1, InputIterator2>
   mismatch (InputIterator1 first1, InputIterator1 last1,
             InputIterator2 first2);
template <class InputIterator1, class InputIterator2, class BinaryPredicate>
 pair<InputIterator1, InputIterator2>
   mismatch (InputIterator1 first1, InputIterator1 last1,
             InputIterator2 first2, BinaryPredicate pred);
函数作用：
比较[first1,last1)区间的元素与first2指向的元素，并返回第一处差异的元素pair，是否一致的判定为pred或==，总感觉这个函数存在缺陷，我该如何界定first2何时结束？会不会访问越界，搞清楚之前不使用这个函数。
equal
函数原型：
template <class InputIterator1, class InputIterator2>
 bool equal (InputIterator1 first1, InputIterator1 last1,
             InputIterator2 first2);
template <class InputIterator1, class InputIterator2, class BinaryPredicate>
 bool equal (InputIterator1 first1, InputIterator1 last1,
             InputIterator2 first2, BinaryPredicate pred);
函数作用：
比较[first1,last1)区间的元素是否全部==（或满足pred）first2指向的区间，同样认为是一个危险的函数，first2的区间长度需要调用者确保是大于first1的区间，但危险程度要小于mismatch。
is_permutation
函数原型：
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 pred);
函数作用：
内部调用了mismatch，将之打入冷宫吧。
search
函数原型：
template <class ForwardIterator1, class ForwardIterator2>
  ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2);
template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
  ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
函数作用：
返回第二个迭代器区间的元素第一次被包含第一个迭代器区间的首元素的地址，换一种类比的方式来讲：正向查找子串第一次被包含的位置。
search_n
函数原型：
template <class ForwardIterator, class Size, class T>
  ForwardIterator search_n (ForwardIterator first, ForwardIterator last, Size count, const T& val);
template <class ForwardIterator, class Size, class T, class BinaryPredicate>
  ForwardIterator search_n ( ForwardIterator first, ForwardIterator last, Size count, const T& val, BinaryPredicate pred );
函数作用：
search的一个分支，第二个迭代器区间替换为count个val元素，其他一样的。
第三张：小结

这部分的算法都支持STL的容器，也不仅支持容器，只要具有和迭代器一样的++、--、==、=、*等的类型，比如普通指针都是支持的。 


联系
我们