Как эффективно remove_if только один элемент из forward_list?

Ответ 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, ","));
}

Пример Live

Это прекратится, как только будет найдено совпадение. Обратите внимание, что adjacent_find принимает двоичный предикат, и, сравнивая только второй аргумент, мы получаем итератор перед элементом, который хотим удалить, так что erase_after может фактически удалить его. Сложность O(N), поэтому вы не получите ее более эффективной, чем это.

Ответ 2

FWIW, здесь еще одна короткая версия

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

В стандартной библиотеке нет ничего, что было бы непосредственно применимо. Собственно, есть. См. Ответ @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;
}

Ответ 4

Приходится рулон...

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

Более полный пример...

Ответ 5

Этот вид вещей был стандартным упражнением, когда я изучил программирование еще в начале 80-х. Было бы интересно вспомнить решение и сравнить его с тем, что можно сделать на С++. На самом деле это было в Алголе 68, но я не буду навязывать это вам и давать перевод на C. Учитывая

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

можно написать, понимая, что нужно передать адрес указателя заголовка списка, если можно отменить связь с первым 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 */
  }
}

Здесь много событий *p_addr; он является последним, где это LHS присвоения, именно по этой причине нужен адрес указателя здесь, в первую очередь. Обратите внимание: несмотря на кажущееся усложнение, оператор p_addr = &(*p_addr)->next; просто заменяет указатель на значение, на которое указывает он, а затем добавляет смещение (которое здесь 0).

Можно ввести вспомогательное значение указателя, чтобы немного уменьшить код, как показано ниже.

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> нам не разрешен доступ к указателям, которые связывают узлы, и получают эти неудобные "итераторы", указывающие один node перед реальным действием ". Наше решение становится

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) и получаем по существу ответ Дэниела Фрея. (Мы могли бы вместо этого попытаться сделать эту переменную указателем типа *T равным &*std::next(it) вместо этого, что достаточно для использования, которое мы делаем из нее, но на самом деле было бы немного хлопот, чтобы он стал нулевым указателем когда std::next(it)==NIL, так как стандарт не позволяет взять &*NIL).

Я не могу не почувствовать, что с давних времен решение этой проблемы не стало более элегантным.