我正在寻找一些简单实现的数据结构，以最短的时间（在最坏情况下）满足我的需求：
（1）弹出第n个元素（我必须保持元素的相对顺序不变）
（2）访问第n个元素。
我不能使用数组，因为它无法弹出元素，并且我不想在删除第i个元素后留下间隙。我尝试通过将第n个元素与下一个元素交换，再重复下去直到最后一个元素来消除间隙，但这证明是时间上的低效率，即使数组的O(1)无人能敌。
我尝试使用向量并使用“erase”进行弹出和“.at()”进行访问，但即使它比数组更好，但对于时间效率来说仍然不便宜。
4个回答
3
好的，我认为在数组上实现分层向量是最适合您的目的的。虽然分层向量的概念可能会有点棘手，而且很难理解，但是一旦你了解了它，它就能够回答许多问题，并且使你更加高效地处理许多数据结构部分。所以建议您掌握分层向量的实现。
- Maggi Iggam
3
- Ivaylo Strandjev
3
是的，我觉得分层也可能是一个不错的选择，我会尝试一下 :) - Manas Verma
@izomorphuis，能否提供一个展示“分层向量”实现的链接，这真的很有趣。 - Manas Verma
我之前已经实现了它，我相信我使用的是我发送给你的相同文章。如果你知道如何在数组分层向量中实现循环队列，那么这就非常简单了。我可能能够找到我的源代码，但我不确定它是否“公开”。;) - Ivaylo Strandjev
2
一个数组会给你
一个二叉搜索树会给你
在列表中使用二叉搜索树将会给你最好的两个方面。把节点插入到列表（以保持顺序）和树中（快速查找）。删除操作将是
请注意，如果使用索引作为排序值将节点插入到树中，则最终得到的将是另一个假装是树的链接列表。一旦构建完成，可以在 O(n) 的时间内平衡 树，而这只需要一次性地发生。
更新：
考虑了更多后，这可能不是您最好的方法。我习惯于对数据本身进行查找，而不是其在集合中的相对位置。这是一种以数据为中心的方法。如果将索引用作排序值，则一旦删除节点，它将会崩溃，因为“较高”的索引将需要更改。
O(1)的查找时间，但O(n)的删除元素时间。
一个列表会给你O(n)的查找时间，但O(1)的删除元素时间。一个二叉搜索树会给你
O(log n)的查找时间和O(1)的删除元素时间。但它不保留相对顺序。在列表中使用二叉搜索树将会给你最好的两个方面。把节点插入到列表（以保持顺序）和树中（快速查找）。删除操作将是
O(1)。struct node {
node* list_next;
node* list_prev;
node* tree_right;
node* tree_left;
// node data;
};
请注意，如果使用索引作为排序值将节点插入到树中，则最终得到的将是另一个假装是树的链接列表。一旦构建完成，可以在 O(n) 的时间内平衡 树，而这只需要一次性地发生。
更新：
考虑了更多后，这可能不是您最好的方法。我习惯于对数据本身进行查找，而不是其在集合中的相对位置。这是一种以数据为中心的方法。如果将索引用作排序值，则一旦删除节点，它将会崩溃，因为“较高”的索引将需要更改。
- Dave Rager
2
好的，我会尝试一下 :) ，但是有一个问题，我不需要在第n次弹出后再次排序吗？ - Manas Verma
是的，我更新了我的帖子。我刚刚阅读了 @izomorphius 提到的分层向量，这可能更加合适。 - Dave Rager
0
警告：不要认真看待这个答案。
理论上，你可以在O(1)的时间内完成这两个操作。假设这是你想要优化的唯一操作。以下解决方案将需要大量空间（而且会泄漏空间），并且创建数据结构将需要很长时间：
使用一个数组，在数组的每个条目中指向另一个数组，该数组与其相同，但已删除该条目。
- Sebastian
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
std::deque怎么样？虽然我不是很了解它。 - Alvin Wong