1

Ребят, такое дело. Вроде бы задание элементарное, но я все не могу дать ему ума.

Само задание:

template<typename FwdIt, typename Pred>
FwdIt remove_if(FwdIt first, FwdIt last, Pred pr);

Нужно написать алгоритм, который удаляет из диапазона [first , last) все элементы, для которых значение предиката pr равно true. Удаленные элементы сдвигаются в конец контейнера. Возвращает итератор на первый удаленный элемент.

Ведь итератор это указатель на элемент контейнера, и вот как через него удалять элементы? Подскажите, пожалуйста. Спасибо.

1
  • 2
    Трюк здесь в том, что std::remove_if ничего не удаляет, а просто переставляет элементы. Если не хотите ломать голову самостоятельно, то ключевые слова — remove_if и cppreference. Commented 18 нояб. 2013 в 20:47

2 ответа 2

4

Эх, так вопрос и не получил канонического ответа.

Вы должны на самом деле воспользоваться идиомой erase/remove.

Код того, как надо делать, можно найти на cppreference:

std::string str = "Text\n with\tsome \t  whitespaces\n\n";
str.erase(std::remove_if(str.begin(), 
                         str.end(),
                         [](char x){return std::isspace(x);}),
          str.end());

std::remove_if перемещает ненужные элементы в конец, и возвращает итератор на первый из них. Так что удалять надо от этого итератора и до конца. Именно это и делает remove.

Для чего всё так сложно? Дело в том, что remove_if не знает ни о контейнере, ни о том, как удалить элемент по итератору. Поэтому он может лишь перемещать элементы.

Некоторые контейнеры (например, set/map), не могут быть использованы таким образом, поскольку в них менять элемент по итератору запрещено, и remove не скомпилируется. Для них можно использовать такую конструкцию:

std::set<int> s = {1, 2, 3, 4, 5, 6, 7, 8, 9};
for (auto it = s.begin(); it != s.end(); /**/)
{
    if (<condition>)
        it = s.erase(it);
    else
        ++it;
}

Для других типов (например, list) идиома erase/remove слишком неэффективна, и для них стоит пользоваться их собственной имплементацией remove_if.

5
  • Сейчас столкнулся с этим явлением, и как выяснилось std::remove_if(...); может вернуть end() - невалидный итератор. что при передаче в <CONTAINER>::erase приведет к неопределенному поведению. К примеру у меня на MSVC2015 x64 приводило к access_violation. Однако на x86 или arm-gcc 4.8 или gcc7 x86|64 ошибки не возникало. В общем отследить удалось только из-за большого количества платформ. Будьте внимательны.
    – JK_Action
    Commented 13 февр. 2020 в 8:47
  • @JK_Action: а можно воспроизводящий пример? Документация говорит, что erase(end, end) должен нормально работать.
    – VladD
    Commented 14 февр. 2020 в 7:09
  • я тут немного ошибся я имел ввиду конструкцию erase(it) и конкретно в моеv случае был std::deque
    – JK_Action
    Commented 14 февр. 2020 в 7:36
  • cpp.sh/5yvl7
    – JK_Action
    Commented 14 февр. 2020 в 7:49
  • @JK_Action: А, это да, в идиоме erase/remove нужно пользоваться erase с двумя аргументами, иначе проблем не избежать (в случае, когда remove_if находит не 1 результат, а больше или меньше).
    – VladD
    Commented 16 февр. 2020 в 14:26
2
  1. читаем справку по С++ RU, EN
  2. постигаем разницу между Sequence и Associative containers тык и незабываем подумать...
  3. собственно как удалить что то из контейнера set, map, vector

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.