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

Ну, я думаю, что вопрос в значительной степени подводит итог. У меня есть forward_list уникальных элементов, и я хочу удалить из него один элемент:

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

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

Я имею в виду, что этот метод работает нормально, но он неэффективен, потому что он продолжает поиск, когда элемент найден и удален. Есть ли лучший способ или мне нужно сделать это вручную?

Источник

5 ответов

Решение

Если вы хотите удалить только первый матч, вы можете использовать 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) так что вы не получите его более эффективным, чем этот.

Источник

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;
}
Источник

Придется катиться самостоятельно...

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

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

Источник

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

Подобные вещи были стандартным упражнением, когда я изучал программирование еще в начале 80-х. Может быть интересно вспомнить решение и сравнить его с тем, что можно сделать в C++. На самом деле это было в Алголе 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 там; это последний, где это 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> нам не разрешен доступ к указателям, которые связывают узлы, и вместо этого получаем этих неуклюжих "итераторов, указывающих на один узел перед реальным действием". Наше решение становится

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).

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

Источник
Другие вопросы по тегам