soraなりの日々 - fc2 -

こころにひっかかったもの

[c++,0x]コードの中心でiを理解する -第二回 0x会 my_list 最終系-

長崎にて、最終系のレビューをやりました、と。
前に書いた時、一個勘違いしててさ。
それはね。
単なる連結リストでなくて、循環連結リストやったんよね・・・orz

オレ、循環今回初めてしたや。

このエントリーをはてなブックマークに追加
て、ことで最終系。

[kwn_list.hpp]
/**
 *  @file kwn_list.hpp
 */

#ifndef _KWN_LIST_HPP
#define _KWN_LIST_HPP

#include <iostream>
#include <assert.h>

namespace kwn
{

  class list
  {
  public:
    /**
     *  @brief  constructor
     */
     list():mp_root(NULL),mp_last(NULL), m_size(0) {}
     list(int n):mp_root(NULL),mp_last(NULL), m_size(0) {
       add(n);
     }

    /**
     *  @brief  destructor
     */
    virtual ~list() { clear(); }

  private:
    /**
     *  @brief  クラス内の構造体
     */
    typedef struct M_LIST {
      int num;
      M_LIST* prev;
      M_LIST* next;

      void init() {
        num = 0;
        prev = NULL;
        next = NULL;
      }
    } M_LIST;

  public:
    /**
     *  @brief  追加
     *  @param  [in] n  リストに設定する数字
     */
    void add(int n) {
      M_LIST* p = new M_LIST;
      assert(p);
      if (!p) {
        std::cout << "allocate error!" << std::endl;
        return; /* error! */
      }

      p->init();
      p->num = n;
      if (!mp_root) {
        mp_root = p;
        mp_last = p;
      }
      mp_last->next = p;  // 最後のリストの次は最新を設定する
      p->prev = mp_last;  // 最新の一個前は最後を設定する
      p->next = mp_root;  // 最新の次は常にルートを設定
      mp_root->prev = p;  // ルートの戻りは常に最新を設定する

      mp_last = p;        // 現在の最終位置を設定する
      m_size++;           // カウントアップ
    }

    /**
     *  @brief  削除
       *  @param  [in] n  リスト内にある削除する値
       *  @param  [in] b  リスト内にある削除する値をすべて削除するか
     */
    void del(int n, bool b=false) {

      M_LIST* p = find(n);
      if (!p) { return; }

      // ポインタの繋直し
      M_LIST* prev = p->prev;
      prev->next = p->next;
      prev->next->prev =prev;
      if (p == mp_root) { mp_root = p->next; }
      if (p == mp_last) { mp_last = p->prev; }
      delete p;
      if (p == mp_root && p == mp_last) {
        mp_root->init();
        mp_root = NULL;
        mp_last->init();
        mp_last = NULL;
      }
      m_size--;           // カウントダウン
      if (!b) { return; }

      // 指定された値の重複全削除
      while (p = find(n)) {
        // ポインタの繋直し
        prev = p->prev;
        prev->next = p->next;
        prev->next->prev = prev;
        if (p == mp_root) { mp_root = p->next; }
        if (p == mp_last) { mp_last = p->prev; }
        delete p;
        if (p == mp_root && p == mp_last) {
          mp_root->init();
          mp_root = NULL;
          mp_last->init();
          mp_last = NULL;
        }
        m_size--;           // カウントダウン
        if (p == mp_last->next) { break; }
      }
    }

    /**
     *  @brief   リスト数
     *  @return  int  リスト数
     */
    unsigned int size() const { return m_size; }

    /**
     *  @brief   合計
     *  @return  int  合計値
     */
    int calc_all() const {
      int num = 0;
      M_LIST* p = mp_root;
      M_LIST* next = NULL;
      while (p) {
        num += p->num;
        next = p->next;
        p = next;
        if (p == mp_last->next) { break; }
      }
      return num;
    }

    /**
     *  @brief   全削除
     */
    void clear() {
      M_LIST* p = mp_root;
      M_LIST* next = NULL;
      while (p) {
        next = p->next;
        delete p;
        m_size--;  // カウントダウン
        p = next;
        if (p == mp_last->next) { break; }
      }
      mp_root = NULL;
      mp_last = NULL;
    }

    /** this is a test code... */
    void disp() {
      M_LIST* p = mp_root;
      M_LIST* next = NULL;
      while (p) {
        std::cout << p->num << std::endl;
        next = p->next;
        p = next;
        if (p == mp_last->next) { break; }
      }
    }

  private:
    /**
     *  @brief   リスト内の検索
     *  @param   [in] n  リスト内にある値
     *  @return  M_LIST* 見つかった値のポインタ
     */
    M_LIST* find(int n) const {
      M_LIST* p = mp_root;
      M_LIST* next = NULL;
      M_LIST* val = NULL;
      while (p) {
        if (n == p->num) {
           val = p;
           break;
        }
        next = p->next;
        p = next;
        if (p == mp_last->next) { break; }
      }
      return val;
    }

  private:
    /**
     *  @brief  class member
     */
     M_LIST* mp_root;  // ルート
     M_LIST* mp_last;  // 最終位置
     unsigned int m_size;
  };
} // namespace kwn

#endif /* _KWN_LIST_HPP */


[main.cpp]
#include <iostream>
#include <assert.h>

#include "kwn_list.hpp"

/**
 *  @brief  test function
 *
 *   command line : g++ main.cpp
 *                : ./a.out
 *        gcc ver : 4.0.1 (Apple Inc. build 5465)
 */
int main()
{
/*
  kwn::list list2 = 2;
  list2.del(2);

  list2.add(4);
  list2.del(4);
*/
  clock_t start, end;
  srand((unsigned)time(NULL));

  start = clock();

  kwn::list* list = new kwn::list;

  const unsigned int MAX = 1000;
  int n = 0;
  for (int iCnt=0; iCnt<MAX; iCnt++) {
//    n = rand();
//    list->add(n);
    list->add(iCnt);
    list->add(iCnt);
    list->add(iCnt);
  }

  list->del(3, true);
  list->disp();

  std::cout << "合計:" << list->calc_all() << std::endl;
  std::cout << "サイズ:" << list->size() << std::endl;

  list->clear();
  delete list;

  end = clock();

  std::cout << MAX << "回ループ速度:" << (double)(end - start) / CLOCKS_PER_SEC << std::endl;

  kwn::list list2 = 2;
  list2.disp();

  kwn::list list3;
  list3.del(3);

  return 0;
}


いやー、久方、今回ポインタではまったや。。。
やっぱ楽しいね(^^;


環境:PowerBook G4 1.25 GHz memory 1 GB
   :gcc version 4.0.1 (Apple Inc. build 5465)
このエントリーをはてなブックマークに追加

コメント

コメントの投稿


管理者にだけ表示を許可する

トラックバック

トラックバックURLはこちら
http://sora2hs.blog70.fc2.com/tb.php/432-d999bab0
この記事にトラックバックする(FC2ブログユーザー)