Как эффективно удалить только один элемент из списка forward_list?
Ну, я думаю, что вопрос в значительной степени подводит итог. У меня есть forward_list уникальных элементов, и я хочу удалить из него один элемент:
std::forward_list<T> mylist;
// fill with stuff
mylist.remove_if([](T const& value)
{
return value == condition;
});
Я имею в виду, что этот метод работает нормально, но он неэффективен, потому что он продолжает поиск, когда элемент найден и удален. Есть ли лучший способ или мне нужно сделать это вручную?
Решение
Если вы хотите удалить только первый матч, вы можете использовать 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).
Я не могу не чувствовать, что с давних времен решение этой проблемы не стало более элегантным.