如何高效地从forward_list中移除单个元素？

Question

我认为问题已经很清楚了。我有一个唯一项目的单向链表(forward_list)，想要从中删除一个项目：

std::forward_list<T> mylist;
// fill with stuff

mylist.remove_if([](T const& value)
  {
    return value == condition;
  });

我的意思是，这种方法虽然有效，但效率不高，因为一旦找到并删除该项，它仍会继续搜索。有更好的方法吗？还是我需要手动完成？

- quant

---

你可以在lambda表达式中简单地写成return value == condition;。 - Geoffroy

@Geoffroy 是的，你说得对，我只是这样做是为了能够添加那个“如果发生这种情况就退出”的语句，以澄清我的意图。 - quant

你需要一个类似于remove_first的功能，但是没有这样的内置函数。为什么不自己写一个呢？这很简单。 - Ivaylo Strandjev

std::find_first_of - P0W

@P0W adjacent_find 后跟 erase_after 就可以解决问题了，详见我的回答。 - TemplateRex

Answer 1

如果你只想移除第一个匹配的内容，可以使用std::adjacent_find函数，并在之后使用erase_after成员函数。

#include <algorithm>
#include <cassert>
#include <forward_list>
#include <iostream>
#include <ios>
#include <iterator>

// returns an iterator before first element equal to value, or last if no such element is present
// pre-condition: before_first is incrementable and not equal to last
template<class FwdIt, class T>
FwdIt find_before(FwdIt before_first, FwdIt last, T const& value)
{
    assert(before_first != last);
    auto first = std::next(before_first);
    if (first == last) return last;
    if (*first == value) return before_first;
    return std::adjacent_find(first, last, [&](auto const&, auto const& R) { 
        return R == value; 
    });
}

int main() 
{
    auto e = std::forward_list<int>{};
    std::cout << std::boolalpha << (++e.before_begin() == end(e)) << "\n";
    std::cout << (find_before(e.before_begin(), end(e), 0) == end(e)) << "\n";

    auto s = std::forward_list<int>{ 0 };
    std::cout << (find_before(s.before_begin(), end(s), 0) == s.before_begin()) << "\n";

    auto d = std::forward_list<int>{ 0, 1 };
    std::cout << (find_before(d.before_begin(), end(d), 0) == d.before_begin()) << "\n";
    std::cout << (find_before(d.before_begin(), end(d), 1) == begin(d)) << "\n";
    std::cout << (find_before(d.before_begin(), end(d), 2) == end(d)) << "\n";

    // erase after
    auto m = std::forward_list<int>{ 1, 2, 3, 4, 1, 3, 5 };
    auto it = find_before(m.before_begin(), end(m), 3);
    if (it != end(m)) 
        m.erase_after(it);
    std::copy(begin(m), end(m), std::ostream_iterator<int>(std::cout, ","));
}

实时示例

一旦找到匹配项，它将停止。请注意，adjacent_find需要一个二进制谓词，并且通过仅比较第二个参数，我们可以得到要删除的元素之前的迭代器，以便erase_after可以实际删除它。复杂度为O(N)，因此您不会比这更有效率。

- TemplateRex

---

很好地使用了adjacent_find函数（我甚至不知道这个函数存在）。点赞👍 - Angew is no longer proud of SO

@Angew 我以前用过它，但几天前我也在 std-proposals 论坛上读到了关于它的内容，其中它被用来展示一个序列是严格递增的，使用 <（而不是 <=，就像 std::is_sorted 一样）。所以它在工作记忆中还比较“新鲜”。 - TemplateRex

等一下，你在实际上篡改adjacent_find以达到你想要的效果时，却在给其他答案投反对票？这很新奇... - Nim

@Nim 标准规定 erase_after 函数：“要求：位置后面的迭代器是可解引用的”。空列表具有 begin() == end()，解引用 end()（或任何无效）迭代器会导致未定义行为。 - TemplateRex

@Nim 顺便说一下，我不认为这是对 adjacent_find 的黑客攻击。前向迭代器天生就适合被 adjacent_find 处理，因为你真的需要一直进行一个向前看一步的操作，因为你不能以 O(1) 的时间复杂度向后查找。 - TemplateRex

Answer 2

顺便说一下，这是另一个简短的版本

template< typename T, class Allocator, class Predicate >
bool remove_first_if( std::forward_list< T, Allocator >& list, Predicate pred )
{
    auto oit = list.before_begin(), it = std::next( oit );
    while( it != list.end() ) {
        if( pred( *it ) ) { list.erase_after( oit ); return true; }
        oit = it++;
    }
    return false;
}

- Daniel Frey

---

好的解决方案+1。我可能会将it=list.begin()作为初始化更明确一些，然后在循环结束时加上 oit=it,++it;，但这显然与您编写的代码等效。 - Marc van Leeuwen

Answer 3

你需要自己动手...

template <typename Container, typename Predicate>
void remove_first_of(Container& container, Predicate p)
{
  auto it = container.before_begin();
  for (auto nit = std::next(it); ; it = nit, nit = std::next(it))
  {
    if (nit == container.end())
      return;
    if (p(*nit))
    {
      container.erase_after(it);
      return;
    }
  }
}

