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;
-
}
阅读(8712) | 评论(0) | 转发(0) |