c++ - 在列表中，删除与删除相同吗？

Question

这是我要表达的两个示例。

第一个例子。

std::list<SomeClass*> somelist;
// we have defined a SomeClass m

1. 方法移除

   std::remove(somelist.begin(), somelist.end(), m);
   

2. 方法删除

   auto it = std::find(somelist.begin(), somelist.end(), m);
   if (it != somelist.end()) {
       somelist.erase(it);
   }
   

问题:在行为或表现上有什么不同吗？

---

第二个例子。

这就是问这个问题的实际目的，

std::list<SomeClass*> somelist;
SomeClass* m = nullptr;

使用第一个示例中的相同方法，使用这两种方法会有什么行为。

Answer 1

标准是这样说的:

• 删除:

  iterator erase(const_iterator position);
  iterator erase(const_iterator first, const_iterator last);
  

  Invalidates only the iterators and references to the erased elements.

• 删除:

  void remove(const T& value);
  template <class Predicate> void remove_if(Predicate pred);
  

  Erases all the elements in the list referred by a list iterator i for which the following conditions hold: *i == value, pred(*i) != false. Invalidates only the iterators and references to the erased elements.

如果您没有迭代器或几个迭代器可用于erase，并且您必须先重新排列元素，使用remove 可以是更好的选择。

请注意，remove 将删除所有与谓词匹配的元素，其复杂度为:

Exactly size() applications of the corresponding predicate

另一方面，find 的复杂度仍然是 O(N)，但它实际上会在找到第一个满足条件的出现时停止。
特别是，它的复杂性由标准定义为:

At most last - first applications of the corresponding predicate.

签名如下:

template<class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T& value);

行为上的差异:使用您的第一个提议删除与谓词匹配的所有元素，使用第二个提议仅(查找并)删除与谓词匹配的第一个元素。
性能差异:相同的复杂性，在最坏的情况下你不会有任何好处(好吧，在最好的情况下你会在大型容器上受益，因为如果 N 等于 100，则 O(N) 无关紧要)。

要回答你的最后一个问题，如果你想从列表中删除 nullptr 并且可能有多个，请使用 remove 而不是 查找/删除。