使用谓词从列表中删除元素

Question

我有一个来自.NET集合库的列表，想要移除单个元素。不幸的是，我无法通过直接与另一个对象进行比较来找到它。

我担心使用FindIndex和RemoveAt会导致对列表进行多次遍历。

我不知道如何使用枚举器来删除元素，否则可能会行得通。 RemoveAll可以实现我需要的功能，但不会在找到一个元素后停止。

有什么建议吗？

- Steinbitglis

---

我以为List是一种链表？不是吗？ - Steinbitglis

@Steinbitglis：List<T>不是链表，它是一种动态数组。 - Ani

@Steinbitglis：不，它不是。它是基于数组的。 - Jon Skeet

澄清一下 - 您想删除第一个匹配项，即使有多个匹配项？ - Oded

我认为HashSet和Dictionary的常数因子会使这个问题变得更加严重。但是我正在研究LinkedList，因为这是我最初想到的东西。 - Steinbitglis

Answer 1

List<T>有一个接受谓词的FindIndex方法。

int index = words.FindIndex(s => s.StartsWith("x"));
if (index >= 0)
{
    words.RemoveAt(index);
}

移除以 "x" 开头的第一个单词。在这个示例中，假定 words 是一个 List<string>。

- Olivier Jacot-Descombes

---

如果列表具有常数时间的索引查找，我认为这将是可以的。我担心RemoveAt也会遍历列表。 - Steinbitglis

@Steinbitglis：这是一个O(n)的操作，因为它需要复制所有内容。你真的想要一个链表吗？ - Jon Skeet

我有很少的元素，它们来来去去。我认为至少使用哈希表会很愚蠢。除了这个看似微不足道的优化问题外，我没有看到链表存在任何问题。 - Steinbitglis

我切换到了LinkedList，希望我能获得类似Deque的操作，其中我主要检查1或2个元素。 - Steinbitglis

@Steinbitglis：如果你需要LinkedList，我会恢复我的答案，因为它已经包含了你需要的解决方案... - Jon Skeet

为了基于谓词查找项目，两种列表类型都需要进行列表遍历，这是一个O(n)操作。从特定索引处的List<T>中删除项目是O(n)，因为必须移动项目。从当前节点的LinkedList<T>中删除项目是O(1)操作。*(替换我删除的旧评论)*。 - Olivier Jacot-Descombes

Answer 2

如果您想仅删除与谓词匹配的第一个元素，可以使用以下方法（示例）：

List<int> list = new List<int>();
list.Remove(list.FirstOrDefault(x => x = 10));

其中(x => x = 10)显然是用于匹配对象的谓词。

- Strillo

---

这需要对列表进行两次枚举。一次是为了找到匹配的项，另一次是为了在“Remove”中再次找到该项。 - Olivier Jacot-Descombes

使用RemoveAt更高效。 - Strillo

如果FirstOrDefault返回null，我猜它会失败 - Chris

Answer 3

编辑：现在原帖已更改为使用 LinkedList<T>，因此可以轻松给出仅迭代到必要程度的答案：

public static void RemoveFirst<T>(LinkedList<T> list, Predicate<T> predicate)
{
    var node = list.First;
    while (node != null)
    {
        if (predicate(node.Value))
        {
            list.Remove(node);
            return;
        }
        node = node.Next;
    }
}

- Jon Skeet

---

我只想删除一个元素。 - Steinbitglis

@Steinbitglis：谓词是否有多个匹配值？您使用的是什么类型的列表？ - Jon Skeet

@Steinbitglis：编辑后展示了如何使用副作用来使用RemoveAll。 - Jon Skeet

这就是我最终寻找的解决方案，所以我将其标记为被接受的答案，无论它是否值得。 - Steinbitglis

如果它是最有帮助的答案，那么它绝对值得被接受。这就是“已接受”的含义。 - Olivier Jacot-Descombes

Answer 4

如果有人需要相同的东西，但是针对于 IList<T> （受 Strillo 回答启发，但更高效）

public bool Remove(this IList<T> list, Predicate<T> predicate)
{
    for(int i = 0; i < list.Count; i++)
    {
        if(predicate(list[i]))
        {
            list.RemoveAt(i);
            return true;
        }                   
    }   

    return false;
}

- tigrou