首页 > 代码库 > STL源码剖析——STL算法之remove删除算法

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

前言

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

remove移除算法源码剖析

// remove, remove_if, remove_copy, remove_copy_if

//移除[first,last)区间内所有与value值相等的元素,并不是真正的从容器中删除这些元素(原容器的内容不会改变)
//而是将结果复制到一个以result为起始位置的容器中。新容器可以与原容器重叠
template <class _InputIter, class _OutputIter, class _Tp>
_OutputIter remove_copy(_InputIter __first, _InputIter __last,
                        _OutputIter __result, const _Tp& __value) {
  __STL_REQUIRES(_InputIter, _InputIterator);
  __STL_REQUIRES(_OutputIter, _OutputIterator);
  __STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool,
       typename iterator_traits<_InputIter>::value_type, _Tp);
  for ( ; __first != __last; ++__first)//遍历容器
    if (!(*__first == __value)) {//如果不相等
      *__result = *__first;//赋值给新容器
      ++__result;//新容器前进一个位置
    }
  return __result;
}
//移除[first,last)区间内被仿函数pred判断为true的元素,并不是真正的从容器中删除这些元素(原容器的内容不会改变)
//而是将结果复制到一个以result为起始位置的容器中。新容器可以与原容器重叠
template <class _InputIter, class _OutputIter, class _Predicate>
_OutputIter remove_copy_if(_InputIter __first, _InputIter __last,
                           _OutputIter __result, _Predicate __pred) {
  __STL_REQUIRES(_InputIter, _InputIterator);
  __STL_REQUIRES(_OutputIter, _OutputIterator);
  __STL_UNARY_FUNCTION_CHECK(_Predicate, bool,
             typename iterator_traits<_InputIter>::value_type);
  for ( ; __first != __last; ++__first)//遍历容器
    if (!__pred(*__first)) {//若pred判断为false
      *__result = *__first;//赋值给新容器
      ++__result;//新容器前进一个位置
    }
  return __result;
}
//移除[first,last)区间内所有与value值相等的元素,该操作不会改变容器大小,只是容器中元素值改变
//即移除之后,重新整理容器的内容
template <class _ForwardIter, class _Tp>
_ForwardIter remove(_ForwardIter __first, _ForwardIter __last,
                    const _Tp& __value) {
  __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator);
  __STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool,
       typename iterator_traits<_ForwardIter>::value_type, _Tp);
  __STL_CONVERTIBLE(_Tp, typename iterator_traits<_ForwardIter>::value_type);
  __first = find(__first, __last, __value);//利用顺序查找找出第一个与value相等的元素
  _ForwardIter __i = __first;
  //下面调用remove_copy
  return __first == __last ? __first 
                           : remove_copy(++__i, __last, __first, __value);
}
//移除[first,last)区间内所有被pred判断为true的元素,该操作不会改变容器大小,只是容器中元素值改变
//即移除之后,重新整理容器的内容
template <class _ForwardIter, class _Predicate>
_ForwardIter remove_if(_ForwardIter __first, _ForwardIter __last,
                       _Predicate __pred) {
  __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator);
  __STL_UNARY_FUNCTION_CHECK(_Predicate, bool,
               typename iterator_traits<_ForwardIter>::value_type);
  __first = find_if(__first, __last, __pred);//利用顺序查找找出第一个与value相等的元素
  _ForwardIter __i = __first;
  //下面调用remove_copy_if
  return __first == __last ? __first 
                           : remove_copy_if(++__i, __last, __first, __pred);
}
//上面四个移除函数举例:
/*
	#include <iostream>     // std::cout
	#include <algorithm>    // std::remove

	bool IsOdd (int i) { return ((i%2)==1); }

	int main () {
	  int myints[] = {10,20,31,30,20,11,10,20};      // 10 20 31 30 20 11 10 20

	  std::vector<int> myvector (8);
	  std::remove_copy (myints,myints+8,myvector.begin(),20); // 10 31 30 11 10 0 0 0
	  std::cout << "myvector contains:";
	  for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)
		std::cout << ' ' << *it;
	  std::cout << '\n';
  
	  // bounds of range:
	  int* pbegin = myints;                          // ^
	  int* pend = myints+sizeof(myints)/sizeof(int); // ^                       ^
	  pend = std::remove (pbegin, pend, 20);         // 10 31 30 11 10 ?  ?  ?
													 // ^              ^
	  std::cout << "range contains:";
	  for (int* p=pbegin; p!=pend; ++p)
		std::cout << ' ' << *p;
	  std::cout << '\n';
  
	  std::vector<int> myvector2 (7);
	  std::remove_copy_if (myints,myints+7,myvector2.begin(),IsOdd);
	  std::cout << "myvector2 contains:";
	  for (std::vector<int>::iterator it=myvector2.begin(); it!=myvector2.end(); ++it)
		std::cout << ' ' << *it;
	  std::cout << '\n';
  
	  pend = std::remove_if (pbegin, pend, IsOdd);   // 10 30 10 ? ? ? ? ?
													 // ^       ^
	  std::cout << "the range contains:";
	  for (int* p=pbegin; p!=pend; ++p)
		std::cout << ' ' << *p;
	  std::cout << '\n';  

	  return 0;
	}
	Output:
	myvector contains: 10 31 30 11 10 0 0 0
	range contains: 10 31 30 11 10
	myvector2 contains: 10 30 10 10 0 0 0
	the range contains: 10 30 10
*/

// unique and unique_copy

template <class _InputIter, class _OutputIter, class _Tp>
_OutputIter __unique_copy(_InputIter __first, _InputIter __last,
                          _OutputIter __result, _Tp*) {
  _Tp __value = http://www.mamicode.com/*__first;>

参考资料:

《STL源码剖析》侯捷

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