한정된갯수의고유번호발급및재사용

UserPreferences

1 개요

1...N 까지의 숫자가 있고, 이 중에 하나를 뽑아내서 사용하다가 반환하고, 다시 뽑아내고...

즉 최대 N개의 아이템이 있다면 이들은 모두 다른 고유 번호를 가지고, 이 고유 번호는 항상 1부터 N까지의 범위 안에 들어가야 한다...는 전제를 만족시키기 위한 자료 구조.

사실 그냥 set 같은 거 써서 처리해도 되긴 하는데, 뭔가 좀 더 빠른 방법을 찾다보니, 예전에 들은 N개의 무작위 번호 추출이 생각나서 만들어봤다.

2 구현

#pragma once

template <typename T>
class cDistinctNumberArray
{
private:
    size_t           m_Count;       ///< 현재 사용 중인 고유 번호의 갯수
    size_t           m_Capacity;    ///< 최대로 할당할 수 있는 고유 번호의 갯수
    T*               m_NumberArray; ///< 고유 번호 목록
    BYTE*            m_TagArray;    ///< 에러 방지를 위한 별도 배열
    CRITICAL_SECTION m_Lock;        ///< 고유 번호 할당을 위한 락


public:
    /// \brief 생성자
    cDistinctNumberArray(size_t count)
    {
        StaticAssert(Generic::IsIntegral<T>::Value);

        m_Count = 0;
        m_Capacity = std::max(count, static_cast<size_t>(1));
        m_NumberArray = new T[m_Capacity];
        m_TagArray = new BYTE[m_Capacity];

        for (size_t i=0; i<m_Capacity; ++i)
        {
            m_NumberArray[i] = static_cast<T>(i);
            m_TagArray[i] = 0;
        }

        InitializeCriticalSection(&m_Lock);
    }

    /// \brief 소멸자
    ~cDistinctNumberArray()
    {
        delete [] m_NumberArray;
        delete [] m_TagArray;

        DeleteCriticalSection(&m_Lock);
    }


public:
    /// \brief 고유 번호를 할당한다.
    bool Allocate(T& value)
    {
        value = std::numeric_limits<T>::max();

        EnterCriticalSection(&m_Lock);

        if (m_Count < m_Capacity)
        {
            value = m_NumberArray[m_Count];
            m_TagArray[value] = 1;
            ++m_Count;
        }

        LeaveCriticalSection(&m_Lock);

        return value != std::numeric_limits<T>::max();
    }

    /// \brief 고유 번호를 반환한다.
    void Deallocate(T value)
    {
        EnterCriticalSection(&m_Lock);

        if (static_cast<size_t>(value) < m_Capacity && m_TagArray[value] == 1)
        {
            std::swap(m_NumberArray[value], m_NumberArray[m_Count-1]);
            m_TagArray[value] = 0;
            --m_Count;
        }

        LeaveCriticalSection(&m_Lock);
    }


private:
    /// \brief 복사 생성 금지
    cDistinctNumberArray(const cDistinctNumberArray<T>&) {}

    /// \brief 대입 금지
    cDistinctNumberArray<T>& operator = (const cDistinctNumberArray<T>&) { return *this; }
};

• CategoryAppProgramming