c++ - 将短列表合并为长 vector 的算法

Question

我有一个稀疏矩阵类，其非零值和相应的列索引按行顺序存储在基本上类似于 STL vector 的容器中。它们可能有未使用的容量，比如 vector ；要插入/删除元素，必须移动现有元素。

假设我有一个操作，insert_erase_replace，或者简称为ier。 ier 可以执行以下操作，给定位置 p、列索引 j 和值 v:

• 如果 v==0，ier 删除 p 处的条目并左移所有后续条目。
• 如果 v!=0，并且 j 已经存在于 p 中，ier 替换单元格内容在 p 和 v。
• 如果 v!=0，并且 j 不在 p 中，ier 插入条目 v 和 p 处的列索引 j 右移所有后续条目后。

所以所有这些都是微不足道的。

现在假设我有 ier2，它做同样的事情，除了它需要一个包含多个列索引 j 和相应值 v。它还具有大小 n，表示列表中存在多少个索引/值对。但是因为 vector 只存储非零值，所以有时实际插入的大小小于n。

仍然微不足道。

但现在假设我有 ier3，它不仅采用像 ier2 这样的一个列表，而且采用多个列表。这表示编辑稀疏矩阵的一部分。

在某些时候，遍历 vector 、逐段复制它们并插入/替换/删除列表索引/值 ier2 样式在我们到达每个插入点时变得更加高效.如果总插入大小会导致我的 vector 无论如何都需要调整大小，那么我们会这样做。

鉴于我的 vector 比列表的总长度大得多，是否有一种算法可以有效地将列表合并到 vector 中？

到目前为止，这是我所拥有的:

• 传递给 ier3 的每个列表表示条目的净删除(左移)、净替换(没有移动，因此便宜)或条目的净插入(a右移)。那里可能还有一些元素的重新排列，但昂贵的部分是净删除和净插入。

• 不难找出一种算法来有效地仅进行净插入或净删除。

• 当这两种情况中的任何一种发生时，情况就更难了。

我唯一能想到的就是分两次处理它:

1. 删除/替换
2. 插入/替换

我们首先删除，因为这使得任何插入都更有可能需要更少的拷贝。

这是正确的方法吗？有人知道更好的吗？

Answer 1

好的，所以我假设 ier3 中每个列表中涵盖的间隔是不相交的，并且按顺序提供给您。如果它用于编辑矩阵的切片，这似乎是合理的。我还假设您不需要调整 vector 的大小，因为这种情况很容易检测和解决。

将read 指针和write 指针初始化为您正在编辑的 vector 的开头。也将有一个指向 ie3 的 instruction 指针，但为了清楚起见，我将在这里忽略它。您还需要一个队列。在每个步骤中，可能会发生以下几种情况之一:

• 默认:read 和write 都不在ier3 详细说明的位置。在这种情况下，将read下的元素添加到队列的后面，并将队列前面的元素写入到write下的单元格中。将两个指针向前移动一个。

• read 越过需要删除的单元格。在这种情况下，只需将 read 向前移动一个而不向队列中添加任何内容。

• read 从一个单元格传递到下一个单元格，以便在它们之间进行插入。在这种情况下，将插入添加到队列的后面，然后继续下一个相关案例。

• read 在需要修改的单元格处。在这种情况下，将修改后的单元格插入队列的后面，将队列前面的任何内容写入 write，然后将它们都向前移动。

• read 已到达 vector 的未使用容量。在这种情况下，只需写入队列中剩下的任何内容即可。

这是基本的轮廓，但可以进行一些优化:首先，如果队列为空，则将两个指针向前移动到 ie3 详细说明的下一个位置，而不做任何事情。其次，每当 read 领先于 write 并且队列为非空时，通过执行额外的写入步骤来最小化缓冲区。