キュー改良

• キュー - sotarokのお勉強

Exceptionの練習としてデータ範囲のチェックと，空のキューも使えるようにした．前回のキューだと1個以上データがないと使えないとかあった．

一応，メモリリークしないことも確認した．valgrind使ってみた．

• http://kzk9.net/column/valgrind.html

// queue.cpp
#include <iostream>
#include <string>

class queue_exception
{
    public:
        const std::string message;
        queue_exception(const std::string &m) : message(m) {};
};

class queue_items
{
    public:
        const int data;
        queue_items *next_ptr;

        queue_items(const int &);
};

queue_items::queue_items(const int &i = 0) : data(i)
{
    next_ptr = NULL;
}

class queue
{
    public:
        queue_items *last_ptr;
        queue_items *first_ptr;

        queue();
        queue(queue_items *);
        static queue* initialize();
        static queue* initialize(int);
        ~queue();
        void enq(const int i);
        int deq();
        void print_all();
        bool is_empty();

    private:
};

queue::queue()
{
    first_ptr = NULL;
    last_ptr = NULL;
}

queue::queue(queue_items *i)
{
    first_ptr = i;
    last_ptr = first_ptr;
}

queue::~queue()
{
    // ちゃんと queue_items を全部 delete する
    queue_items *tmp;
    while(first_ptr != NULL) {
        tmp = first_ptr;
        first_ptr = first_ptr->next_ptr;
        delete tmp;
    }
}

queue* queue::initialize()
{
    return new queue();
}

queue* queue::initialize(const int i)
{
    return new queue(new queue_items(i));
}

void queue::enq(const int i)
{
    queue_items *new_ptr;

    new_ptr = new queue_items(i);

    if (last_ptr == NULL) {
        last_ptr = new_ptr;
        first_ptr = last_ptr;
    }
    else {
        last_ptr->next_ptr = new_ptr;
        last_ptr = last_ptr->next_ptr;
    }
}

bool queue::is_empty()
{
    if (first_ptr == NULL) {
        return true;
    }
    return false;
}

int queue::deq()
{
    // 範囲内チェック
    if (first_ptr == NULL) {
        throw queue_exception("queue is out of data.");
    }

    int tmp = first_ptr->data;
    queue_items *tmp_ptr = first_ptr;

    first_ptr = first_ptr->next_ptr;

    delete tmp_ptr;
    tmp_ptr = NULL;

    return tmp;
}

void queue::print_all()
{
    queue_items *current_ptr = first_ptr;

    std::cout << "queue data : ";
    while (current_ptr != NULL) {
        std::cout << current_ptr->data << " -> ";
        current_ptr = current_ptr->next_ptr;
    }

    std::cout << "end." << std::endl;
}

int main()
{
    int i = 0, test_max = 10, intervals = 2;
    queue *q, *q2;

    try {
        q = queue::initialize(i);
        q2 = queue::initialize(i + 1);

        std::cout << "after initialize: " << std::endl;
        q->print_all();
        q2->print_all();

        std::cout << "\nstart test: " << std::endl;
        for(++i ;i < test_max; ++i) {
            q->enq(i);
            q2->enq(i * 2);
            if (i%intervals == 0) {
                std::cout << i << " => " << std::flush;
                q->print_all();
                std::cout << i << " => " << std::flush;
                q2->print_all();
            }
        }

        for(;i - 1 > 0; --i) {
            if (i%intervals == 0) {
                std::cout << i << " => ";
                q->print_all();
                std::cout << i << " => ";
                q2->print_all();
            }
            if (!q->is_empty()) {
                q->deq();
            }
            if (!q2->is_empty()) {
                q2->deq();
            }
        }

        std::cout << "end of test.\n" << std::endl;
        q->print_all();
        q2->print_all();

        delete q;
        delete q2;
    }
    catch (queue_exception& e) {
        std::cerr << "Exception: " <<  std::endl;
        std::cerr << "  -- " << e.message << std::endl;
        exit(8);
    }
    catch (...) {
        std::cerr << "Error: Unexpected exception occurred." << std::endl;
        exit(8);
    }

    return 0;
}

after initialize:
queue data : 0 -> end.
queue data : 1 -> end.

start test:
2 => queue data : 0 -> 1 -> 2 -> end.
2 => queue data : 1 -> 2 -> 4 -> end.
4 => queue data : 0 -> 1 -> 2 -> 3 -> 4 -> end.
4 => queue data : 1 -> 2 -> 4 -> 6 -> 8 -> end.
6 => queue data : 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> end.
6 => queue data : 1 -> 2 -> 4 -> 6 -> 8 -> 10 -> 12 -> end.
8 => queue data : 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> end.
8 => queue data : 1 -> 2 -> 4 -> 6 -> 8 -> 10 -> 12 -> 14 -> 16 -> end.
10 => queue data : 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> end.
10 => queue data : 1 -> 2 -> 4 -> 6 -> 8 -> 10 -> 12 -> 14 -> 16 -> 18 -> end.
8 => queue data : 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> end.
8 => queue data : 4 -> 6 -> 8 -> 10 -> 12 -> 14 -> 16 -> 18 -> end.
6 => queue data : 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> end.
6 => queue data : 8 -> 10 -> 12 -> 14 -> 16 -> 18 -> end.
4 => queue data : 6 -> 7 -> 8 -> 9 -> end.
4 => queue data : 12 -> 14 -> 16 -> 18 -> end.
2 => queue data : 8 -> 9 -> end.
2 => queue data : 16 -> 18 -> end.
end of test.

