首页 > 代码库 > STL源码剖析——STL算法之remove删除算法
STL源码剖析——STL算法之remove删除算法
前言
由于在前文的《STL算法剖析》中,源码剖析非常多,不方便学习,也不方便以后复习,这里把这些算法进行归类,对他们单独的源码剖析进行讲解。本文介绍的STL算法中的remove删除算法,源码中介绍了函数remove、remove_copy、remove_if、remove_copy_if、unique、unique_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删除算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。