没有重复或有序集的列表 [英] A list with no duplicates or an ordered set

问题描述

是否有一个提供数据结构的库，它保留了项目的顺序并且不包含任何重复项？那么这样的数据结构是否存在一个合适的名称？

我认为它的行为就像在每次操作后应用 nub 的列表。

解决方案

这里有一个解决方案：

使用 fingertree 与 Set monoid作为你的度量。然后插入，首先检查成员身份，使用完整fingertree的 measure 。这给你 O（log（n）） cons和snoc， O（1）删除。

以下是另一个解决方案：

将常规列表与普通 Set 并获得基本相同的效果。你会得到更好的常数因子，但是 O（log（n））删除。

下面是一个问题：你想插入一个重复？现有的立场应该保留吗？新的职位？优先队列可能接近你想要的，取决于。

Is there a library which provides a data structure, which preserves the order of items and does not contain any duplicates? And does there exist a proper name for such a data structure?

I expect it to behave like a list with nub applied after each operation on it. Of course I don't expect it to be implemented as ineffectively.

解决方案

Here's one solution:

Use a fingertree with the Set monoid as your measure. Then on inserts, check membership first, using the measure of your full fingertree. This gives you O(log(n)) cons and snoc, O(1) deletes.

Here's another solution:

Pair a normal list with a normal Set and get basically the same effect. You get better constant factors, but O(log(n)) deletes.

Here's a question: What do you want to happen on insert of a duplicate? Should the existing position be preserved? The new position? Priority Queues may be close to what you want, depending.

这篇关于没有重复或有序集的列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！