How do I efficiently remove_if only a single eleme

问题:

Well I think the question pretty much sums it up. I have a forward_list of unique items, and want to remove a single item from it:

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

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

I mean, this method works fine but it's inefficient because it continues to search once the item is found and deleted. Is there a better way or do I need to do it manually?

回答1:

If you only want to remove the first match, you can use std::adjacent_find followed by the member 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, ","));
}

Live Example

This will stop as soon as a match is found. Note that the adjacent_find takes a binary predicate, and by comparing only the second argument, we get an iterator before the element we want to remove, so that erase_after can actually remove it. Complexity is O(N) so you won't get it more efficient than this.

回答2:

FWIW, here's another short version

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;
}

回答3:

Going to have to roll your own...

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;
    }
  }
}

A more complete example...

回答4:

There is nothing in the standard library which would be directly applicable. Actually, there is. See @TemplateRex's answer for that.

You can also write this yourself (especially if you want to combine the search with the erasure), something like this:

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;
}

回答5:

This kind of stuff used to be a standard exercise when I learned programming way back in the early '80s. It might be interesting to to recall the solution, and compare that with what one can do in C++. Actually that was in Algol 68, but I won't impose that on you and give the translation into C. Given

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

one could write, realising that one needs to pass the address of the list head pointer if is to be possible to unlink the first node:

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 */
  }
}

There are a lot of occurrences of *p_addr there; it is the last one, where it is the LHS of an assignment, that is the reason one needs the address of a pointer here in the first place. Note that in spite of the apparent complication, the statement p_addr = &(*p_addr)->next; is just replacing a pointer by the value it points to, and then adding an offset (which is 0 here).

One could introduce an auxiliary pointer value to lighten the code a bit up, as follows

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);
  }
}

but that is fundamentally the same code: any decent compiler should realise that the pointer value *p_addr is used multiple times in succession in the first example, and keep it in a register.

Now with std::forward_list<T>, we are not allowed access to the pointers that link the nodes, and get those awkward "iterators pointing one node before the real action" instead. Our solution becomes

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);
}

Again we could keep a second iterator variable to hold std::next(it) without having to spell it out each time (not forgetting to refresh its value when we increment it) and arrive at essentially the answer by Daniel Frey. (We could instead try to make that variable a pointer of type *T equal to &*std::next(it) instead, which suffices for the use we make of it, but it would actually be a bit of a hassle to ensure it becomes the null pointer when std::next(it)==NIL, as the standard will not let us take &*NIL).

I cannot help feel that since the old days the solution to this problem has not become more elegant.