从集合中获取和删除元素

Question

最有效的方法是从集合中移除n个元素并将这些已移除的元素添加到另一个已存在的集合中，这两个集合不同。

目前我有以下代码：

var entries = collection.Take(5).ToList();
foreach(var entry in entries)
    collection.Remove(entry);
otherCollection.AddRange(entries);

然而，对我来说，这看起来并不高效（多个线性算法而不是只有一个）。

一种可能的解决方案当然可以改变集合实现方式-只要满足以下要求：

• otherCollection 必须实现 IEnumerable<T>，当前为 List<T> 类型。
• collection 必须实现 ICollection<T>，当前为 LinkedList<T> 类型。

提示：条目不一定实现 Equals() 或 GetHashCode()。

最有效的方法是什么？

---

由于我的性能考虑显然太难理解了，所以这里再次展示我的代码示例：

var entries = collection.Take(1000).ToList(); // 1000 steps
foreach(var entry in entries) // 1000 * 1 steps (as Remove finds the element always immediately at the beginning)
    collection.Remove(entry);
otherCollection.AddRange(entries); // another 1000 steps

总共有3000个步骤 => 我想将其减少为1000个步骤。

- D.R.

---

在集合中，你总是需要使用 O(n) 操作的线性搜索，没有比这更好的方法。 - Tim Schmelter

我认为这个集合有一个 RemoveAll(collection.Take(5))。 - Jeroen van Langen

@spender：请随意编辑我的帖子，英语不是我的母语。 - D.R.

@D.R. 我认为没有办法避免执行多个O(n)操作。IEnumerable<T>上的扩展方法是有意设计成这样的。 - evanmcdonnal

@JeroenvanLangen：即使如此，也必须搜索整个集合以查看哪些元素与给定谓词匹配。这只是更优雅，没有更多，也没有更少。 - Tim Schmelter

Answer 1

之前的函数只返回了一半结果。应该使用以下代码：

public static IEnumerable<T> TakeAndRemove<T>(Queue<T> queue, int count)
{
   for (int i = 0; i < count && queue.Count > 0; i++)
      yield return queue.Dequeue();
}

- XSBen

Answer 2

根据您的使用情况，最好的数据结构似乎是队列。使用队列时，您的方法可以如下所示：

public static IEnumerable<T> TakeAndRemove<T>(Queue<T> queue, int count)
{
   count = Math.Min(queue.Count, count);
   for (int i = 0; i < count; i++)
      yield return queue.Dequeue();
}

- chrischu