一个更完整的示例...

- Nim

---

@TemplateRex，这是针对特定容器的专用算法，OP可以根据需要更改容器类型。但是，在这里，begin不是标准的开头，因此接受简单范围可能会令人困惑。此外，不要忘记erase_after！ - Nim

我不明白为什么你不把 nit != container.end() 放在 for 循环的第二个语句中，而是放在 for 块的开头进行测试。但这似乎是最好的答案。 - kingsjester

Answer 4

标准库中没有直接适用的内容。实际上有。请查看@TemplateRex的答案。

如果您想将搜索与删除结合起来，也可以自己编写，类似于以下内容：

template <class T, class Allocator, class Predicate>
bool remove_first_if(std::forward_list<T, Allocator> &list, Predicate pred)
{
  auto itErase = list.before_begin();
  auto itFind = list.begin();
  const auto itEnd = list.end();
  while (itFind != itEnd) {
    if (pred(*itFind)) {
      list.erase_after(itErase);
      return true;
    } else {
      ++itErase;
      ++itFind;
    }
  }
  return false;
}

- Angew is no longer proud of SO

---

@TemplateRex 这是一个特殊容器的特殊算法。它只是一个方便的包装器，结合了搜索和erase_after。我已经反映了您使用纯std解决方案的答案，但如果您发现自己一遍又一遍地执行erase_before(find_before_first())，那么您可能也想将此组合封装在一个函数中。 - Angew is no longer proud of SO

@TemplateRex 如果您想要将erase_after()调用一起封装，那么您必须传递容器。是的，这个函数可以在内部调用您的find_before_first()（这样会更短），但是它仍然可能有存在的有效原因。 - Angew is no longer proud of SO

好的，如果您可以进行一次标记编辑，我会取消点赞。不过，erase_after / find_first_before 的代码很短，足够简洁，我不会将其包装起来。但我能理解您的观点，您可能想这样做，尽管我更愿意在存在“erase_after”成员的情况下对其进行SFINAE处理，而不是将“forward_list”硬编码为参数;-) - TemplateRex

@TemplateRex 已完成，谢谢。现在 OP 有三种选择：使用您的 std 库、Nim 的通用容器和我的 forward_list。我认为这是一个不错的结果 :-) - Angew is no longer proud of SO

@TemplateRex，即使它不使用值，before_begin()可以被解引用吗？ - abir

Answer 5

当我在80年代初学习编程时，这种事情曾经是标准的练习。回忆解决方案并将其与C++进行比较可能很有趣。实际上，那时使用的是Algol 68，但我不会强制让您使用Algol 68，而是给出C语言的翻译。给定：

typedef ... T;
typedef struct node *link;
struct node { link next; T data; };

如果想要删除第一个节点，就需要传递列表头指针的地址，因此可以写成：

void search_and_destroy(link *p_addr, T y)
{
  while (*p_addr!=NULL && (*p_addr)->data!=y)
    p_addr = &(*p_addr)->next;
  if (*p_addr!=NULL)
  {
    link old = *p_addr;
    *p_addr = old->next; /* unlink node */
    free(old); /* and free memory */
  }
}

这里有很多关于*p_addr的出现；它最后一次出现时是一个赋值语句的左值，这也是为什么首先需要指针地址的原因。请注意，尽管看起来很复杂，语句p_addr = &(*p_addr)->next;只是用指针替换它所指向的值，然后添加一个偏移量（这里是0）。

可以引入一个辅助指针value来简化代码，如下所示：

void search_and_destroy(link *p_addr, T y)
{
  link p=*p_addr;
  while (p!=NULL && p->data!=y)
    p=*(p_addr = &p->next);
  if (p!=NULL)
  {
    *p_addr = p->next;
    free(p);
  }
}

但这基本上是相同的代码：任何好的编译器都应该意识到指针值*p_addr在第一个示例中连续使用多次，并将其保存在寄存器中。

现在使用std::forward_list<T>，我们不允许访问链接节点的指针，而是得到那些笨拙的“迭代器指向真正操作之前的一个节点”。我们的解决方案变成了：

void search_and_destroy(std::forward_list<T> list, T y)
{
  std::forward_list<T>::iterator it = list.before_begin();
  const std::forward_list<T>::iterator NIL = list.end();

  while (std::next(it)!=NIL && *std::next(it)!=y)
    ++it;
  if (std::next(it)!=NIL)
    list.erase_after(it);
}

再次，我们可以保留第二个迭代器变量来保存std::next(it)，而不必每次都拼写它（不要忘记在增加it时刷新其值），从而基本上得到Daniel Frey的答案。（我们也可以尝试将该变量作为指向类型*T的指针等于&*std::next(it)，这对我们所做的使用足够了，但实际上确保它在std::next(it)==NIL时成为空指针有点麻烦，因为标准不允许我们取&*NIL）。

我不能不感觉自从早期以来，这个问题的解决方案并没有变得更加优雅。

- Marc van Leeuwen