用于在给定索引处插入,删除和重新排列的高效C#数据结构

Question

我正在寻找C#中一个高效的数据结构,它允许我保留一份(由用户)订购的项目列表,而不需要重复.

我的意思是由用户订购,即:

• 插入元素1.
• 在元素1之前插入元素2.
• 将元素3插入1和2之间.然后随意重新排列.

我需要在更改时在数据库中不断更新订单,以便我可以在开始时加载它.

我需要的操作:

1. 插入给定的索引
2. 在给定索引处删除
3. 从索引x移动到索引y(如果没有性能损失,可以表示为2和1的组合)

所有这些操作都将是频繁且同样重要的.

Answer 1

我假设"有效"你的意思是渐近有效.如果情况并非如此,那么澄清问题.

索引和任意插入的组合是一个棘手的问题.

• List<T>s - 它只是数组上的一个薄包装 - 在结尾处有O(1)插入/删除,在开头有O(n)插入/删除,以及O(1)索引.检查唯一性是O(n).
• 链接列表具有O(1)插入/删除,前提是您已知道要放置项目的位置,但O(n)索引以查找该位置.检查唯一性是O(n)
• 如果你聪明的话,平衡二叉树有O(lg n)插入和删除以及索引.检查唯一性是O(n).更多奇特的数据结构,如手指树,跳过列表等,是类似的.
• 散列集有O(1)插入和删除但没有索引; 检查唯一性是O(1).

没有适合您需求的单一数据结构.我的建议是:

1. 拥抱不变性.编写满足您需求的不可变数据结构.理由更容易.
2. 写一个平衡二叉树的组合 - 红黑,AVL等 - 和一个哈希集.哈希集仅用于唯一性检查.BBT在每个节点中都有低于它的项目数; 这有助于编制索引.插入和删除算法对于BBT来说是正常的,除了它们还重写树的主干以确保正确更新项目计数.

这将为您提供O(1)唯一性检查和O(lg n)索引,插入和删除.

我注意到这个数据结构为你提供了O(1)的问题答案"这个集合中的这个项目是什么？" 但O(n)回答了"它在哪里？"的问题.因此,如果您需要快速反向索引操作,那么您手上的问题就会大得多.