В C++ удаление объекта из списка

Я пишу программу, которая более или менее похожа на это:

#include <list>

list<MyClass> things;

class MyClass {
   // some stuff

   void remove() {
       things.remove_if(THING_IS_ME);
   }
};

Что мне нужно написать вместо THING_IS_ME?

Другими словами, я использую глобальный список STL как набор вещей. В какой-то момент объект, который находится в списке, распознает, что он является избыточным, и хочет а) удалить себя из списка и б) уничтожить себя.

Как мне это сделать?

Я не писал C++ около 15 лет, и меня немного смущает эта страница здесь: http://www.cplusplus.com/reference/algorithm/remove_if/

Что это за предикаты? Есть ли в C++ функции высшего порядка сейчас?

Источник

4 ответа

Решение

(Первоначально набор комментариев, но переписанный как ответ после обнаружения того, что ОП действительно хотел сделать.)

Вы понимаете, что контейнеры STL хранят копии того, что вы вставили, верно? Это означает, что случаи MyClass лучше быть сопоставимым (например, через operator==) - вы не можете просто сравнить адреса, так как они всегда будут разными.

Если иметь копии MyClass не имеет смысла, то вам, вероятно, лучше использовать контейнер с указателями.

При этом язык C++ по умолчанию использует семантику копирования. Язык требует, чтобы вы делали такие вещи, как ссылки, явными в коде. Я настоятельно рекомендую вам взять хорошую книгу по C++, иначе в будущем у вас возникнут подобные проблемы.

Источник

За последние 15 лет в C++ все сильно изменилось. В июле 1994 года предложение Александра Степанова о библиотеке, включающей его идеи общего программирования, получило окончательное одобрение комитета ANSI/ISO. Эта библиотека, которую мы обычно называем сегодня STL, впоследствии стала стандартной библиотекой C++. История STL столь же увлекательна, как и идеи, стоящие за ней, и она определенно стоит того, чтобы ее прочитать.

std::remove_if() Функция, которую вы нашли, является еще одним отражением этой философии, которая стала частью современной идентичности C++. Короче говоря, это универсальная функция, которая будет работать с любым контейнером (последовательностью) элементов и с любым (действующим как) условием. Для этого вы должны предоставить функции две вещи:

  1. пара итераторов, которые разграничивают диапазон элементов, над которыми вы хотите работать;
  2. и предикат, который при вызове элемента возвращает true, если элемент должен быть удален, и false в противном случае.

Оказывается, в этом случае вы хотите предикат равенства. И поскольку удаление элементов, основанных на равенстве, является такой распространенной задачей, стандарт также обеспечивает std::remove() функция, которая предполагает неявный предикат равенства. Конечно, вы должны убедиться, что элементы могут сравниваться:

bool operator==(const MyClass& a, const MyClass& b)
{
    // return true if the two are equal, and false otherwise.
}

Затем мы можем использовать наш предикат для удаления элементов типа MyClass:

std::remove(things.begin(), things.end(), *this);  // if *this == elem

Напомним, что стандартная функция std::remove() работает с любым контейнером, даже с теми, которые еще не были созданы. Поскольку каждый вид контейнера имеет свой собственный способ удаления элементов, эта функция не может действительно выполнить удаление, не зная деталей реализации контейнера, в котором она работает. Так что вместо std::remove() Функция меняет элементы так, что элементы "удалены" находятся в конце контейнера. Затем он возвращает итератор, указывающий на первый элемент последовательных "удаленных" элементов.

typedef std::list<MyClass>::iterator iter;
iter first_removed = std::remove(things.begin(), things.end(), *this);

Наконец, мы действительно удаляем элементы, вызывая функцию удаления конкретного контейнера, которая работает на одной позиции в списке или на ряде последовательных элементов для удаления:

things.erase(first_removed, things.end());

Весьма часто можно увидеть код такого рода в одной строке:

things.erase(std::remove(things.begin(), things.end(), *this),
             things.end());

Все это может показаться ошеломляющим и сложным, но у него есть несколько преимуществ. С одной стороны, этот дизайн стандартной библиотеки поддерживает динамическое программирование. Это также позволяет стандартной библиотеке предлагать контейнеры с очень тонкими интерфейсами, а также несколько бесплатных функций, которые работают с различными типами контейнеров. Это позволяет быстро создать контейнер и мгновенно получить все возможности стандартной библиотеки для работы с ним. Кроме того, он позволяет быстро написать универсальную функцию, которая мгновенно работает со всеми стандартными контейнерами - уже написанными и еще не написанными.

Источник

remove_if Функция принимает три параметра: два итератора, которые определяют диапазон, над которым вы работаете, и предикат (тестовая функция, которая возвращает bool). Стартовый итератор указывает на первый элемент, с которым вы хотите работать; конечный итератор указывает на элемент после последнего элемента в диапазоне.

В примере со страницы, на которую вы ссылаетесь, предикатом является строка кода, которая говорит

bool IsOdd (int i) { return ((i%2)==1); }

Чтобы ваш код делал то, что вы хотите, вам нужно написать что-то вроде этого:

things.remove_if(things.begin(), things.end(), SomePredicateFunction);

и вы бы определить SomePredicateFunction вот так (замена true с соответствующим тестом):

bool SomePredicateFunction (MyClass c) { return true; }
Источник

Во-первых, простой рукописный цикл:

for( list<MyClass>::iterator it = things.begin(); it != things.end(); /*  */ ) {
    if( qualifiesForDelete( *it ) ) {
        it = things.erase( it );
    }
    else {
        ++it;
    }
}

Во-вторых, используя remove_if алгоритм. remove_if будучи алгоритмом, в отличие от функции-члена list, не может на самом деле удалить какие-либо элементы, скорее он перемещает элементы, которые должны быть удалены, к концу списка. впоследствии erase должен быть вызван. Это очень важная идиома, идиома стирания-удаления, которую нужно выучить.

things.erase( 
    remove_if( things.begin(), things.end(), deletionPredicate ), 
    things.end() 
);

где deletionPredicate это функция или объект-функция, которая принимает один аргумент типа и возвращает bool, Элементы для которых true возвращается считается удаленным.

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