5

我写了一个简单的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;
}

我的问题是，即使在第二次尝试插入时已经插入了“hello”，因此new不再调用，但仍有大量内存被分配和取消分配。这个数量随着 I 增加 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

我已经确认调用 Node() 构造函数的次数是恒定的。那么为什么以及如何分配和释放所有内存呢？

4

2 回答 2

13

每次调用 时insert，都会传递 a const char[6]，但它需要 a const std::string&，因此每次迭代都会创建一个临时std::string，然后将其传递给函数，然后在下一次迭代之前销毁。这澄清了 10000 个分配和释放，只剩下 11 个，这大概是您对节点的分配，以及std::map内部所做的任何事情，以及我忽略的其他一些地方（例如字符串的副本或映射）

即使容器不包含任何元素，它也可以分配内存，但我认为它应该以其他方式设计，如果容器的任何主要实现做了这样的事情，我会感到惊讶。（虽然双端队列可能是个例外）

于 2013-01-08T19:44:15.737 回答
5

std::map将动态分配自己的内存，每次调用时都会创建一个新内存get_child()。使用默认构造函数时它分配了多少内存我不能说，但它可能是. 仅仅因为您不调用new并不意味着您的类创建的其他类型不调用。

此外，std::map不会为插入的每个元素分配一个全新的堆存储。那将是非常低效的。它有一些内部算法来在需要时增加其后备存储，并且它肯定会分配比适合该新元素所需的更多。

于 2013-01-08T19:24:35.590 回答