一种可按插入顺序和数量级遍历的数据结构
A data structure traversable by both order of insertion and order of magnitude
有没有一种数据结构可以同时遍历O(n)的插入顺序和数量级，最多O(log(n))次插入和删除？
换句话说，给定元素 5、1、4、3、2（按此顺序插入），可以在 O(n) 时间内将其遍历为 1,2,3,4,5 或 5,1,4,3,2 .
当然我可以使用数组并在遍历之前简单地对其进行排序，但这需要一个 O(n*log(n)) 预遍历步骤。另外，我可以使用多链表来实现 O(n) 遍历，但在这种情况下，插入和删除操作也需要 O(n)，因为我不能保证最新的元素一定是最大的。
如果存在这样的数据结构，请给我一个正式的名称，以便我进一步研究，如果没有，请提供一个简短的表面描述。
谢谢
评论者是对的：最好的办法是将对象存储两次：一次在链表中（插入顺序），一次在二叉树中（内部排序顺序）。
这并不像听起来那么糟糕，因为您不必复制对象，因此唯一的成本是 list/tree 脚手架，这将花费您每个存储对象 4 个机器字。
一个也允许亚线性删除的解决方案是构建一个数据结构D，它使用linked列表D.L按插入顺序遍历，以及一个排序树D.T 为按数量级遍历。但是如何 link 它们在次线性时间内额外实现删除操作呢？诀窍是 D.T 应该 而不是 存储 值 ，而只是 对相应 [=47] 的引用=]ed 列表元素 in D.L.
插入：追加到D.L的时间O(1)，插入追加元素的引用到D.T的时间O(log (n)). D.T 中的任何比较当然是在引用值上进行的，而不是引用本身)
按插入顺序（或向后）遍历：简单地在时间O(n)内线性遍历D.L
按数量级（或向后）遍历：简单地通过树遍历
在时间O(n)内遍历D.T
删除：首先在O(log n)时间内找到并删除D.T中的元素，这也为您提供了对D.L的正确元素引用，所以它可以在时间 O(1).
中从 D.L 中删除
你甚至不需要两个数据结构。只需使用二叉树，而不是插入您的对象，而是将其包装在一个对象中，该对象还包含指向上一个和下一个对象的指针。这在像 java 这样的主流语言中是相当微不足道的，你可以使用带有比较器的默认树实现来按 属性.
排序你的树
只要保留对第一个和最后一个元素的引用，就可以使用对象的内部指针按顺序遍历它们。
有没有一种数据结构可以同时遍历O(n)的插入顺序和数量级，最多O(log(n))次插入和删除？
换句话说，给定元素 5、1、4、3、2（按此顺序插入），可以在 O(n) 时间内将其遍历为 1,2,3,4,5 或 5,1,4,3,2 .
当然我可以使用数组并在遍历之前简单地对其进行排序，但这需要一个 O(n*log(n)) 预遍历步骤。另外，我可以使用多链表来实现 O(n) 遍历，但在这种情况下，插入和删除操作也需要 O(n)，因为我不能保证最新的元素一定是最大的。
如果存在这样的数据结构，请给我一个正式的名称，以便我进一步研究，如果没有，请提供一个简短的表面描述。
谢谢
评论者是对的：最好的办法是将对象存储两次：一次在链表中（插入顺序），一次在二叉树中（内部排序顺序）。
这并不像听起来那么糟糕，因为您不必复制对象，因此唯一的成本是 list/tree 脚手架，这将花费您每个存储对象 4 个机器字。
一个也允许亚线性删除的解决方案是构建一个数据结构D，它使用linked列表D.L按插入顺序遍历，以及一个排序树D.T 为按数量级遍历。但是如何 link 它们在次线性时间内额外实现删除操作呢？诀窍是 D.T 应该 而不是 存储 值 ，而只是 对相应 [=47] 的引用=]ed 列表元素 in D.L.
插入：追加到D.L的时间O(1)，插入追加元素的引用到D.T的时间O(log (n)). D.T 中的任何比较当然是在引用值上进行的，而不是引用本身)
按插入顺序（或向后）遍历：简单地在时间O(n)内线性遍历D.L
按数量级（或向后）遍历：简单地通过树遍历
在时间O(n)内遍历D.T
删除：首先在O(log n)时间内找到并删除D.T中的元素，这也为您提供了对D.L的正确元素引用，所以它可以在时间 O(1).
D.L 中删除
你甚至不需要两个数据结构。只需使用二叉树，而不是插入您的对象，而是将其包装在一个对象中，该对象还包含指向上一个和下一个对象的指针。这在像 java 这样的主流语言中是相当微不足道的，你可以使用带有比较器的默认树实现来按 属性.
排序你的树只要保留对第一个和最后一个元素的引用，就可以使用对象的内部指针按顺序遍历它们。