В C ++ удаление объекта из списка - PullRequest
Новая
       13

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

1 голос
/ 20 октября 2010

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

#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 ]

5 голосов
/ 20 октября 2010

За последние 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());

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

2 голосов
/ 20 октября 2010

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

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

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

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

0 голосов
/ 20 октября 2010

Функция 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; }
0 голосов
/ 20 октября 2010

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

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 должен быть вызван.Это очень важный идиома, erase-remove idiom , который необходимо выучить. 

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

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

...