c++ - 链表快速分配和缓慢释放

Question

我是 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 秒。我做错了什么吗？

Answer 1

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