Static Queue 테스트

앞서 만든 static queue가 잘 동작하는지 몇 가지 테스트를 해 보았다. 먼저, 아래와 같이 queue에 저장할 간단한 데이터 구조를 만들었다.

struct DataItem
{
    DataItem(int key = 0, double value = 0) : m_key(key), m_value(value) {};
    void print() const
    {
        std::cout << "key=" << m_key << ", value=" << m_value << std::endl;
    }
private:
    int m_key;
    double m_value;
};

typedef StaticQueue<DataItem> StaticDataQueue;

그리고, 최대 용량 10개 짜리 dataQue를 만들어서 enqueue와 dequeue 테스트...

//
    StaticDataQueue dataQue(10);
    for(size_t i = 0; i < 100; ++i) {
#if __cplusplus >= 201103L
        dataQue.enqueue(DataItem(i, 0.1 * i)); // call move semantics(-std=c++11)
#else
        dataQue.enqueue(DataItem(i, 10 * i)); // call copy semantics
        //dataQue.enqueue(new DataItem(i, 10 * i)); // OK~!
#endif
        if(i >= dataQue.capacity() - 1 && !dataQue.isEmpty()) {
            DataItem dq_item = dataQue.dequeue();
            std::cout << "Dequeue: ";
            dq_item.print();
        }
    }
    dataQue.print();

Constructor와 Operator 테스트...

//
    dataQue[3] = DataItem(3, 333);

    StaticDataQueue qtmp1(dataQue), qtmp2(100);
    std::cout << "\n<< qtmp1 >>\n";
    qtmp1.print();
    std::cout << "\n<< qtmp2 >>\n";
    qtmp2.print();
 
    qtmp2 = qtmp1;
    std::cout << "\n<< qtmp2 >>\n";
    qtmp2.print();

#if __cplusplus >= 201103L
    StaticDataQueue qtmp3(std::move(qtmp2));
    std::cout << "\n<< qtmp2 >>\n";
    qtmp2.print();
    std::cout << "\n<< qtmp3 >>\n";
    qtmp3.print();
#endif

그럭저럭 잘 동작한다. 위에서 dataQue[3]와 같이 컨테이너의 데이터를 수정하는 것도 바람직하지는 않지만 가능하다. 여기선 단지 index operator를 테스트한 것이다. 메모리 누수도 없고~!

Static Queue

늙어도 심심삼아 코딩 할 수 있도록 소시적 배운 C++의 기억을 회복할 겸  C++ STL deque을 써서 static queue를 만들어 보았다. 임의의 data structure에 대한 pointer 들을 저장하되 정해진 용량까지만 저장한다. Queue size는 가변적이다. enqueue를 시작하면 정해진 용량까지만 채워지고 그 용량을 넘어서면 과거 데이터부터 자동 삭제된다. 또, dequeue할 때마다 size는 하나씩 감소한다. 즉, size는 0 ~ capacity 내에서 유동적이다.

실제 이 static queue를 써먹을 것인지는 중요하지 않다. 여기서는 C++ Class Constructor 기본 개념과 pointer에 대해 빨리 적응하고, 덤으로 C++11에 추가된 move constructor 등에 대해서도 알아 보는데 의의가 있다.

#include <iostream>
#include <deque>

template<typename _Tp>
class StaticQueue
{
public:
    typedef typename std::deque<_Tp*> _Tp_Data;
    typedef typename _Tp_Data::iterator iterator;
    typedef typename _Tp_Data::const_iterator const_iterator;

    // default constructor
    explicit StaticQueue(size_t capa=100) :
        m_size(0), m_capacity(capa)
    {
        m_dequeue_item = new _Tp;
        m_data = new _Tp_Data;
    }

    // destructor
    ~StaticQueue() { destroy(); }

    // copy constructor
    StaticQueue(const StaticQueue& rhs) { copyFrom(rhs); }

    // copy assignment operator
    StaticQueue& operator=(const StaticQueue& rhs)
    {
        if(this!=&rhs) {
            destroy();
            copyFrom(rhs);
        }
        return *this;
    }

#if __cplusplus >= 201103L
    // move constructor: -std=c++11
    StaticQueue(StaticQueue&& rhs) { moveFrom(rhs); }

    // move assignment operator: -std=c++11
    StaticQueue& operator=(StaticQueue&& rhs)
    {
        if(this!=&rhs) {
            destroy();
            moveFrom(rhs);
        }
        return *this;
    }
#endif
   
