问题标签 [insertion-order]

我目前有一个std::map<std::string,int> 将整数值存储到唯一字符串标识符的方法，并且我确实使用该字符串进行查找。它主要做我想要的，除了它不跟踪插入顺序。因此，当我迭代地图以打印出值时，它们会根据字符串进行排序；但我希望它们根据（第一次）插入的顺序进行排序。

我考虑过使用 avector<pair<string,int>>代替，但我需要查找字符串并将整数值递增约 10,000,000 次，所以我不知道 a 是否std::vector会明显变慢。

有没有办法使用std::map或者是否有其他std容器更适合我的需要？

我在 GCC 3.4 上，我的std::map.

我尝试过使用Map,HashMap和LinkedHashMap作为 AutoBean 工厂的类型，并且总是在序列化之后改变初始元素的顺序。

我不想发送ArrayList包含订单数据的附加信息。有没有办法强制 AutoBean 保持秩序Map？

与 Perl 打交道并已被阻止的第一天 :)

情况是这样的：一个文件在文件夹 A 中更新，但也存在于文件夹 B、C 和 D 中，为了更容易，所有文件都可以不同，所以我不能只做一个差异。打算复制到其他文件的新行由行尾的标志标识，例如#I。

更新前的文件如下所示：

更新后是这样的：

我需要做的是在其他文件上搜索“第二行”，插入标有#I的行 - 按照它们插入的顺序 - 然后搜索“第五行”并插入“第六行#I” .

在这个例子中，它们都是连续的，但是在我需要更新的文件中，第一个更新块和第二个（以及第三个等等）之间可以有几行。

将要更新的文件可以是sh脚本、awk脚本、纯文本文件等，脚本应该是通用的。该脚本将有两个入口参数，更新的文件和要更新的文件。

欢迎提供有关如何执行此操作的任何提示。如果需要，我可以提供到目前为止的代码 - 关闭但尚未工作。

谢谢，

若昂

PS：这是我到目前为止所拥有的

获得的结果几乎是我想要但还没有的结果。

Java 中是否有现有的List实现基于提供的顺序来维护Comparator？

可以通过以下方式使用的东西：

以便someT插入，以便列表中的顺序根据cmp

（根据@andersoj 的建议，我又提出了一个要求来完成我的问题）

此外，我希望能够在不删除元素的情况下按排序顺序遍历列表，即：

应该通过。

欢迎所有建议（除了告诉我Collections.sort在无序的完整列表中使用），不过，我更喜欢其中java.*或最终的东西，org.apache.*因为此时很难引入新的库。

注意：（UPDATE4）我意识到这种列表的实现会性能不足。有两种通用方法：

1. 使用链接结构（某种）B-tree 或类似的
2. 使用数组和插入（使用二分查找）

1. CPU 缓存未命中有问题 2. 数组中的元素移位有问题。

UPDATE2： TreeSet不起作用，因为它使用提供的比较器 (MyComparator) 来检查是否相等，并基于它假定元素相等并排除它们。我只需要比较器进行排序，而不是“唯一性”过滤（因为元素的自然排序不相等）

UPDATE3： PriorityQueue不工作List（因为我需要），因为没有办法按“排序”的顺序遍历它，要按排序顺序获取元素，您必须将它们从集合中删除。

更新：

类似的问题：
A good Sorted List for Java
Sorted array list in Java

寻找一个插入顺序集合，该集合还允许高效查询和位置子集视图（如子列表）。似乎最直接的选择是采用 List 的链表方法，将节点嵌入为映射值，并在类上公开部分或全部列表接口。

有人会为此向甲骨文抱怨吗？为排序的地图和集合添加了 NavigableMap/Set 并且没有更常见的插入顺序等价物......

编辑：请不要建议 LinkedHashSet - 它没有任何方法可以查询位置或做一个相对子集。

我有以下问题。在我的服务器上，我必须按特定顺序维护数据（按照特定的插入顺序）。它必须存储在一个文件中。我目前正在使用 SQLite 来执行此操作，但是假设 SQL db 将保持插入顺序是否安全，或者我应该使用其他东西（在这种情况下，请给我提示该怎么做）。

假设我们正在处理键 1-15。要获得常规 BST 的最坏情况性能，您可以按升序或降序插入键，如下所示：

1、2、3、4、5、6、7、8、9、10、11、12、13、14、15

那么BST本质上就会变成一个链表。

对于 BST 的最佳情况，您可以按以下顺序插入键，它们的排列方式是，插入的下一个键是要插入的总范围的一半，所以第一个是 15/2 = 8，然后是 8 /2 = 4 等等...

8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15

那么 BST 将是一棵平衡良好的树，最佳高度为 3。

红黑树的最佳情况也可以用 BST 的最佳情况来构造。但是我们如何构建红黑树的最坏情况呢？它与 BST 的最坏情况相同吗？是否存在会产生最坏情况的特定模式？

当我使用地图时，我倾向于选择那些元素可以按照插入顺序进行迭代的地图。这让他们感觉更有确定性并且更容易测试。由于这个原因和其他原因，我一直是 Java 中 LinkedHashMap 的傻瓜。

在 FP 世界中，对于查找而言，树优先于地图。诚然，在 Scala 中有一个不可变的 LinkedHashMap 版本，称为 ListMap，但它不使用哈希，而且对于大多数实际用途来说似乎太慢了。

如果我想获得不变性的优势，我如何才能满足我对能够记住插入顺序和快速查找的数据结构的渴望？有人在某处的图书馆里写过东西吗？

这是我的插入排序，与“算法简介”一书中的方式完全相同：

这打印：

我做错了什么让它们出现故障？

有谁知道插入顺序对 2-3-4 树有什么影响？还是 B 树？

似乎最小高度的公式是 log _m (k+1)，其中 m 是最大高度。孩子的数量，k 是键的数量

最大高度的公式是：log _n ((k+1)/2) 其中 n 是最小高度。一个内部节点可以拥有的子节点数。

但是什么插入序列实际上得到了这些结果？！我不知道。

有人建议最小化 2-3-4 树的高度，你可以取线性序列的中值，例如。1,2,3,4,5,6,7,8 它是 4，并插入它，然后再重复冲洗子列表中位数的任一侧。这是真的？如果是这样，什么序列使高度最大化？