template<class T>
class MyMap
{
public:
MyMap( int _nSize = 1 )
{
Init(_nSize);
}
~MyMap()
{
SAFE_DELETE_ARRAY(ayKey);
SAFE_DELETE_ARRAY(ayData);
}
void Init( int _nSize )
{
nMaxSize = _nSize;
nNowSize = 0;
ayKey = new int[nMaxSize];
ayData = new T[nMaxSize];
memset( ayKey, -1, sizeof(int) * nMaxSize );
}
bool insert( int _nKey, T _Val )
{
int nIndex = find(_nKey);
if( nMaxSize != nIndex )
{
ayData[nIndex] = _Val;
return true;
}
for(int i = 0; i < nMaxSize; ++i)
{
if( -1 == ayKey[i] )
{
ayKey[i] = _nKey;
ayData[i] = _Val;
nNowSize++;
return true;
}
}
// 빈 공간이 없다!
int* ayKey2 = new int[nMaxSize * 2];
T* ayData2 = new T[nMaxSize * 2];
memset( ayKey2, -1, sizeof(int) * nMaxSize * 2 );
memcpy(ayKey2, ayKey, sizeof(int) * nMaxSize );
memcpy(ayData2, ayData, sizeof(T) * nMaxSize );
SAFE_DELETE_ARRAY(ayKey);
SAFE_DELETE_ARRAY(ayData);
ayKey = ayKey2;
ayData = ayData2;
nMaxSize = nMaxSize * 2;
return insert(_nKey, _Val);
}
int find( int _nKey )
{
for(int i = 0; i < nMaxSize; ++i)
{
if( _nKey == ayKey[i] )
return i;
}
return nMaxSize; // 찾지 못 함!
}
bool erase( int _nKey )
{
int nIndex = find(_nKey);
if( nMaxSize != nIndex )
{
ayKey[nIndex] = -1;
nNowSize--;
return true;
}
return false;
}
int GetMaxSize()
{
return nMaxSize;
}
int GetNowSize()
{
return nNowSize;
}
T* KeyToValue(int _nKey)
{
int nIndex = find(_nKey);
if( nMaxSize != nIndex )
return ArrayIndexToValue( nIndex );
return NULL;
}
int ArrayIndexToKey(int _nIndex)
{
if( 0 > _nIndex || nMaxSize - 1 < _nIndex ) // 배열 바운더리 체크
{
_asm int 3
return nMaxSize;
}
return ayKey[_nIndex];
}
T* ArrayIndexToValue(int _nIndex)
{
if( 0 > _nIndex || nMaxSize - 1 < _nIndex ) // 배열 바운더리 체크
{
_asm int 3
return NULL;
}
return &ayData[_nIndex];
}
int GetMaximumValueKey()
{
int nKey = -1;
int nValue = 0;
for(int i = 0; i < nMaxSize;++i)
{
if( nValue < ayData[i] )
{
nKey = ayKey[i];
nValue = ayData[i];
}
}
return nKey;
}
void clear()
{
memset( ayKey, -1, sizeof(int) * nMaxSize );
}
private:
int* ayKey;
T* ayData;
int nMaxSize;
int nNowSize;
};
속도 검증 코드
MapTest.zip