    // index operator
    const _Tp& operator[](size_t index) const { return *m_data->at(index); }
    _Tp& operator[](size_t index) { return *m_data->at(index); }

    // getters
    size_t size() const { return m_size; }
    size_t capacity() const { return m_capacity; }
    _Tp_Data* data() const { return m_data; }

    // setters
    void setCapacity(size_t size) { m_capacity = size; }

    void enqueue(const _Tp& item);
    void enqueue(_Tp* item);
#if __cplusplus >= 201103L
    // rvalue reference parameter: -std=c++11
    void enqueue(_Tp&& item);
#endif
    const _Tp& dequeue();
    bool isEmpty() const { return !m_size; }

    void print() const;

private:
    void popFront();
    void copyFrom(const StaticQueue& rhs);
    void moveFrom(StaticQueue& rhs);
    void destroy();

    size_t m_size;       // Current queue size
    size_t m_capacity;   // Maximum queue size
    _Tp* m_dequeue_item; // Storage for a dequeued item
    _Tp_Data* m_data;    // Queue container for storing FIFO data
};


template<typename _Tp>
inline void StaticQueue<_Tp>::enqueue(const _Tp& item)
{
    m_data->push_back(new _Tp(item));

    if(++m_size > m_capacity) {
        popFront();
        m_size = m_capacity;
    }
}

template<typename _Tp>
inline void StaticQueue<_Tp>::enqueue(_Tp* item)
{
    m_data->push_back(item);

    if(++m_size > m_capacity) {
        popFront();
        m_size = m_capacity;
    }
}

#if __cplusplus >= 201103L
template<typename _Tp>
inline void StaticQueue<_Tp>::enqueue(_Tp&& item)
{
    m_data->push_back(new _Tp(item));

    if(++m_size > m_capacity) {
        popFront();
        m_size = m_capacity;
    }
}
#endif

template<typename _Tp>
inline const _Tp& StaticQueue<_Tp>::dequeue()
{
    // What if undeflow condition(m_size==0)?
    if(m_size) {
        *m_dequeue_item = *m_data->front();
        popFront();
        --m_size;
    }

    return *m_dequeue_item;
}

template<typename _Tp>
inline void StaticQueue<_Tp>::print() const
{
    std::cout << "\nQueue size/capacity: " << size() << "/" << capacity() << std::endl;

    if(!isEmpty()) {
        int c = 0;
        for(const_iterator i=m_data->begin(); i != m_data->end(); ++i) {
            std::cout << c++ << ": ";
            (*i)->print();
        }
    }
}

template<typename _Tp>
inline void StaticQueue<_Tp>::popFront()
{
    delete m_data->front();
    m_data->pop_front();
}

template<typename _Tp>
inline void StaticQueue<_Tp>::copyFrom(const StaticQueue<_Tp>& rhs)
{
    m_size = rhs.m_size;
    m_capacity = rhs.m_capacity;

    m_dequeue_item = new _Tp(*rhs.m_dequeue_item);

    m_data = new _Tp_Data;
    for(size_t i=0; i < rhs.m_size; ++i) {
        _Tp* item = new _Tp(rhs[i]);
        m_data->push_back(item);
    }
}

template<typename _Tp>
inline void StaticQueue<_Tp>::moveFrom(StaticQueue<_Tp>& rhs)
{
    m_size = rhs.m_size;
    m_capacity = rhs.m_capacity;
    m_dequeue_item = rhs.m_dequeue_item;
    m_data = rhs.m_data;

    rhs.m_size = 0;
    rhs.m_capacity = 0;
    rhs.m_dequeue_item = 0;
    rhs.m_data = 0;        
}

template<typename _Tp>
inline void StaticQueue<_Tp>::destroy()
{
    if(m_dequeue_item) delete m_dequeue_item;
    m_dequeue_item = 0;

    if(!isEmpty()) {
        for(iterator i=m_data->begin(); i != m_data->end();) {
            delete *i;
            i = m_data->erase(i);
        }
    }

    if(m_data) delete m_data;
    m_data = 0;
}

참고 사항

구글 blogger에 소스 코드 삽입시 Syntax Highlighter를 사용하는 방법은 아래의 사이트 참조.
http://oneqonea.blogspot.kr/2012/04/how-do-i-add-syntax-highlighting-to-my.html