STL源码剖析——STL算法之remove删除算法

桃扇骨 2022-08-12 19:29 283阅读 0赞

前言

由于在前文的《STL算法剖析》中，源码剖析非常多，不方便学习，也不方便以后复习，这里把这些算法进行归类，对他们单独的源码剖析进行讲解。本文介绍的STL算法中的remove删除算法，源码中介绍了函数remove、remove_copy、remove_if、remove_copy_if、unique、unique_copy。并对这些函数的源码进行详细的剖析，并适当给出使用例子，具体详见下面源码剖析。

remove移除算法源码剖析

  1. // remove, remove_if, remove_copy, remove_copy_if
  3. //移除[first,last)区间内所有与value值相等的元素，并不是真正的从容器中删除这些元素(原容器的内容不会改变)
  4. //而是将结果复制到一个以result为起始位置的容器中。新容器可以与原容器重叠
  5. template <class _InputIter, class _OutputIter, class _Tp>
  6. _OutputIter remove_copy(_InputIter __first, _InputIter __last,
  7.                         _OutputIter __result, const _Tp& __value) {
  8.   __STL_REQUIRES(_InputIter, _InputIterator);
  9.   __STL_REQUIRES(_OutputIter, _OutputIterator);
  10.   __STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool,
  11.        typename iterator_traits<_InputIter>::value_type, _Tp);
  12.   for ( ; __first != __last; ++__first)//遍历容器
  13.     if (!(*__first == __value)) {//如果不相等
  14.       *__result = *__first;//赋值给新容器
  15.       ++__result;//新容器前进一个位置
  16.     }
  17.   return __result;
  18. }
  19. //移除[first,last)区间内被仿函数pred判断为true的元素,并不是真正的从容器中删除这些元素(原容器的内容不会改变)
  20. //而是将结果复制到一个以result为起始位置的容器中。新容器可以与原容器重叠
  21. template <class _InputIter, class _OutputIter, class _Predicate>
  22. _OutputIter remove_copy_if(_InputIter __first, _InputIter __last,
  23.                            _OutputIter __result, _Predicate __pred) {
  24.   __STL_REQUIRES(_InputIter, _InputIterator);
  25.   __STL_REQUIRES(_OutputIter, _OutputIterator);
  26.   __STL_UNARY_FUNCTION_CHECK(_Predicate, bool,
  27.              typename iterator_traits<_InputIter>::value_type);
  28.   for ( ; __first != __last; ++__first)//遍历容器
  29.     if (!__pred(*__first)) {//若pred判断为false
  30.       *__result = *__first;//赋值给新容器
  31.       ++__result;//新容器前进一个位置
  32.     }
  33.   return __result;
  34. }
  35. //移除[first,last)区间内所有与value值相等的元素,该操作不会改变容器大小，只是容器中元素值改变
  36. //即移除之后，重新整理容器的内容
  37. template <class _ForwardIter, class _Tp>
  38. _ForwardIter remove(_ForwardIter __first, _ForwardIter __last,
  39.                     const _Tp& __value) {
  40.   __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator);
  41.   __STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool,
  42.        typename iterator_traits<_ForwardIter>::value_type, _Tp);
  43.   __STL_CONVERTIBLE(_Tp, typename iterator_traits<_ForwardIter>::value_type);
  44.   __first = find(__first, __last, __value);//利用顺序查找找出第一个与value相等的元素
  45.   _ForwardIter __i = __first;
  46.   //下面调用remove_copy
  47.   return __first == __last ? __first 
  48.                            : remove_copy(++__i, __last, __first, __value);
  49. }
  50. //移除[first,last)区间内所有被pred判断为true的元素,该操作不会改变容器大小，只是容器中元素值改变
  51. //即移除之后，重新整理容器的内容
  52. template <class _ForwardIter, class _Predicate>
  53. _ForwardIter remove_if(_ForwardIter __first, _ForwardIter __last,
  54.                        _Predicate __pred) {
  55.   __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator);
  56.   __STL_UNARY_FUNCTION_CHECK(_Predicate, bool,
  57.                typename iterator_traits<_ForwardIter>::value_type);
  58.   __first = find_if(__first, __last, __pred);//利用顺序查找找出第一个与value相等的元素
  59.   _ForwardIter __i = __first;
  60.   //下面调用remove_copy_if
  61.   return __first == __last ? __first 
  62.                            : remove_copy_if(++__i, __last, __first, __pred);
  63. }
  64. //上面四个移除函数举例：
  65. /*
  66.     #include <iostream>     // std::cout
  67.     #include <algorithm>    // std::remove
  69.     bool IsOdd (int i) { return ((i%2)==1); }
  71.     int main () {
  72.       int myints[] = {10,20,31,30,20,11,10,20};      // 10 20 31 30 20 11 10 20
  74.       std::vector<int> myvector (8);
  75.       std::remove_copy (myints,myints+8,myvector.begin(),20); // 10 31 30 11 10 0 0 0
  76.       std::cout << "myvector contains:";
  77.       for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)
  78.         std::cout << ' ' << *it;
  79.       std::cout << '\n';
  81.       // bounds of range:
  82.       int* pbegin = myints;                          // ^
  83.       int* pend = myints+sizeof(myints)/sizeof(int); // ^                       ^
  84.       pend = std::remove (pbegin, pend, 20);         // 10 31 30 11 10 ?  ?  ?
  85.                                                      // ^              ^
  86.       std::cout << "range contains:";
  87.       for (int* p=pbegin; p!=pend; ++p)
  88.         std::cout << ' ' << *p;
  89.       std::cout << '\n';
  91.       std::vector<int> myvector2 (7);
  92.       std::remove_copy_if (myints,myints+7,myvector2.begin(),IsOdd);
  93.       std::cout << "myvector2 contains:";
  94.       for (std::vector<int>::iterator it=myvector2.begin(); it!=myvector2.end(); ++it)
  95.         std::cout << ' ' << *it;
  96.       std::cout << '\n';
  98.       pend = std::remove_if (pbegin, pend, IsOdd);   // 10 30 10 ? ? ? ? ?
  99.                                                      // ^       ^
  100.       std::cout << "the range contains:";
  101.       for (int* p=pbegin; p!=pend; ++p)
  102.         std::cout << ' ' << *p;
  103.       std::cout << '\n';  
  105.       return 0;
  106.     }
  107.     Output:
  108.     myvector contains: 10 31 30 11 10 0 0 0
  109.     range contains: 10 31 30 11 10
  110.     myvector2 contains: 10 30 10 10 0 0 0
  111.     the range contains: 10 30 10
  112. */
  114. // unique and unique_copy
  116. template <class _InputIter, class _OutputIter, class _Tp>
  117. _OutputIter __unique_copy(_InputIter __first, _InputIter __last,
  118.                           _OutputIter __result, _Tp*) {
  119.   _Tp __value = *__first;
  120.   *__result = __value;
  121.   while (++__first != __last)
  122.     if (!(__value == *__first)) {
  123.       __value = *__first;
  124.       *++__result = __value;
  125.     }
  126.   return ++__result;
  127. }
  128. //若result类型为output_iterator_tag，则调用该函数
  129. template <class _InputIter, class _OutputIter>
  130. inline _OutputIter __unique_copy(_InputIter __first, _InputIter __last,
  131.                                  _OutputIter __result, 
  132.                                  output_iterator_tag) {
  133.         //判断first的value_type类型，根据不同类型调用不同函数
  134.   return __unique_copy(__first, __last, __result, __VALUE_TYPE(__first));
  135. }
  136. //若result类型为forward_iterator_tag，则调用该函数
  137. template <class _InputIter, class _ForwardIter>
  138. _ForwardIter __unique_copy(_InputIter __first, _InputIter __last,
  139.                            _ForwardIter __result, forward_iterator_tag) {
  140.   *__result = *__first;//记录第一个元素
  141.   while (++__first != __last)//遍历区间
  142.       //若不存在相邻重复元素，则继续记录到目标区result
  143.     if (!(*__result == *__first))
  144.       *++__result = *__first;//记录元素到目标区
  145.   return ++__result;
  146. }
  147. unique_copy将区间[first,last)内元素复制到以result开头的区间上，但是如果存在相邻重复元素时，只复制其中第一个元素
  148. //和unique一样，这里也有两个版本
  149. /*
  150. 函数原型：
  151. equality (1)    
  152.     template <class InputIterator, class OutputIterator>
  153.     OutputIterator unique_copy (InputIterator first, InputIterator last,
  154.                               OutputIterator result);
  155. predicate (2)    
  156.     template <class InputIterator, class OutputIterator, class BinaryPredicate>
  157.     OutputIterator unique_copy (InputIterator first, InputIterator last,
  158.                               OutputIterator result, BinaryPredicate pred);
  159. */
  160. //版本一
  161. template <class _InputIter, class _OutputIter>
  162. inline _OutputIter unique_copy(_InputIter __first, _InputIter __last,
  163.                                _OutputIter __result) {
  164.   __STL_REQUIRES(_InputIter, _InputIterator);
  165.   __STL_REQUIRES(_OutputIter, _OutputIterator);
  166.   __STL_REQUIRES(typename iterator_traits<_InputIter>::value_type,
  167.                  _EqualityComparable);
  168.   if (__first == __last) return __result;
  169.   //根据result迭代器的类型，调用不同的函数
  170.   return __unique_copy(__first, __last, __result,
  171.                        __ITERATOR_CATEGORY(__result));
  172. }
  174. template <class _InputIter, class _OutputIter, class _BinaryPredicate,
  175.           class _Tp>
  176. _OutputIter __unique_copy(_InputIter __first, _InputIter __last,
  177.                           _OutputIter __result,
  178.                           _BinaryPredicate __binary_pred, _Tp*) {
  179.   __STL_BINARY_FUNCTION_CHECK(_BinaryPredicate, bool, _Tp, _Tp);
  180.   _Tp __value = *__first;
  181.   *__result = __value;
  182.   while (++__first != __last)
  183.     if (!__binary_pred(__value, *__first)) {
  184.       __value = *__first;
  185.       *++__result = __value;
  186.     }
  187.   return ++__result;
  188. }
  190. template <class _InputIter, class _OutputIter, class _BinaryPredicate>
  191. inline _OutputIter __unique_copy(_InputIter __first, _InputIter __last,
  192.                                  _OutputIter __result,
  193.                                  _BinaryPredicate __binary_pred,
  194.                                  output_iterator_tag) {
  195.   return __unique_copy(__first, __last, __result, __binary_pred,
  196.                        __VALUE_TYPE(__first));
  197. }
  199. template <class _InputIter, class _ForwardIter, class _BinaryPredicate>
  200. _ForwardIter __unique_copy(_InputIter __first, _InputIter __last,
  201.                            _ForwardIter __result, 
  202.                            _BinaryPredicate __binary_pred,
  203.                            forward_iterator_tag) {
  204.   __STL_BINARY_FUNCTION_CHECK(_BinaryPredicate, bool,
  205.      typename iterator_traits<_ForwardIter>::value_type,
  206.      typename iterator_traits<_InputIter>::value_type);
  207.   *__result = *__first;
  208.   while (++__first != __last)
  209.     if (!__binary_pred(*__result, *__first)) *++__result = *__first;
  210.   return ++__result;
  211. }
  212. //版本二
  213. template <class _InputIter, class _OutputIter, class _BinaryPredicate>
  214. inline _OutputIter unique_copy(_InputIter __first, _InputIter __last,
  215.                                _OutputIter __result,
  216.                                _BinaryPredicate __binary_pred) {
  217.   __STL_REQUIRES(_InputIter, _InputIterator);
  218.   __STL_REQUIRES(_OutputIter, _OutputIterator);
  219.   if (__first == __last) return __result;
  220.   //根据result迭代器的类型，调用不同的函数
  221.   return __unique_copy(__first, __last, __result, __binary_pred,
  222.                        __ITERATOR_CATEGORY(__result));
  223. }
  224. //移除区间[first,last)相邻连续重复的元素
  225. //unique有两个版本
  226. //功能：Removes all but the first element from every consecutive group of equivalent elements in the range [first,last).
  227. /*
  228. 函数原型：
  229. equality (1)：版本一采用operator==    
  230.     template <class ForwardIterator>
  231.     ForwardIterator unique (ForwardIterator first, ForwardIterator last);
  232. predicate (2)：版本二采用pred操作    
  233.     template <class ForwardIterator, class BinaryPredicate>
  234.     ForwardIterator unique (ForwardIterator first, ForwardIterator last,
  235.                           BinaryPredicate pred);
  236. */
  237. //版本一
  238. template <class _ForwardIter>
  239. _ForwardIter unique(_ForwardIter __first, _ForwardIter __last) {
  240.   __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator);
  241.   __STL_REQUIRES(typename iterator_traits<_ForwardIter>::value_type,
  242.                  _EqualityComparable);
  243.   __first = adjacent_find(__first, __last);//找出第一个相邻元素的起始位置
  244.   return unique_copy(__first, __last, __first);//调用unique_copy完成操作
  245. }
  246. //版本二
  247. template <class _ForwardIter, class _BinaryPredicate>
  248. _ForwardIter unique(_ForwardIter __first, _ForwardIter __last,
  249.                     _BinaryPredicate __binary_pred) {
  250.   __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator);
  251.   __STL_BINARY_FUNCTION_CHECK(_BinaryPredicate, bool, 
  252.       typename iterator_traits<_ForwardIter>::value_type,
  253.       typename iterator_traits<_ForwardIter>::value_type);
  254.   __first = adjacent_find(__first, __last, __binary_pred);//找出第一个相邻元素的起始位置
  255.   return unique_copy(__first, __last, __first, __binary_pred);//调用unique_copy完成操作
  256. }

参考资料：

《STL源码剖析》侯捷

发表评论

表情：
评论列表 （有 0 条评论，283人围观）

还没有评论，来说两句吧...

相关阅读

    相关 【STL源码剖析】Sort算法

    前言：sort算法必须拿出来单独将，因为它是STL所有算法中最复杂最庞大的一个，就像我肯定会把copy算法单独列出来一样，这两个算法太重要了。 提示：STL算法特点是，前两个

    亦凉亦凉/ 0 赞/ 314 阅读