新しいものは呼び出されていませんが、メモリが割り当てられました

Question

私は単純なTrieの実装を書いています。

は私の問題は、「ハロー」は既に二回挿入されているにもかかわらず、その挿入が試みられ、ひいては newされていることである

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

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

がある：ここでは

#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; 
} 

は私のテストプログラムである：ここでは、ソースコードがありますもはや呼び出されず、多くのメモリが割り当てられ、割り当てが解除されています。この量は、私が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を明らかにします。おそらくノードの割り当てだけでなく、std::mapが内部で行うものと、見落としたいくつかの他の場所（文字列やマップのコピーなど）

コンテナは要素を含んでいなくてもメモリを割り当てることができますが、それは別の方法で設計されていたはずですが、コンテナの主要な実装があれば驚くはずです。 （deque mayも例外ですが）

Answer 2

std::mapは、独自のメモリを動的に割り当て、get_child()に電話するたびに新しいメモリを作成します。私は言うことはできませんが、おそらく何かです。 newに電話していないからといって、あなたのクラスで作成された他のタイプはそうではありません。

また、std::mapは、挿入されたすべての要素に対して全く新しいヒープストアを割り当てません。それはひどく非効率的です。必要に応じてバッキングストアを拡張するための内部アルゴリズムがいくつかあり、新しい要素に合わせるために必要以上に割り当てることができます。