1

我是 C++ 新手，遇到了一个令人沮丧的问题 -

我有这个模板化的 LinkedList 实现：

template <typename U>
class LinkedList : std::iterator<std::input_iterator_tag, U> {
public:
    struct Node {
    friend LinkedList;
        U content;
        Node* getNext() { return next; };
    private:
        Node* next;
        Node* prev;
    };

    LinkedList() : head(NULL), tail(NULL) { };
    ~LinkedList() {
        Node * current = tail;
        while(current != NULL) {
            Node* temp = current;
            current = current->prev;
            delete temp;
        }
    };
    Node* getHead() { return head; }
    Node* getTail() { return tail; }
    bool append(U content) {
        Node* node = new Node();
        if(node == NULL) return false;

        node->content = content;
        if(tail == NULL) {
            tail = head = node;
        } else {
            tail->next = node;
            node->prev = tail;
            tail = node;
        }

        return true;
    };

bool remove(U* cont) {
    if(tail == NULL) return false;

    if(cont != NULL) *cont = tail->content;

    Node *temp = tail;
    if(tail == head) {
        tail = NULL;
        head = NULL;
    } else tail = temp->prev;
    delete temp;
    return true;
};
private:
    Node *head, *tail;
};

我针对它运行以下代码：

char c1, c2;
cout << "start allocation" << endl;

LinkedList<int>* list = new LinkedList<int>();

for(ULONGLONG i = 0; i < 1e5; i++) {
    list->append(0);
}

cout << "allocation complete" << endl;

cin >> c1;

cout << "start deleting" << endl;

delete list;

cout << "done deleting" << endl;

cin >> c2;

cout << c2 << endl; // don't optimize read key away

因此它分配了 100,000 个 int 节点，然后将它们全部删除。为所有节点分配空间几乎是瞬时的，而删除它们大约需要 10 秒。我在做一些明显错误的事情吗？

4

2 回答 2

3

这可能是运行时库如何释放内存的产物。在分配过程中，为每个节点项找到一个块可能只是获取主池的几个操作，并将其分成两部分并将较小的部分返回给您的程序使用。释放该块可能包括遍历一个空闲列表以查看这些小分配是否可以组合成更大的空闲块。

于 2013-06-12T21:03:17.847 回答
0

尝试在发布模式而不是调试模式下运行。

在调试模式下，当释放一个块时，运行时会进行大量的完整性检查，以确保你没有覆盖你不拥有的内存，它还会清理释放的内存内容。在 Release 中，所有这些开销都消失了。

（请注意，我在这里假设您使用的是 Dev Studio。其他平台有不同的启用内存检查的规则，但您的问题听起来与我在调试模式下使用 Dev Studio 的经历非常相似。）

于 2013-06-12T21:46:35.217 回答