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

これはおそらく、ランタイム ライブラリがメモリの割り当てを解除する方法のアーティファクトです。割り当て中に、各ノード項目のブロックを見つけることは、メイン プールを取得し、それを 2 つの部分に分割し、小さい方の部分をプログラムで使用するために返すためのおそらくほんの数回の操作です。そのブロックを解放するには、空きリストを調べて、これらの小さな割り当てを組み合わせてより大きな空きブロックにできるかどうかを確認することが含まれる場合があります。

于 2013-06-12T21:03:17.847 に答える