在 List<T> 中删除交替元素

Question

如何在不使用占位列表变量的情况下，最有效地删除一个List<T>中的交替元素(奇数索引或偶数索引)？

如果您能在每个答案中提到成本，将不胜感激。

我正在寻找一种高效的方法来完成这个操作。

谢谢！

- AB Kolan

---

“Alternate” 在编程中的确切含义是什么？ - Mehrdad Afshari

你的意思是要删除每个元素中的另一个元素，即所有偶数索引或所有奇数索引的元素吗？ - R. Martinho Fernandes

是的，偶数索引或奇数索引元素。 - abhilash

大家（尤其是那些声望较高的人），我们应该训练自己去点赞这样的问题。如果这个问题足够有趣，让我们花时间参与，难道不值得一票吗？ - AnthonyWJones

@AnthonyWJones，当问题更清晰时，我点了一次赞同。 - JaredPar

Answer 1

如果你对每个要移除的项都调用RemoveAt，那么你将会移动大量的数据。最高效的方法是将要保留的项目一起移动，然后在结尾处移除未使用的项目：

int pos = 0;
for (int i = 0; i < values.Count; i += 2, pos++) {
    values[pos] = values[i];
}
values.RemoveRange(pos, values.Count - pos);

编辑：
使用此方法可以在15毫秒内处理100万个整数的列表。如果使用RemoveAt，则需要超过三分钟...

编辑2：
实际上，您可以从pos=1和i=2（或3）开始，因为第一个项目不必被复制到自身。但这使得代码有点不太明显。

- Guffa

---

我认为只有列表中元素的数量是偶数时，这才能正常工作。 - tvanfosson

啊，我明白了。复制你想要保存的元素，如果最后还有一个你没有迭代过的额外元素，那么它必须是你想要删除的元素。很好。 - tvanfosson

从列表中删除一个元素保证是O(1)。因此，删除元素的顺序是不重要的。 - Martin York

是的，它确实有一个索引器：http://msdn.microsoft.com/en-us/library/0ebtbkkc.aspx 不，RemoveAt方法是一个为O(n)操作：http://msdn.microsoft.com/en-us/library/5cw9x18z.aspx - Guffa

@Martin，不幸的是，它不是O(1)，因为删除会导致数组中元素的移动。这种移动可能非常昂贵：http://blogs.msdn.com/jaredpar/archive/2008/04/07/binaryinsert-part2.aspx - JaredPar

Answer 2

考虑一种创建新列表的解决方案，可以使用一个旧列表 old 来实现：

var newList = old.Where((_, i) => i%2 != 0).ToList();

或者，显然

var newList = l.Where((_, i) => i%2 == 0).ToList();

根据你选择的替代方案而定。

编辑

答案相当快。如果你在这里读到其他内容，那是因为我在周末测量，周末的大脑很有趣。 :( 闭包解决方案约快40%，而答案要快大约2个数量级。我想这真的取决于你的列表变得有多大！

- Frank

---

不确定你是不是在讽刺？这绝对是 C# 代码，我在发布之前试过了。坦率地说，考虑到这是所有答案中最简单的一个，我有点惊讶为什么没有得到更多的赞。 - flq

这段代码并没有满足任何主题帖的需求。他想要从列表中删除元素，而这段代码并没有实现。他想要高性能，而这段代码也无法提供。 - Hosam Aly

这个很简单，而且迭代器通常正是你所需要的。 - rjh

@Frank，我曾经认为在C#中_是非法标识符，因为C#要求至少有一个字母字符。每天都会学到新东西。 - JaredPar

该OP特别要求不使用占位符列表的解决方案。 - Guffa

这个解决方案真的非常理想。稍微改进一下，可能会是list = list.Where((_, i) => i%2 != 0).ToList();。由于GC中的所有优化，对旧列表及其所有未包含的项目的引用都被清除了。很难比这更好了。 - andleer

Answer 3

另一个选项与Frank的类似，但使用闭包。而且它比Frank的版本更快。

bool isEven = true;            
var newList = list.Where(x => isEven = !isEven).ToList();

- Matajon

Answer 4

我不确定你所说的“alternate”是什么意思，但如果你的意思是“每隔一项”，则以下代码可以实现。它将从删除第二个元素开始，然后删除第四个元素，以此类推。

List<T> list = GetTheList();
int i = 1;
while ( i < list.Count ) {
  list.RemoveAt(i);
  i++;
}

- JaredPar

---

当你从开头删除一个元素时，所有剩余的元素都会向下移动一个。这肯定不会消除交替元素，并且可能会导致异常，具体取决于是否在每一步重新计算保护条件，即列表计数将发生变化。 - tvanfosson

它确实可以工作，但效率非常低下。要处理一个包含1000个整数的列表，你需要移动接近1MB的数据... - Guffa

@tvanfosson：代码似乎依赖于您所描述的解决方案的行为。请注意，i只增加1次迭代，在与您描述的位置移动结合使用时，它只会删除每隔一个项目，正如预期的那样。 - AnthonyWJones

我使用了.NET Reflector来检查实现。RemoveAt方法使用Array.Copy来移动内部数组中的数据。 - Guffa

@Guffa，List<T>的所有方法都有可能使用这个方法。 - JaredPar

Answer 5

通向涅槃之路铺满了延迟执行。或者说什么的。

    public static IEnumerable<T> AlternateItems<T>(this IEnumerable<T> source)
    {
        while (source.Any())
        {
            yield return source.First();

            source = source.Skip(1);

            if (source.Any()) source = source.Skip(1);                
        }
    }

这适用于所有序列，不仅限于。迭代的成本要推迟到迭代时才计算，如果最终你不需要访问列表中的所有元素，则这可能是一个巨大的优势。

在我的简单测试中，当你迭代整个列表时，性能并不是很好，所以一定要对实际情况进行分析。

- Jay Bazuzi

Answer 6

for (int i=myList.length-1; i >= 0; i--)
  if (i % 2 == 0)
    myList.Remove(myList[i]);

- tsilb

Answer 7

显然是根据使用情况而定，但您可以拥有一个包装器IList，它将您提供的索引乘以2，并报告列表的长度为1/2（详细信息被省略）。这是O（1）。

- wowest

Answer 8

我会使用STL容器通常使用的标准模式。 先做删除，然后再进行擦除。

这样做可以避免让习惯于查看此模式的人感到困惑。

template<typename T>
struct RemoveEven
{
    RemoveEven():count(0)   {}
    bool operator()(T const&)
    {
        bool    result  =  count%2 == 0;
        count++;
        return result;
    }
    private:
        std::size_t count;
};
int main()
{
    std::list<int>  a;
    a.erase(std::remove_if(a.begin(),a.end(),RemoveEven<int>()),a.end());

}

- Martin York