STL之remove算法详解

算法描述

接口

template<class ForwardIterator, class Type>
 ForwardIterator remove(
      ForwardIterator _First, 
      ForwardIterator _Last, 
      const Type& _Val
   );

功能

将一个指定的值从指定的区间中[first,last)“删除”，这里的“删除”是指：把区间内”指定值”的位置腾出，用copy的方式把后面”非指定值”逐一的往前移动。
比如：
序列（1234）remove 2后，返回的序列是 1344（3被复制到2的位置，4被复制到3的位置）。

原理

第一层算法：

template<class _FwdIt, class _Ty> inline
_FwdIt remove(_FwdIt _First, _FwdIt _Last, const _Ty& _Val)
{   
    // remove each matching _Val
    _First = find(_First, _Last, _Val);
    if (_First == _Last)
    {
        return (_First);// empty sequence, all done
    }
    else
    {   
        // nonempty sequence, worth doing
        _FwdIt _First1 = _First;
        return (_STDEXT unchecked_remove_copy(++_First1,
         _Last, _First, _Val));
    }
}

最底层算法：

/******************************************************
**_First:第一个待删除值的下一个位置
**_Last:指向目标容器最后一个元素的下一个位置
** _Val：待删除的值
**_Dest：返回值，初始值为目标容器的第一个指定位置
*********************************************************/
template<class _InIt, class _OutIt, class _Ty> inline
_OutIt _Remove_copy(_InIt _First, _InIt _Last, _OutIt _Dest, 
                    const _Ty& _Val, _Range_checked_iterator_tag)
{   
    //copy omitting each matching _Val
    for (; _First != _Last; ++_First)
    {
        if (!(*_First == _Val))
        {
            *_Dest++ = *_First;
        }   
    }

    return (_Dest);
}

特点

remove算法是稳定的，因为其他元素的相对位置并没有改变。同时remove算法并不能直接的删除特定元素，因此目标的容器大小不变。

算法应用

源码

#include "stdafx.h"
#include <string.h>
#include <algorithm>
#include <vector>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <iterator>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{

    vector<int> vecContainer;
    const int nLoop = 5;

    for (int i = 0; i < nLoop; ++i)
    {
        vecContainer.push_back(i);
    }

    vecContainer.insert(vecContainer.end(), 2);
    vecContainer.insert(vecContainer.end(), 5);
    vecContainer.insert(vecContainer.end(), 6);

    //0 1 2 3 4 2 5 6 
    vector<int> vecData(vecContainer);

    cout <<"before remove:"<<endl;
    copy(vecContainer.begin(), vecContainer.end(), 
         ostream_iterator<int>(cout," "));
    cout << endl;

    cout <<"after remove:"<<endl;
    remove(vecContainer.begin(), vecContainer.end(), 2);
    copy(vecContainer.begin(), vecContainer.end(), 
         ostream_iterator<int>(cout," "));
    cout << endl;

    //需要使用备份后的vecData
    cout <<"after erase:"<<endl;
    //推荐用法
    vecData.erase(remove(vecData.begin(),vecData.end(), 2), 
                  vecData.end());
    copy(vecData.begin(), vecData.end(),
         ostream_iterator<int>(cout," "));
    cout<<endl;

    return 0;
}

内存变化过程

运行结果

结论：使用remove删除成员后需要立即调用erase，确保真正的删除!