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 секунд. Я делаю что-то явно неправильно?
ли вы компилируете с оптимизацией? –
Как вы это определяете? –
Вы можете обнаружить, что это полезно для распределителя пулов, поскольку каждый узел имеет одинаковый размер, а когда список удален, вы можете сказать, что распределитель удаляет весь фрагмент памяти сразу (без необходимости цикла). –