时间戳

首页 > 解决方案 > 我可以逐个元素删除数组元素吗？

c++ - 我可以逐个元素删除数组元素吗？

问题描述

我正在尝试创建自定义列表。这是节点结构：

struct Node {
    ListNode* prev;
    ListNode* next;
    void* data;
};

构造函数之一从数组创建列表。所以我决定在内存的连续部分分配节点，以使算法更快一点。

auto elements = new Node[size];
elements[0] = ...
elements[size - 1] = ...
for (int i = 1; i + 1 < size; i++) {
    elements[i].data = array[i];
    elements[i].prev = &elements[i - 1];
    elements[i].next = &elements[i + 1];
}
head = &elements[0];
tail = &elements[size - 1];

之后我可以添加新元素：

Node* tmp = new Node;
tmp->prev = tail;
tmp->data = data;
tail = tmp;

我也可以改变next和prev。

所以我无法区分元素（这个元素是数组的一部分还是稍后使用 分配new）并且在析构函数中我必须使用delete而不是删除元素delete[]。

Node* curNode = head;
for (int i = 0; i < size; i++) {
    Node* tmp = curNode.next;
    delete curNode;
    curNode = tmp;
}

此代码不会删除已在数组中分配的元素（根据 Valgrind）。如何在一个数组中分配节点（以减少缓存未命中的数量），然后逐个元素成功地删除它们？

标签： c++

解决方案

您正在尝试做的是您可能想到的最 hacky 的链表实现。出于所有现实生活的目的，您应该坚持下去，STL它看起来就像std::vector您想要的那样。话虽如此，如果您尝试实现自己的链表来了解它是如何工作的，让我首先说您已经做错了。

根据定义，链表由Nodes每个Node指向的位置组成next，也可以指向previous。内存中各个节点的物理顺序无关紧要，从功能的角度来看也无关紧要。cache hits如果您在同一页面中有一堆连续的，则可能会获得相关的性能提升Nodes，但这不是您在实现链表时应该瞄准的目标。如果您的目标是获得顶级性能，那么 purearray list将永远击败linked list您能想到的任何实现。并且std::vector已经是你应该在 99% 的时间内使用的东西。

If you already implement a function that takes collection of elements and build Nodes out of them, you somewhat enforce OS to gets you chunks of memory for Nodes in kind of contiguous fashion. It's not a strong guarantee, but I would consider it good enough.

You can't release individual elements that belongs to a chunk of memory created with new[]. If you want to stick to array as your underlying storage for Nodes you have two options, as already mentioned in comments.

Option 1) Allocate single array for whole list and use indexes as your next and previous pointers in nodes. Note that it would require you to somehow handle situation when your list will be asked to hold more elements than your array can handle. Most likely allocating more arrays or allocating bigger one and copying everything which will bring you to array list with fancy ordering.

Option 2) Add dedicated memory manager that will be allocating chunks of memory in form of arrays and will handle individual entries, which is basically implementing your own memory allocator.

推荐阅读