queue data : 9 -> end.
queue data : 18 -> end.

valgrind的にも．

% valgrind --leak-check=full ./a.out
==21772== Memcheck, a memory error detector.
==21772== Copyright (C) 2002-2006, and GNU GPL'd, by Julian Seward et al.
==21772== Using LibVEX rev 1658, a library for dynamic binary translation.
==21772== Copyright (C) 2004-2006, and GNU GPL'd, by OpenWorks LLP.
==21772== Using valgrind-3.2.1, a dynamic binary instrumentation framework.
==21772== Copyright (C) 2000-2006, and GNU GPL'd, by Julian Seward et al.
==21772== For more details, rerun with: -v
==21772==
after initialize:
queue data : 0 -> end.
queue data : 1 -> end.

start test:
2 => queue data : 0 -> 1 -> 2 -> end.
2 => queue data : 1 -> 2 -> 4 -> end.
4 => queue data : 0 -> 1 -> 2 -> 3 -> 4 -> end.
4 => queue data : 1 -> 2 -> 4 -> 6 -> 8 -> end.
6 => queue data : 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> end.
6 => queue data : 1 -> 2 -> 4 -> 6 -> 8 -> 10 -> 12 -> end.
8 => queue data : 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> end.
8 => queue data : 1 -> 2 -> 4 -> 6 -> 8 -> 10 -> 12 -> 14 -> 16 -> end.
10 => queue data : 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> end.
10 => queue data : 1 -> 2 -> 4 -> 6 -> 8 -> 10 -> 12 -> 14 -> 16 -> 18 -> end.
8 => queue data : 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> end.
8 => queue data : 4 -> 6 -> 8 -> 10 -> 12 -> 14 -> 16 -> 18 -> end.
6 => queue data : 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> end.
6 => queue data : 8 -> 10 -> 12 -> 14 -> 16 -> 18 -> end.
4 => queue data : 6 -> 7 -> 8 -> 9 -> end.
4 => queue data : 12 -> 14 -> 16 -> 18 -> end.
2 => queue data : 8 -> 9 -> end.
2 => queue data : 16 -> 18 -> end.
end of test.

queue data : 9 -> end.
queue data : 18 -> end.
==21772==
==21772== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 15 from 1)
==21772== malloc/free: in use at exit: 0 bytes in 0 blocks.
==21772== malloc/free: 22 allocs, 22 frees, 176 bytes allocated.
==21772== For counts of detected errors, rerun with: -v
==21772== All heap blocks were freed -- no leaks are possible.

queueのデストラクタでqueue_itemsを消してやらないとメモリリークする．でも，デストラクタにちゃんとdeleteするコード書けば，mainをたとえば以下のようにしても，

int main()
{
    int i = 0, test_max = 10, intervals = 2;
    queue *q, *q2;

    try {
        q = queue::initialize(i);
        q2 = queue::initialize(i + 1);

        std::cout << "after initialize: " << std::endl;
        q->print_all();
        q2->print_all();

        std::cout << "\nstart test: " << std::endl;
        for(++i ;i < test_max; ++i) {
            q->enq(i);
            q2->enq(i * 2);
            if (i%intervals == 0) {
                std::cout << i << " => " << std::flush;
                //q->print_all(); // プリントは省略
                std::cout << i << " => " << std::flush;
                //q2->print_all();
            }
        }

        /* deq しない
        for(;i - 1 > 0; --i) {
            if (i%intervals == 0) {
                std::cout << i << " => ";
                q->print_all();
                std::cout << i << " => ";
                q2->print_all();
            }
            if (!q->is_empty()) {
                q->deq();
            }
            if (!q2->is_empty()) {
                q2->deq();
            }
        }
        */

        std::cout << "end of test.\n" << std::endl;
        q->print_all();
        q2->print_all();

        delete q;
        delete q2;
    }
    catch (queue_exception& e) {
        std::cerr << "Exception: " <<  std::endl;
        std::cerr << "  -- " << e.message << std::endl;
        exit(8);
    }
    catch (...) {
        std::cerr << "Error: Unexpected exception occurred." << std::endl;
        exit(8);
    }

    return 0;
}

% valgrind --leak-check=full ./a.out
==21861== Memcheck, a memory error detector.
==21861== Copyright (C) 2002-2006, and GNU GPL'd, by Julian Seward et al.
==21861== Using LibVEX rev 1658, a library for dynamic binary translation.
==21861== Copyright (C) 2004-2006, and GNU GPL'd, by OpenWorks LLP.
==21861== Using valgrind-3.2.1, a dynamic binary instrumentation framework.
==21861== Copyright (C) 2000-2006, and GNU GPL'd, by Julian Seward et al.
==21861== For more details, rerun with: -v
==21861==
after initialize:
queue data : 0 -> end.
queue data : 1 -> end.

start test:
2 => 2 => 4 => 4 => 6 => 6 => 8 => 8 => end of test.

queue data : 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> end.
queue data : 1 -> 2 -> 4 -> 6 -> 8 -> 10 -> 12 -> 14 -> 16 -> 18 -> end.
==21861==
==21861== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 15 from 1)
==21861== malloc/free: in use at exit: 0 bytes in 0 blocks.
==21861== malloc/free: 22 allocs, 22 frees, 176 bytes allocated.
==21861== For counts of detected errors, rerun with: -v
==21861== All heap blocks were freed -- no leaks are possible.

ちゃんと開放される．
インスタンスのメンバのメモリ管理も自分の仕事．