预分配数组列表
4.67/5 (6投票s)
结合了数组和链表优点的列表，性能更佳。
引言
用于存储元素的两种不同数据结构是数组和链表。数组在使用前需要预先分配，并且受限于其存储容量。链表在运行时创建并为其节点分配内存。链表的优点在于内存利用率高，因为构成列表的节点是动态分配的。然而，在进行大量分配和释放操作后，长期使用会导致内存碎片。与链表相比，数组的一个优点是易于使用、维护，并且检索特定位置的元素简单快捷。
当然也有一些缺点。在数组中进行添加操作时，插入新元素位置之后的所有元素都需要向前移动一个位置。对于删除元素，删除元素之后的所有元素都需要向后移动一个位置。
在链表中向特定位置添加和删除元素包含两个操作：
- 如果位置大于 0（即不是列表中的第一个元素），则找到添加到/删除点之前的元素。
- 更新（列表中要操作的元素之前的）元素的链接，使其指向下一个元素的下一个元素（如果是删除操作），或指向新元素（如果是添加操作）。在后一种情况下，新节点的下一个节点也需要更新，以指向（列表中要操作的元素之前的）原始元素的下一个节点。在删除的情况下，为被删除元素分配的内存将被释放。
因此，链表的删除和添加操作比数组更高效。链表的一个缺点是，为了检索一个元素，我们需要遍历列表中位于该元素之前的所有元素。预分配的数组列表试图结合数组和链表的优点，同时消除它们的大部分缺点。预分配的链表列表试图消除链表的主要缺点，即大量节点删除和添加后发生的内存碎片。它还试图在随机插入/删除操作（我们稍后会看到）以及访问元素方面比链表更有效。
动机
链表的使用会导致大量添加和删除操作后产生内存碎片。数组在删除和添加操作时效率低下，因为整个元素都需要被复制。预分配的数组列表试图消除这两种缺点，同时保留数组和链表的大部分优点。如果需要存储固定数量的元素，并且对该存储上的加、删、排序等操作频繁，那么预分配的数组列表是理想的选择。在这种情况下，内存的预分配将被列表上操作的效率所抵消，正如我们稍后在 PAL、Vector 和 List 的性能比较中所看到的。
使用的数据结构
顾名思义，预分配列表是事先分配内存（如数组），因此允许的元素数量是有限的。与链表一样，每个元素都存储在一个节点中，该节点除了包含元素空间外，还包含一个节点指针空间。该指针指向持有该位置元素的同一节点或不同节点。因此，与链表唯一的区别是，链接指向的不是紧邻的下一个节点，而是（即，预分配列表节点中的指针）指向包含当前位置元素的节点。与数组一样，我们可以通过位置索引访问存储中的任意位置的元素。这意味着检索一个位置的元素是先在该存储中的特定位置检索节点，然后检索该节点的节点指针所指向的元素。
template <class T>
struct node{
T val;
struct node *posptr;
};
template <class T=int, int N=100>
class CPArrayList{
private:
// The Buffer or store
char BUFFER[N];
// The size of each node
int m_nodesize;
// The maximum no of nodes that can be stored in the store
int m_capacity;
// No of elems currently in use
int m_filledelems;
// No of elems allocated from the list
int m_allocelems;
// Method that returns a free node(a new region from buffer or a free region
// (that was deleted))
node<T> *getfreenode(void);
// Method that returns the node at a particular position
node<T> *getNodeAtPos(int);
public:
CPArrayList();
int nodesize(void) { return m_nodesize; }
int capacity(void) { return m_capacity; }
bool insert(T info, int pos=0);
bool set(T info, int pos);
T get(int pos);
void remove(int pos);
void printlist(void);
};
BUFFER：一个持有列表内存的数组或缓冲区。m_capacity：一个保存存储限制的变量。m_filledelems：在某个时间点插入/相关的列表元素数量。(m_filledelems-1)值索引到具有指向当前列表最后一个节点的指针的节点。m_allocelems：从存储中使用的节点总数，无论它当前是否在使用。如果一个节点被删除，则称该节点未使用。删除是一种特殊情况，节点实际上并没有真正返回到存储中，而是被添加到空闲列表中。空闲列表实际上是主存储本身的一个子集存储的名称，它是一个节点列表，每个节点都指向一个已删除的元素节点，但它本身可能未被删除（稍后将解释），并且包含一个列表元素。空闲元素的数量可以计算为m_allocelems – m_filledelems。
列表上的操作
元素添加
添加元素到列表时，首先找到一个空闲节点。这是通过首先在空闲节点列表中搜索它来实现的（Alloc_elems > Filled_elems 表示列表中有空闲元素）。如果空闲列表中没有元素且 Alloc_elems < Max_elems，则从数组列表中获取一个未使用的节点并使用。如果 Alloc_elems >= Max_elems，则表示存储限制已达到，因此无法再分配更多节点。
插入元素的位置可以通过索引存储中的特定位置来找到。该位置的节点指针指向空闲节点，并将空闲节点的值设置为新值。在插入之前，将更新新插入节点之后的所有节点，以便每个节点指针（在节点中）根据其插入之前的相应位置被赋予前一个节点的指针。这会扩展到最后一个节点之后的节点，因此该节点指向的元素现在成为列表中的最后一个元素。列表元素数量加 1。如果要将新元素添加到列表末尾，则只需要进行与获取空闲节点及其在相应位置被节点指向相关的操作。
与在数组中添加元素相比，操作看起来与 PAL 几乎相同。然而，这里的主要区别在于，而不是逐字节复制每个元素值，只更新节点的指针。因此，与数组添加相比，添加操作更有效，但比链表添加效率低。
/**
* While adding an element at a particular position which is not the
* last position of the list, care should be taken to update all the
* element pointers that begin with the old element at the point of
* addition.
* For example if the current list allocation is as follows:
* 1,3,4,5
* If an element 2 is now added at position 2, all position pointers
* starting from position 2 need to be updated.
*/
template <class T,int N>
bool CPArrayList<T,N>::insert(T info, int pos)
{
int nextpos = m_filledelems;
node <T> *freenode = 0;
/**
* First look at the free node list to return any
* node that was freed.
*/
if(m_filledelems < m_allocelems)
{
freenode = getNodeAtPos(m_filledelems)->posptr;
}
// Next return a freenode if any from the buffer.
else if(m_allocelems < m_capacity)
{
freenode = (node<T> *) (BUFFER + m_allocelems * m_nodesize);
++m_allocelems;
}
else
return false;
freenode->val = info;
for(; nextpos > pos; --nextpos)
{
getNodeAtPos(nextpos)->posptr = getNodeAtPos(nextpos-1)->posptr;
}
getNodeAtPos(pos)->posptr = freenode;
++m_filledelems;
return true;
}
元素删除
如果要在列表中的位置 x（其中 x>0）删除一个元素，则首先将此位置节点指向的节点压入空闲列表堆栈。之后，更新从该位置到倒数第二个节点（即 n 个节点中的 n-1th 个位置）的所有节点指针，以便每个节点的指针都更新为下一个节点的指针，以在删除操作后压缩列表。因此，现在列表的最后一个节点是删除操作之前的倒数第二个节点。列表元素数量减 1。
/**
* The deletion of an element at a particular position is a critical operation
* in the list.
* In most of the cases related to deletion it is necessary to update links for
* elements that follow the newly deleted element.
*/
template <class T,int N>
void CPArrayList<T,N>::remove(int pos)
{
/**
* On deletion of an element at a position, we need to update
* the position pointers of all nodes that come after the
* deletion position.
*/
node <T> *newfreenode = getNodeAtPos(pos)->posptr;
int nextpos = pos;
for(;nextpos < (m_filledelems-1); nextpos++)
{
getNodeAtPos(nextpos)->posptr = getNodeAtPos(nextpos+1)->posptr;
}
getNodeAtPos(nextpos)->posptr = newfreenode;
--m_filledelems;
}
示例说明
- 预分配后初始状态
已分配节点 - 0，已填充节点 - 0（所有 5 个节点都已预分配，但尚未实际使用，因此已分配和已填充节点计数为空。每当从存储中返回一个新节点（而不是包含已删除节点的空闲列表）时，已分配节点计数会增加。已填充节点计数表示 PAL 当前正在使用的元素数量。
- 在位置 1 添加值为 1 的节点后
已分配节点 - 1，已填充节点 - 1
- 在位置 2 添加值为 4 的节点后
已分配节点 - 2，已填充节点 - 2
- 在位置 2 添加值为 2 的节点后
已分配节点 - 3，已填充节点 - 3
- 在位置 3 添加值为 3 的节点后，总共分配了 4 个节点（1、2、3 和 4）
已分配节点 - 4，已填充节点 - 4
- 在位置 5 添加值为 5 的节点后（1、2、3、4、5）
已分配节点 - 5，已填充节点 - 5
- 删除位置 3 的节点后（1、2、4 和 5）；请注意，现在第 4 个节点包含一个已被删除的值，但它仍然指向一个有效节点（值为 5），该节点又指向已删除的节点。由于它指向已删除的节点，节点 5 是空闲列表的一部分。
已分配节点 - 5，已填充节点 - 4，空闲列表节点 - 1
- 删除位置 2 的节点后（1、4 和 5）；除了指向已删除节点（值为 2 的第 3 个节点）外，第 4 个节点本身也被删除了。节点 5 包含有效值但指向已删除节点。第 4 个节点现在被纳入空闲列表（其中已包含第 5 个节点）。因此，无论删除位置如何，最后一个节点（删除前填充的节点中的最后一个）始终指向最近删除的节点。这也便于在将来的添加操作中重新使用已删除的节点。
已分配节点 - 5，已填充节点 - 3，空闲列表节点 - 2
- 在位置 2 添加值为 3 的节点后（1、3、4 和 5）；由于已填充节点 < 已分配节点，因此被指向最后一个节点之后的节点指向的节点（值为 2 的节点）被新值替换。在总空闲节点数减少后，已填充节点数增加 1。
已分配节点 - 5，已填充节点 - 4，空闲列表节点 - 1
- 在位置 2 添加值为 2 的节点后（1、2、3、4 和 5）；由于已填充节点 < 已分配节点，因此被指向最后一个节点之后的节点（上面第 4 个节点，值为 3）被新值填充。在总空闲节点数减少后，已填充节点数增加 1。
已分配节点 - 5，已填充节点 - 5，空闲列表节点 - 0
与 Vector 和 List 的比较
Vector 是顺序容器，元素按照严格的线性顺序排列。Vector 容器实现为动态数组，其元素存储在连续的存储位置，允许使用指向元素的常规指针通过偏移量访问其元素。
Vector 的优点在于
- 按位置索引访问单个元素（常数时间）。
- 按任意顺序迭代元素（线性时间）。
- 向其末尾添加和删除元素（常数摊销时间，如下面的结果表中所示）。
List 容器实现为双向链表。双向链表可以将其包含的每个元素存储在不同且不相关的存储位置。通过将指向前一个元素和后一个元素的链接与每个元素关联来保持顺序。
这为 List 容器提供了以下优势
- 在容器内的任何位置高效插入和删除元素（常数时间）。
- 高效地在容器内，甚至在不同容器之间移动元素和元素块（常数时间）。
- 向前或向后迭代元素（线性时间）。
与其他的基本标准顺序容器（如 list）相比，Vector 在访问元素以及在序列末尾添加或删除元素方面通常效率最高。对于涉及在末尾以外的位置插入或删除元素的这些操作，它们的性能不如 list。
PAL 在拥有 Vector 的所有上述指定优势的同时，与 Vector 相比，其插入和删除操作更快（因为只复制指针而不是整个元素，如前所述）。
与链表和 vector 容器的决战
|
元素 |
元素大小（字节） |
PAL 成本（秒） |
Vector 成本（秒） |
List 成本（秒） |
||||||
|
|
|
start
|
随机 |
end |
start
|
随机 |
end |
start
|
随机 |
end |
|
2383 |
77 |
0.016 |
0.02 |
0 |
0.12 |
0.06 |
0.008 |
0.004 |
0.02 |
0 |
|
2383 |
110 |
0.017 |
0.013 |
0 |
0.14 |
0.065 |
0 |
0 |
0.03 |
0 |
|
2383 |
210 |
0.017 |
0.013 |
0 |
0.22 |
0.111 |
0.001 |
0 |
0.029 |
0 |
|
2383 |
325 |
0.017 |
0.001 |
0 |
0.25 |
0.125 |
0 |
0.001 |
0.03 |
0 |
|
2383 |
435 |
0.016 |
0.015 |
0 |
0.3 |
0.141 |
0.01 |
0.004 |
0.03 |
0 |
|
2383 |
540 |
0.017 |
0.016 |
0 |
0.37 |
0.178 |
0.005 |
0.001 |
0.029 |
0 |
|
2383 |
650 |
0.020 |
0.012 |
0 |
0.44 |
0.219 |
0.01 |
0.004 |
0.023 |
0 |
|
2383 |
760 |
0.023 |
0.003 |
0 |
0.48 |
0.234 |
0.005 |
0 |
0.033 |
0 |
|
2383 |
870 |
0.017 |
0.013 |
0 |
0.62 |
0.307 |
0.01 |
0 |
0.031 |
0 |
对于 PAL 和 Vector，在列表开头进行的插入被认为是最昂贵的操作之一。对于 List，这应该是随机插入操作。
如上表所示，随着元素大小的增加，使用 Vector 的成本与 PAL 相比增加（因为 PAL 只复制节点地址而不是整个节点）。List 仅在开头添加时表现更好，在随机添加时 PAL 表现更好。与元素大小无关，PAL 和 List 在相似操作上的插入操作成本几乎恒定。
|
元素 |
元素大小（字节） |
PAL 成本（秒） |
Vector 成本（秒） |
List 成本（秒） |
||||||
|
|
|
start
|
随机 |
end |
start
|
随机 |
end |
start
|
随机 |
End |
|
2383 |
77 |
0.03 |
0.011 |
0 |
0.113 |
0.052 |
0 |
0 |
0.027 |
0 |
|
2383 |
110 |
0.016 |
0.005 |
0 |
0.14 |
0.073 |
0 |
0 |
0.022 |
0.002 |
|
2383 |
210 |
0.02 |
0.005 |
0 |
0.211 |
0.106 |
0 |
0 |
0.029 |
0 |
|
2383 |
325 |
0.017 |
0.014 |
0 |
0.24 |
0.114 |
0 |
0 |
0.029 |
0 |
|
2383 |
435 |
0.016 |
0.014 |
0 |
0.28 |
0.14 |
0 |
0 |
0.017 |
0.002 |
|
2383 |
540 |
0.024 |
0.002 |
0 |
0.35 |
0.179 |
0 |
0 |
0.023 |
0 |
|
2383 |
650 |
0.015 |
0.005 |
0 |
0.412 |
0.211 |
0 |
0 |
0.019 |
0.002 |
|
2383 |
760 |
0.019 |
0.01 |
0 |
0.455 |
0.223 |
0 |
0 |
0.026 |
0 |
|
2383 |
870 |
0.018 |
0.011 |
0 |
0.555 |
0.272 |
0 |
0 |
0.029 |
0 |
对于 PAL 和 Vector，在列表开头进行的删除被认为是最昂贵的操作之一。对于 List，这应该是随机删除。
如上表所示，随着元素大小的增加，使用 Vector 的成本与 PAL 相比增加（因为 PAL 只复制节点地址而不是整个节点）。List 仅在开头删除时表现更好，在随机删除时 PAL 表现更好。与元素大小无关，PAL 和 List 在相似操作上的删除操作成本几乎恒定。
结论
如果将随机插入/删除视为实际中的常态，那么与 Vector 和 List 相比，PAL 在性能方面具有优势。
感谢对本文提出的评论，这些评论有助于本文的更新。期待更多有价值的评论，请不要忘记评价本文。