在 C++ 中从列表中删除元素

Question

我正在进行一项C++练习，尝试理解如何从列表中删除元素并将其余元素向左移动。我想知道是否有更好的解决方案。以下是我的版本，它似乎能够完成任务，但我有一种感觉还有更好的方法：

Account AccountList::remove(int i){
if(i>=0 && i<size()) {
    for (int n = i; n < size(); n++) {
        if(i+1!=size()) {
            aList[n]=aList[n+1];
        }
    }
    sz--;
    return aList[i];
} else {
    return Account();
}
}

- Au Ris

Answer 1

你在这里有两个问题。

1. 你没有返回已删除的元素，而是用下一个元素覆盖它并返回那个。我不认为这是你的意图。
2. 你的循环范围不正确。使用此循环，当n = size() - 1时，您将超出数组边界并使用索引n + 1。

以下是更正后的版本。

Account AccountList::remove(int i)
{
  if(i>=0 && i<size()) 
  {
    Account a = aList[i]
    for (int n = i; n < size() - 1; n++) 
    {
        if(i+1!=size()) 
        {
            aList[n]=aList[n+1];
        }
    }
    sz--;
    return a;
  } else 
  {
    return Account();
  }
}

- PermanentGuest

Answer 2

如果你这样做，那么你没有正确地实现列表。一个列表应该在删除元素时具有复杂度O(1)。那看起来更像是一个数组或向量。

一个列表通常由相互链接的节点组成，在这种情况下，你只需要删除相关的节点，并使前一个节点指向要删除的节点之后的节点即可。

- Luchian Grigore

---

一个列表不一定需要是链表。使用数组作为后端结构也是可以接受的。 - Isaiah van der Elst

即使假设“List”只能意味着链表（为什么？跳表或数组列表呢？），由于O(n)查找，链表对于任意元素的O(1)删除并不适用。 - Grizzly

@Grizzly 是的，但我假设您已经有了指向要删除节点的指针。在这种情况下，它将是 begin() + n。 - Luchian Grigore

@Luchian Grigore，那不正确。列表（通常是链表）的删除复杂度为O(n)，而不是O(1)。另一方面，数组的复杂度为O(1)。 - arahant

@IsaiahvanderElst 我指的是通常的C++列表实现。否则，它与数组有什么不同？ - Luchian Grigore

@arahant请看我对grizzly的评论的回复。 - Luchian Grigore