5
मैंने एक सरल Trie कार्यान्वयन लिखा है।नया नहीं कहा जाता है, फिर भी स्मृति आवंटित
#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 है:
#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;
}
यहाँ मेरी परीक्षण कार्यक्रम है: यहाँ स्रोत कोड है अब और नहीं कहा जाता है, बहुत सारी मेमोरी आवंटित की जा रही है और आवंटित की जा रही है। यह राशि बढ़ जाती है क्योंकि मैं अधिकतम i के मूल्य को बढ़ाता हूं।
==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
मैं पुष्टि की है कि के समय नोड() निर्माता संख्या कहा जाता है स्थिर है: उदाहरण के लिए, उपरोक्त मामले valgrind में यह उत्पादन देता है। फिर क्यों और कैसे सभी स्मृति आवंटित और आवंटित किया जा रहा है?
आप बहुत सारे मानचित्र बना रहे हैं। वे आंतरिक रूप से स्मृति आवंटित कर सकते हैं। –