STL插入排序std::upper_bound和std::lower_bound的使用

1. 使用vector进行排序插入
    如果我们有个vector容器,如std::vector vMyVec,里面现在已经有1,3,5,7, 四个元素,现在需要往1,3之间插入2这个元素,那怎么办呢,更或者vector里面是个自定义的类型,需要做这种插入操作,那可以采用下面的方法

#include <vector>
#include <algorithm>
class CEntity
{
public:
    CEntity( int nValue=0 ):m_nValue(nValue)
    {

    }
    int m_nValue;
};

class CLess
{
public:
    bool operator()( const CEntity& lh, const CEntity& rh )
    {
        //这里还可以进行一些自定义的判断方式

        return lh.m_nValue < rh.m_nValue;
    }
};
int _tmain(int argc, _TCHAR* argv[])
{
         std::vector<CEntity> vEntity1;
    std::vector<CEntity> vEntity2;
    for ( int n=0; n<10; n++ )
    {
        nValue = rand()%10;
        vEntity1.insert(std::upper_bound(vEntity1.begin(),vEntity1.end(),CEntity(nValue),CLess()), CEntity(nValue) );
        vEntity2.push_back( CEntity(nValue) );
    }
}

2. std::upper_bound 的通用class Predicate
当我们要对std容器进行自定义排序插入操作，需要用到std::upper_bound和std::lower_bound,这两个函数都需要提供自定义的排序类，这里讨论的就是实现这个可通用的实现排序类：

template<typename _TKey, typename _TData>
class CKeyData
{
public:
    CKeyData(const _TKey& k, const _TData& d):m_Key(k)
        , m_Data(d)
    {

    }
    ~CKeyData()
    {

    }
    _TKey m_Key;
    const _TData& m_Data;
};

template<typename _TKey, typename _TData>
class CKeyUpSort
{
public:
    bool operator()( const CKeyData<_TKey,_TData>& lh, const CKeyData<_TKey,_TData>& rh )
    {
        return lh.m_Key > rh.m_Key;
    }
};

template<typename _TKey, typename _TData>
class CKeyLowSort
{
public:
    bool operator()( const CKeyData<_TKey,_TData>& lh, const CKeyData<_TKey,_TData>& rh )
    {
        return lh.m_Key < rh.m_Key;
    }
};

class CMyData
{
public:
    CMyData( int nId ):m_nId(nId)
    {

    }
    int m_nId;
};

int main(int argc, char *argv[])
{
    //假设现在有一个无序的实体列表
    typedef std::list<CMyData> MyList;
    MyList listMyData;
    for ( int n=0; n<10; n++ )
    {
        listMyData.push_back(CMyData(rand()%10));
    }

    typedef CKeyData<int,CMyData> MyKeyData;
    typedef CKeyUpSort<int,CMyData> MySort;
    std::list<MySort> listMy;
    MyList::iterator itr = listMyData.begin();
    MyList::iterator itrE = listMyData.end();
    for ( ; itr!=itrE; ++itr )
    {
        CMyData& data = *itr;
        //以data.m_nId为键值，进行降序插入
        MyKeyData keydata(data.m_nId,data);
        listMy.insert( std::upper_bound(listMy.begin(),listMy.end(),keydata,MySort()), keydata );
    }

    return 0;
}