vector<vector> 作为快速遍历的二维数据结构
vector<vector> as a quick-traversal 2d data structure
我目前正在考虑实施 2D 数据结构，以允许我以正确的 Z 顺序存储和绘制对象（GDI+，实体按调用顺序绘制）。要求松散：
- 能够将新对象添加到任何深度索引的顶部
- 能够删除任意对象
- （能够将对象移动到新深度索引的顶部，通过以上 2 点实现）
- 快速的中序和逆序遍历
由于主要要求是遍历完整数据的速度，首先想到的是类似数组的结构，例如。向量。它还可以轻松地允许推送新对象（删除不太好的对象......）。这完全符合我们的要求，因为碰巧大部分可绘制实体没有变化，而那些确实位于订单顶端的实体。
然而，这让我想到了更多动态需求的含义：
- 向量将根据需要自行调整大小 -> 因为 'depth' 向量需要在内存中连续维护（顶级向量强制执行），这可能导致一些相当昂贵的向量调整大小。最坏的情况是所有向量都需要移动到新的内存位置，平均情况需要移动链上的所有向量。
- 向量通常会在末尾保留一个缓冲区用于添加新对象 -> 遍历在 'depth' 向量之间跳转时仍然很容易导致缓存未命中，从而使顶级向量的连续内存变得不那么有用
有人可以确认这些观察确实是正确的，使向量成为存储更大动态数据集的最昂贵的结构吗？
根据我上面的想法，我最终推断出在遍历整个数据集时，特别是在顶级向量中的不同向量之间跳转时，你还不如使用任何其他遍历复杂度较低的数据结构，或者类似的随机访问复杂度（linked_list；映射）。遍历实际上是相同的，因为我们不妨假设缓存未命中无论如何都会发生，并且我们通过不在内存中连续保存深度向量来省去很多麻烦。
这确实是一个好的解决方案吗？如果我没记错的话，在一维问题 space 上，这将归结为更重要的遍历或 addition/removal、向量或链表。在 2D space 上，我不太确定它是黑白的。
我想知道什么样的应用程序需要良好的二维遍历 space，而不影响数据 addition/removal，以及那里使用了什么样的数据结构。
P.S。我只是注意到我完全忽略了 space-复杂性，所以不妨继续忽略它（除非您想增加更多洞察力 :D）
我想链表会更合适，因为您将始终遍历整个列表（向量有利于随机访问）。链接列表的插入和删除非常便宜，并且遍历与向量遍历没有什么不同。也许你应该考虑双向链表，因为你想以两种方式遍历它。
您的第一个假设有些不正确。
不要将向量视为内存块本身，而是将其视为 指针 以自动管理内存块和一些元数据以跟踪它。矢量本身是 固定 大小，它跟踪的内存不是。 （看这个例子，注意vector对象的大小是常数：https://ideone.com/3mwjRz）
一个向量的向量可以被认为是一个指针数组。调整指针指向的内容并不意味着您需要调整包含它们的数组的大小。项目连续的承诺仍然成立：父数组具有所有彼此相邻的指针，并且每个指针指向一个连续的内存块。但是，不能保证 arr[0][N-1] 的结尾与 arr[1][0] 的开头相邻。 （为此，你的第二点是正确的。）
我目前正在考虑实施 2D 数据结构，以允许我以正确的 Z 顺序存储和绘制对象（GDI+，实体按调用顺序绘制）。要求松散：
- 能够将新对象添加到任何深度索引的顶部
- 能够删除任意对象
- （能够将对象移动到新深度索引的顶部，通过以上 2 点实现）
- 快速的中序和逆序遍历
由于主要要求是遍历完整数据的速度，首先想到的是类似数组的结构，例如。向量。它还可以轻松地允许推送新对象（删除不太好的对象......）。这完全符合我们的要求，因为碰巧大部分可绘制实体没有变化，而那些确实位于订单顶端的实体。
然而，这让我想到了更多动态需求的含义：
- 向量将根据需要自行调整大小 -> 因为 'depth' 向量需要在内存中连续维护（顶级向量强制执行），这可能导致一些相当昂贵的向量调整大小。最坏的情况是所有向量都需要移动到新的内存位置，平均情况需要移动链上的所有向量。
- 向量通常会在末尾保留一个缓冲区用于添加新对象 -> 遍历在 'depth' 向量之间跳转时仍然很容易导致缓存未命中，从而使顶级向量的连续内存变得不那么有用
有人可以确认这些观察确实是正确的，使向量成为存储更大动态数据集的最昂贵的结构吗？
根据我上面的想法，我最终推断出在遍历整个数据集时，特别是在顶级向量中的不同向量之间跳转时，你还不如使用任何其他遍历复杂度较低的数据结构，或者类似的随机访问复杂度（linked_list；映射）。遍历实际上是相同的，因为我们不妨假设缓存未命中无论如何都会发生，并且我们通过不在内存中连续保存深度向量来省去很多麻烦。
这确实是一个好的解决方案吗？如果我没记错的话，在一维问题 space 上，这将归结为更重要的遍历或 addition/removal、向量或链表。在 2D space 上，我不太确定它是黑白的。
我想知道什么样的应用程序需要良好的二维遍历 space，而不影响数据 addition/removal，以及那里使用了什么样的数据结构。
P.S。我只是注意到我完全忽略了 space-复杂性，所以不妨继续忽略它（除非您想增加更多洞察力 :D）
我想链表会更合适，因为您将始终遍历整个列表（向量有利于随机访问）。链接列表的插入和删除非常便宜，并且遍历与向量遍历没有什么不同。也许你应该考虑双向链表，因为你想以两种方式遍历它。
您的第一个假设有些不正确。
不要将向量视为内存块本身，而是将其视为 指针 以自动管理内存块和一些元数据以跟踪它。矢量本身是 固定 大小，它跟踪的内存不是。 （看这个例子，注意vector对象的大小是常数：https://ideone.com/3mwjRz）
一个向量的向量可以被认为是一个指针数组。调整指针指向的内容并不意味着您需要调整包含它们的数组的大小。项目连续的承诺仍然成立：父数组具有所有彼此相邻的指针，并且每个指针指向一个连续的内存块。但是，不能保证 arr[0][N-1] 的结尾与 arr[1][0] 的开头相邻。 （为此，你的第二点是正确的。）