Reservable Queue

#pragma once

namespace MC
{
    template<typename T>
    class Queue
    {
    public:
        Queue() : m_head(0), m_tail(0), m_count(0), m_capacity(1), m_data(1) {}

        void Push(T&& value)
        {
            if (m_count == m_capacity)
            {
                Reallocate(CapacityLogic());
            }
            m_data[m_tail] = std::move(value);
            m_tail = (m_tail + 1) % m_capacity;
            m_count++;
        }

        void Push(const T& value)
        {
            if (m_count == m_capacity)
            {
                Reallocate(m_capacity * 2);
            }
            m_data[m_tail] = value;
            m_tail = (m_tail + 1) % m_capacity;
            m_count++;
        }

        inline void Pop()
        {
            Assert(!IsEmpty(), "Queue is empty");
            m_head = (m_head + 1) % m_capacity;
            m_count--;
        }

        inline T& Front()
        {
            Assert(!IsEmpty(), "Queue is empty");
            return m_data[m_head];
        }

        inline const T& Front() const
        {
            Assert(!IsEmpty(), "Queue is empty");
            return m_data[m_head];
        }

        inline bool IsEmpty() const
        {
            return m_count == 0;
        }

        void Reserve(size_t newCapacity)
        {
            if (newCapacity > m_capacity)
            {
                Reallocate(newCapacity);
            }
        }

        inline size_t Size() const
        {
            return m_count;
        }

    private:
        void Reallocate(size_t newCapacity)
        {
            std::vector<T> newData(newCapacity);
            if (m_tail > m_head)
            {
                std::move(m_data.begin() + m_head, m_data.begin() + m_tail, newData.begin());
            }
            else
            {
                std::move(m_data.begin() + m_head, m_data.end(), newData.begin());
                std::move(m_data.begin(), m_data.begin() + m_tail, newData.begin() + (m_capacity - m_head));
            }
            m_data = std::move(newData);
            m_head = 0;
            m_tail = m_count;
            m_capacity = newCapacity;
        }

        inline size_t CapacityLogic()
        {
            // 요소가 적을 때는 용량이 빠르게 증가
            if (m_capacity < 1024)
                return m_capacity * 2;
            else
                return m_capacity + m_capacity / 2;
        }

    private:
        size_t m_head;
        size_t m_tail;
        size_t m_count;
        size_t m_capacity;
        std::vector<T> m_data;
    };
}

 

Reserve가 가능한 큐

 

기존 큐와 벤치마크 결과

 

벤치마크 코드

void BenchmarkQueue()
{
    const int numOperations = 1000000;

    std::queue<int> stdQueue;
    auto start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < numOperations; ++i)
    {
        stdQueue.push(i);
    }
    for (int i = 0; i < numOperations; ++i)
    {
        stdQueue.pop();
    }
    auto end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> durationSTD = end - start;
    std::cout << "std::queue duration: " << durationSTD.count() << " seconds" << std::endl;

    MC::Queue<int> mcQueue;
    mcQueue.Reserve(numOperations);
    start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < numOperations; ++i)
    {
        mcQueue.Push(i);
    }
    for (int i = 0; i < numOperations; ++i)
    {
        mcQueue.Pop();
    }
    end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> durationMC = end - start;
    std::cout << "MC::Queue duration: " << durationMC.count() << " seconds" << std::endl;
}

int main()
{
    for(int i=0;i<10;i++)
    {
        BenchmarkQueue();
        std::cout << std::endl;
    }

    return 0;
}