要素のキューリーク？

Question

私はテンプレートとC++で簡単なキューを書いていますが、私のvalgrindのは私が漏れていますことを言い続け：

==5427== HEAP SUMMARY: 
==5427==  in use at exit: 72,704 bytes in 1 blocks 
==5427== total heap usage: 5 allocs, 4 frees, 72,768 bytes allocated 
==5427== 
==5427== 72,704 bytes in 1 blocks are still reachable in loss record 1 of 1 
==5427== at 0x4C29110: malloc (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so) 
==5427== by 0x50E366F: ??? (in /usr/lib64/libstdc++.so.6.0.21) 
==5427== by 0x400E8E9: call_init.part.0 (in /lib64/ld-2.19.so) 
==5427== by 0x400E9D2: _dl_init (in /lib64/ld-2.19.so) 
==5427== by 0x40011C9: ??? (in /lib64/ld-2.19.so) 
==5427== 
==5427== LEAK SUMMARY: 
==5427== definitely lost: 0 bytes in 0 blocks 
==5427== indirectly lost: 0 bytes in 0 blocks 

そして、ここでは私の実装です：

template <typename T> class Queue 
{ 

    struct node_t { 
     T data; 
     struct node_t* next; 
    }; 
    node_t* newNode(T data) 
    { 
     node_t* n = (node_t*)malloc(sizeof(node_t)); 
     if (n) { 
      n->data = data; 
      n->next = NULL; 
     } 
     return n; 
    } 

public: 

    Queue() : m_head(NULL), m_tail(NULL) {} 
    ~Queue(){} 

    void put(T data) 
    { 
     node_t* n = newNode(data); 

     if (m_tail != NULL) { 
      m_tail->next = n; 
     } 
     m_tail = n; 
     if (m_head == NULL) { 
      m_head = n; 
     } 
    } 

    T get() 
    { 
     node_t* it = m_head; 
     if (m_head != NULL) { 
      m_head = m_head->next; 
     } 

     T ret; 
     if (it != NULL) {    
      ret = it->data; 
      free(it); 
     } 
     return ret; 
    } 

    bool isEmpty() 
    { 
     return m_head == NULL; 
    } 

private: 
    node_t* m_head; 
    node_t* m_tail; 
}; 

また、私は戻っていますプライベートノードからのデータですが、get関数では、キューが空の場合には初期化されないコピー変数を常に返します。new（）を使用してヘッドノードがない場合はポインタまたはNULLを返すほうがよいでしょうプレゼント？

Answer 1

deleteのリリースでは、割り当てのためにmalloc()を混在しているようです。これは未定義の動作です。

空のキューのget()の結果に関しては、get()のキューが空でないことを前提としています。

Answer 2

私はR.Sadgewickの "Algorithms in C"で同じロジックを見てきましたが、キューを空にする際にテールデータも失われています。デキューのコードは、古典的なリンクリストの削除アルゴリズムを削除していますが、結局はテールノードが残っています。プログラムの最後にキューノードがヌルであることを確認するために、 。

template <typename T> class Queue 
{ 
    struct node_t { 
     T data; 
     struct node_t* next; 
    }; 

    node_t* new_node(T data, node_t* link) 
    { 
     node_t* n = (node_t*)malloc(sizeof(node_t)); 
     if (n) { 
      n->data = data; 
      n->next = link; 
     } 
    } 

public: 
    Queue() : m_head(NULL), m_tail(NULL) {} 
    ~Queue() 
    { 
     while (!isEmpty()) { 
      T* n = dequeue(); 
     } 
    } 

    void enqueue(T data) 
    { 
     if (m_head == NULL) { 
      m_tail = new_node(data, m_head); 
      m_head = m_tail; 
     } else { 
      m_tail->next = new_node(data, m_tail->next); 
      m_tail = m_tail->next; 

     } 
    } 

    T* dequeue() 
    { 
     if (m_head == NULL) { 
      return NULL; 
     } 

     T t = m_head->data; 
     node_t* n = m_head; 
     // Sadgewick: 
     // m_head = m_head->next; 
     // mine: 
     m_head = m_tail = m_head->next; 
     free(n); 
     return &t; 
    } 

    bool isEmpty() 
    { 
     return m_head == NULL; 
    } 

private: 
    node_t* m_head; 
    node_t* m_tail; 
};