STL算法之remove刪除算法 · STL源碼剖析

### 前言 ? 由于在前文的《[STL算法剖析](http://blog.csdn.net/chenhanzhun/article/details/39698523)》中，源碼剖析非常多，不方便學習，也不方便以后復習，這里把這些算法進行歸類，對他們單獨的源碼剖析進行講解。本文介紹的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 = *__first; *__result = __value; while (++__first != __last) if (!(__value == *__first)) { __value = *__first; *++__result = __value; } return ++__result; } //若result類型為output_iterator_tag，則調用該函數 template <class _InputIter, class _OutputIter> inline _OutputIter __unique_copy(_InputIter __first, _InputIter __last, _OutputIter __result, output_iterator_tag) { //判斷first的value_type類型，根據不同類型調用不同函數 return __unique_copy(__first, __last, __result, __VALUE_TYPE(__first)); } //若result類型為forward_iterator_tag，則調用該函數 template <class _InputIter, class _ForwardIter> _ForwardIter __unique_copy(_InputIter __first, _InputIter __last, _ForwardIter __result, forward_iterator_tag) { *__result = *__first;//記錄第一個元素 while (++__first != __last)//遍歷區間 //若不存在相鄰重復元素，則繼續記錄到目標區result if (!(*__result == *__first)) *++__result = *__first;//記錄元素到目標區 return ++__result; } ////unique_copy將區間[first,last)內元素復制到以result開頭的區間上，但是如果存在相鄰重復元素時，只復制其中第一個元素 //和unique一樣，這里也有兩個版本 /* 函數原型： equality (1) template <class InputIterator, class OutputIterator> OutputIterator unique_copy (InputIterator first, InputIterator last, OutputIterator result); predicate (2) template <class InputIterator, class OutputIterator, class BinaryPredicate> OutputIterator unique_copy (InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate pred); */ //版本一 template <class _InputIter, class _OutputIter> inline _OutputIter unique_copy(_InputIter __first, _InputIter __last, _OutputIter __result) { __STL_REQUIRES(_InputIter, _InputIterator); __STL_REQUIRES(_OutputIter, _OutputIterator); __STL_REQUIRES(typename iterator_traits<_InputIter>::value_type, _EqualityComparable); if (__first == __last) return __result; //根據result迭代器的類型，調用不同的函數 return __unique_copy(__first, __last, __result, __ITERATOR_CATEGORY(__result)); } template <class _InputIter, class _OutputIter, class _BinaryPredicate, class _Tp> _OutputIter __unique_copy(_InputIter __first, _InputIter __last, _OutputIter __result, _BinaryPredicate __binary_pred, _Tp*) { __STL_BINARY_FUNCTION_CHECK(_BinaryPredicate, bool, _Tp, _Tp); _Tp __value = *__first; *__result = __value; while (++__first != __last) if (!__binary_pred(__value, *__first)) { __value = *__first; *++__result = __value; } return ++__result; } template <class _InputIter, class _OutputIter, class _BinaryPredicate> inline _OutputIter __unique_copy(_InputIter __first, _InputIter __last, _OutputIter __result, _BinaryPredicate __binary_pred, output_iterator_tag) { return __unique_copy(__first, __last, __result, __binary_pred, __VALUE_TYPE(__first)); } template <class _InputIter, class _ForwardIter, class _BinaryPredicate> _ForwardIter __unique_copy(_InputIter __first, _InputIter __last, _ForwardIter __result, _BinaryPredicate __binary_pred, forward_iterator_tag) { __STL_BINARY_FUNCTION_CHECK(_BinaryPredicate, bool, typename iterator_traits<_ForwardIter>::value_type, typename iterator_traits<_InputIter>::value_type); *__result = *__first; while (++__first != __last) if (!__binary_pred(*__result, *__first)) *++__result = *__first; return ++__result; } //版本二 template <class _InputIter, class _OutputIter, class _BinaryPredicate> inline _OutputIter unique_copy(_InputIter __first, _InputIter __last, _OutputIter __result, _BinaryPredicate __binary_pred) { __STL_REQUIRES(_InputIter, _InputIterator); __STL_REQUIRES(_OutputIter, _OutputIterator); if (__first == __last) return __result; //根據result迭代器的類型，調用不同的函數 return __unique_copy(__first, __last, __result, __binary_pred, __ITERATOR_CATEGORY(__result)); } //移除區間[first,last)相鄰連續重復的元素 //unique有兩個版本 //功能：Removes all but the first element from every consecutive group of equivalent elements in the range [first,last). /* 函數原型： equality (1)：版本一采用operator== template <class ForwardIterator> ForwardIterator unique (ForwardIterator first, ForwardIterator last); predicate (2)：版本二采用pred操作 template <class ForwardIterator, class BinaryPredicate> ForwardIterator unique (ForwardIterator first, ForwardIterator last, BinaryPredicate pred); */ //版本一 template <class _ForwardIter> _ForwardIter unique(_ForwardIter __first, _ForwardIter __last) { __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator); __STL_REQUIRES(typename iterator_traits<_ForwardIter>::value_type, _EqualityComparable); __first = adjacent_find(__first, __last);//找出第一個相鄰元素的起始位置 return unique_copy(__first, __last, __first);//調用unique_copy完成操作 } //版本二 template <class _ForwardIter, class _BinaryPredicate> _ForwardIter unique(_ForwardIter __first, _ForwardIter __last, _BinaryPredicate __binary_pred) { __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator); __STL_BINARY_FUNCTION_CHECK(_BinaryPredicate, bool, typename iterator_traits<_ForwardIter>::value_type, typename iterator_traits<_ForwardIter>::value_type); __first = adjacent_find(__first, __last, __binary_pred);//找出第一個相鄰元素的起始位置 return unique_copy(__first, __last, __first, __binary_pred);//調用unique_copy完成操作 } ~~~ 參考資料：《STL源碼剖析》侯捷