nowe nie wywołane, ale przydzielona pamięć

Question

Napisałem prostą implementację Trie. Oto kod źródłowy:

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

Oto mój program testowy:

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

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

Moim problemem jest to, że nawet „cześć” jest już włożona po raz drugi jego wstawiania próby, a więc new jest nie jest już wywoływana, wiele pamięci jest przydzielane i rozdzielane. Ta kwota wzrasta, gdy zwiększam wartość maks. I. Na przykład, w powyższym przykładzie valgrind daje następujący wynik:

==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 

I potwierdziły, że wiele razy węzła() konstruktora jest nazywany jest stała. Więc dlaczego i jak cała pamięć jest przydzielana i zwalniana?

Answer 1

każdym razem wywołać insert, przekazać mu const char[6], ale oczekuje const std::string&, a więc każda iteracja tworzy tymczasowy std::string, który jest następnie przekazywany do funkcji, a następnie zniszczone przed następnej iteracji. To wyjaśnia 10000 alokacji i deallokacji, pozostawiając tylko 11, które przypuszczalnie są twoimi przydziałami węzła, a także to, co robisz wewnętrznie, oraz kilka innych miejsc, które przeoczyłem (takich jak kopie łańcuchów lub mapa)

Pojemnik mógł przydzielić pamięć, nawet jeśli nie zawierał żadnych elementów, ale twierdziłbym, że powinien on zostać zaprojektowany inaczej, i byłby zaskoczony, gdyby jakakolwiek poważna implementacja kontenera spowodowała taką rzecz. (Chociaż deque może być wyjątkiem:)

Answer 2

std::map będzie dynamicznie przypisywać swoją pamięć, a Ty tworzysz nową za każdym razem, gdy wywołasz get_child(). Ile pamięci jest przydzielana przy użyciu domyślnego konstruktora, którego nie mogę powiedzieć, ale prawdopodobnie jest to coś. To, że nie dzwonisz pod numer new, nie oznacza, że ​​inne typy stworzone przez twoją klasę nie.

Ponadto, std::map nie przydzieli całkowicie nowego magazynu sterty dla każdego wstawionego elementu. To byłoby strasznie nieefektywne. Posiada pewien wewnętrzny algorytm, aby w razie potrzeby rozbudować swój system kopii zapasowych i na pewno przydzieli więcej, niż potrzeba, aby zmieścić ten nowy element.