问题标签 [insertion-order]

我正在寻找的数据结构应该是标准关联的，允许在给定唯一键的情况下快速（至少优于 O(n)）检索/替换/添加/删除项目，就像任何树或哈希图一样。

棘手的部分是还要公开以下内容（也比 O(n) 好）：

index 是插入顺序（在添加时），如果发生删除，则更新。

这是我想要的一个例子：

我想我知道如何自己实现一个，但我想知道这样的容器是否已经存在。

我有一个LinkedHashMap. LinkedHashMap保留插入顺序。我需要获取这张地图的值，并且我需要它们的顺序相同。因此，如果我values()在 this 上调用方法LinkedHashMap，Collection我从values()方法中检索到的将保证插入顺序？

在 Scala 中，将元素添加到不可变列表的方式如下：

这意味着您首先创建一个 Nil（空）列表，然后添加 2 和 1。即这些操作是右关联的。因此，有效地，它可以以更清晰的方式重写，如下所示：

问题是，如果 List 应该保留插入顺序，并且如果先将 2 添加到空列表然后添加 1，那么为什么答案不是l: List[Int] = List(2, 1)？

尝试插入有序列表时，请考虑两种情况。

1. 使用指针数组。二进制搜索以查找插入点的位置：

   • 使用 memmove() 移动字节为新地址腾出空间

   • 使用迭代移动地址以为新地址腾出空间

2. 使用链表和线性搜索

哪个表现更好？我的猜测是，在优化代码中，1. 的两个选项的性能大致相同，但 1. 和 2. 将如何比较。似乎它们都是 O(n)。有没有更简单的方法来做到这一点？是否可以在任何类型的链表上设置二进制搜索？

非常欢迎任何其他建议。

是否有一个标准的 swift 类，它是一个 Dictionary，但像Java 的 LinkedHashMap一样将键保持在插入顺序中？如果没有，将如何实施？

您好，我是 c 新手，所以我的代码有一些问题。我的代码应该显示一个菜单，如果您想添加、搜索、删除或打印所有内容，该菜单会显示。但是，这有效，我的插入部分无效。当我选择添加并开始输入我希望程序崩溃的信息时？

这是我的代码

我面临一个应用程序，我必须设计一个具有随机访问（或至少比 O(n) 更好）的容器具有便宜的 (O(1)) 插入和删除，并根据顺序存储数据（等级) 在插入时指定。

例如，如果我有以下数组：

我可以调用索引 2 上的 remove 来删除 10，我也可以通过插入 13 来调用索引 1 上的 insert。

在这两个操作之后，我将拥有：

这些数字存储在一个序列中，插入/删除操作需要一个索引参数来指定应该在哪里插入数字或应该删除哪个数字。

我的问题是，除了链表和向量之外，什么样的数据结构可以维护这样的东西？我倾向于优先考虑下一个可用索引的堆。但我一直看到一些关于融合树有用的东西（但更多的是理论上的意义）。

什么样的数据结构可以给我最佳的运行时间，同时还能降低内存消耗？我一直在玩一个保留插入顺序的哈希表，但到目前为止它一直没有成功。

我直接使用 std:: 向量的原因是因为我必须构造一些东西，根据这些基本操作预先形成向量。容器的大小有可能增长到数十万个元素，因此在 std::vector 中进行转换是不可能的。与链表相同的问题（即使是双链表），在最坏的情况下遍历它到给定的索引将需要 O (n/2)，它被舍入到 O (n)。

我正在考虑一个包含 Head、Tail 和 Middle 指针的双向链表，但我觉得不会好多少。

很困惑如何在根节点插入。它与在根节点和非叶节点插入一样吗？，谢谢

假设我有一个LinkedHashMap<String, Double> myMap我添加pair1的 , pair2,pair3对。

现在我执行以下循环：

Double循环中的第一个对象会是吗pair1？第二个pair2？还是不必？

我检查了类似的程序，似乎它确实保持了插入顺序，但总是这样吗？

我很难想象我的程序将如何插入元素。这是老师给我们的代码：

遗憾的是，我无法理解和想象它是如何将元素放入树中的。据我了解，它使用递归分治算法将数组分成两部分并添加元素，但是我无法理解哪个元素成为根。有人可以帮我想象一下插入所有内容后树的外观吗？