新的不叫，但內存分配

Question

我寫了一個簡單的Trie實現。這裏是源代碼：

#include <string> 
#include <map> 

typedef unsigned int uint; 

class Trie { 
public: 
    class Node { 
    public: 
      Node(const char & _value); 
      ~Node(); 
      char get_value() const; 
      void set_marker(const uint & _marker); 
      uint get_marker() const; 
      bool add_child(Node * _child); 
      Node * get_child(const char & _value) const; 
      void clear(); 
    private: 
      char m_value; 
      uint m_marker; 
      std::map<char, Node *> m_children; 
    }; 

    Trie(); 
    ~Trie(); 
    bool insert(const std::string & _str); 
    bool find(const std::string & _str) const; 
private: 
    Node * m_root; 
}; 
// - implementation (in a different file) 
using namespace std; 

Trie::Node::Node(const char & _value) : 
      m_value(_value), m_marker(0), m_children() { 
} 

Trie::Node::~Node() { 
    clear(); 
} 

void Trie::Node::clear() { 
    map<char, Node*>::const_iterator it; 
    for (it = m_children.begin(); it != m_children.end(); ++it) { 
      delete it->second; 
    } 
} 

void Trie::Node::set_marker(const uint & _marker) { 
    m_marker = _marker; 
} 

uint Trie::Node::get_marker() const { 
    return m_marker; 
} 

char Trie::Node::get_value() const { 
    return m_value; 
} 

Trie::Node * Trie::Node::get_child(const char & _value) const { 
    map<char, Node*>::const_iterator it; 
    bool found = false; 
    for (it = m_children.begin(); it != m_children.end(); ++it) { 
      if (it->first == _value) { 
        found = true; 
        break; 
      } 
    } 
    if (found) { 
      return it->second; 
    } 
    return NULL; 
} 

bool Trie::Node::add_child(Node * _child) { 
    if (_child == NULL) { 
      return false; 
    } 
    if (get_child(_child->get_value()) != NULL) { 
      return false; 
    } 
    m_children.insert(pair<char, Node *>(_child->get_value(), _child)); 
    return true; 
} 

Trie::Trie() : 
      m_root(new Node('\0')) { 
} 

Trie::~Trie() { 
    delete m_root; 
} 

bool Trie::insert(const string & _str) { 
    Node * current = m_root; 
    bool inserted = false; 
    for (uint i = 0; i < _str.size(); ++i) { 
      Node * child = current->get_child(_str[i]); 
      if (child == NULL) { 
        child = new Node(_str[i]); 
        current->add_child(child); 
        inserted = true; 
      } 
      current = child; 
    } 
    if (current->get_marker() != _str.size()) { 
      current->set_marker(_str.size()); 
      inserted = true; 
    } 
    return inserted; 
} 

bool Trie::find(const std::string & _str) const { 
    Node * current = m_root; 
    bool found = false; 
    for (uint i = 0; i < _str.size(); ++i) { 
      Node * child = current->get_child(_str[i]); 
      if (child == NULL) { 
        break; 
      } else { 
        current = child; 
      } 
    } 
    if (current->get_marker() == _str.size()) { 
      found = true; 
    } 
    return found; 
} 

這裏是我的測試程序：

#include <iostream> 
#include <sstream> 
#include "Trie.h" 

int main() { 
    Trie t; 
    for (unsigned int i = 0; i < 10000; ++i) { 
      t.insert("hello"); 
    } 
    return 0; 
} 

我的問題是，即使「你好」已經插入第二次的插入嘗試，從而new是不再被調用，大量的內存正在分配和解除分配。這個數額隨着我增加max i的值而增加。例如，在上述情況下的valgrind給出了這樣的輸出：

==10322== HEAP SUMMARY: 
==10322==  in use at exit: 0 bytes in 0 blocks 
==10322== total heap usage: 10,011 allocs, 10,011 frees, 300,576 bytes allocated 

我已經證實，被稱爲次節點（）構造的數量是恆定的。那麼爲什麼以及如何分配和釋放所有的內存？

Answer 1

你叫insert每一個時間，你傳遞一個const char[6]，但它需要一個const std::string&，所以每一次迭代創建一個臨時std::string，然後將其傳遞給函數，然後銷燬的下一個迭代之前。這澄清了10000的分配和釋放，只剩下11個，這大概是你的節點分配，以及任何std::map在內部做的，以及我忽略的一些其他地方（如字符串或地圖的副本）

一個容器可以分配內存，即使它不包含任何元素，但我認爲它應該被設計爲其他方式，並且如果容器的任何主要實現都做了這樣的事情，將會感到驚訝。 （雖然deque 可能是例外）

Answer 2

std::map將動態分配自己的內存，並且每次調用get_child()時都會創建一個新內存。使用默認構造函數時分配多少內存我不能說，但它可能是某些東西。僅僅因爲你不打電話new並不意味着你的班級創建的其他類型不會。

此外，std::map不會爲插入的每個元素分配一個全新的堆存儲。這將是非常低效的。它有一些內部算法，可以在需要時增加其後備存儲，並且它肯定會分配比需要更多的東西來適應這個新元素。