Как удалить элемент из set c

Как удалить элемент из set c

Подскажите, есть объект std::set с элементами целого типа. В цикле проходиться и удаляется какой либо элемент по некоторому условию. При этом итератор становиться недействительным. Как после удаления переместить итератор на следующий элемент после удаленного?

Re: Удаление в цикле, std::set

От:	Bell
Дата:	19.07.10 08:57
Оценка:	+2

Здравствуйте, Аноним, Вы писали:

А>Подскажите, есть объект std::set с элементами целого типа. В цикле проходиться и удаляется какой либо элемент по некоторому условию. При этом итератор становиться недействительным. Как после удаления переместить итератор на следующий элемент после удаленного?

for(MySet::iterator i = s.begin(), e = s.end(); i != e; /*пусто . */ ) < if ( . . . ) s.erase(i++); else ++i; >

Любите книгу — источник знаний (с) М.Горький
Re: Удаление в цикле, std::set

От:	_niko_
Дата:	19.07.10 09:33
Оценка:

Здравствуйте, Аноним, Вы писали:

А>Подскажите, есть объект std::set с элементами целого типа. В цикле проходиться и удаляется какой либо элемент по некоторому условию. При этом итератор становиться недействительным. Как после удаления переместить итератор на следующий элемент после удаленного?

Лучше делать выборку в отдельное множество и с последующим вызовом метода swap

 std::setint> s; // Исходное множество std::setint> tmp; std::setint>::iterator it = s.begin(); std::setint>::iterator it_end = s.end(); for (; it != it_end; ++it) < if (/* условие */) < tmp.insert(*it); >> s.swap(tmp);

Re[2]: Удаление в цикле, std::set

От:	dilmah
Дата:	19.07.10 09:41
Оценка:

__>Лучше делать выборку в отдельное множество и с последующим вызовом метода swap

то есть чтобы удалить 2 элемента из 1000 нужно 998 элементов скопировать в tmp? оригинально..

Re: Удаление в цикле, std::set

От:	Shellac
Дата:	19.07.10 09:56
Оценка:	-1

Здравствуйте, Аноним, Вы писали:

mySet.erase(std::remove_if(mySet.begin(), mySet.end(), /*условие*/), mySet.end());

Re[2]: Удаление в цикле, std::set

От:	Кодт
Дата:	19.07.10 10:06
Оценка:

Здравствуйте, Shellac, Вы писали:

S>

S>mySet.erase(std::remove_if(mySet.begin(), mySet.end(), /*условие*/), mySet.end()); S>

Это рецепт для вектора.
Для множеств (set/multiset/map/multimap) он не подходит, потому что remove_if
— пытается преодолеть константность (итераторы возвращают ссылки на константные ключи)
— пытается сломать инварианты (упорядоченность и уникальность ключей)

Перекуём баги на фичи!
Re[3]: Удаление в цикле, std::set

От:	Shellac
Дата:	19.07.10 10:21
Оценка:

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, Shellac, Вы писали:

S>>

S>>mySet.erase(std::remove_if(mySet.begin(), mySet.end(), /*условие*/), mySet.end()); S>>

К>Это рецепт для вектора.
К>Для множеств (set/multiset/map/multimap) он не подходит, потому что remove_if
К>- пытается преодолеть константность (итераторы возвращают ссылки на константные ключи)
К>- пытается сломать инварианты (упорядоченность и уникальность ключей)

а, точно, не углядел

Re[3]: Удаление в цикле, std::set

От:	_niko_
Дата:	19.07.10 12:09
Оценка:

Здравствуйте, dilmah, Вы писали:

__>>Лучше делать выборку в отдельное множество и с последующим вызовом метода swap

D>то есть чтобы удалить 2 элемента из 1000 нужно 998 элементов скопировать в tmp? оригинально..

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

Re: Удаление в цикле, std::set

От:	saf_e
Дата:	20.07.10 14:09
Оценка:

Здравствуйте, Аноним, Вы писали:

А>Подскажите, есть объект std::set с элементами целого типа. В цикле проходиться и удаляется какой либо элемент по некоторому условию. При этом итератор становиться недействительным. Как после удаления переместить итератор на следующий элемент после удаленного?

Мне видится лишь достаточно неэффективный подход в виде:

for(set_iterator it . )
set_iterator next_it = it;
const T &key = *(++next_it);
set.erase(it);
it = set.find(key);
>

Re[2]: Удаление в цикле, std::set

От:	dilmah
Дата:	20.07.10 15:46
Оценка:	1 (1)

_>Мне видится лишь достаточно неэффективный подход в виде

у контейнеров типа std::set, std::map, std::list стандарт гарантирует, что удаление итератора не инвалидирует остальных итераторов. Поэтому самый первый ответ в этом топике является самым простым и корректным.

Особенности языков программирования

Мы подошли к двум наиболее интересным с точки зрения изучения STL контейнерам: set и map . С которым из них стоит познакомиться в первую очередь — вопрос, не имеющий однозначного ответа. Мнение автора заключается в том, что при академическом подходе к изучению STL, в первую очередь следует познакомиться с set , как с более простым контейнером из рассматриваемой пары. Всё, что можно сделать с set , можно сделать и с map , обратное же утверждение не всегда истинно. С алгоритмической точки зрения map является логическим продолжением set , в то время как многие программисты-практики зачастую смутно понимают назначение контейнера set , и всегда используют map , что менее элегантно и часто более сложно для понимания сторонними людьми. Контейнер set , как уже было упомянуто, содержит множество элементов. Строго говоря, set обеспечивает следующую функциональность: — добавить элемент в рассматриваемое множество, при этом исключая возможность появления дублей; — удалить элемент из множества; — узнать количество (различных) элементов в контейнере; — проверить, присутствует ли в контейнере некоторый элемент. Об алгоритмической эффективности контейнера set мы поговорим позже, вначале познакомимся с его интерфейсом.

set s; for(int i = 1; i s.insert(42); // ничего не произойдёт --- // элемент 42 уже присутствует в множестве for(int i = 2; i // set::size() имеет тип unsigned int int N = int(s.size()); // N будет равно 50

У set нет метода push_back() . Это неудивительно: ведь такого понятия, как порядок элементов или индекс элемента, в set не существует, поэтому слово «back» здесь никак не применимо. А раз уж у set нет понятия «индекс элемента», единственный способ просмотреть данные, содержащиеся в set , заключается в использовании итераторов:

set S; . // вычисление суммы элементов множества S int r = 0; for(set::const_iterator it = S.begin(); it != S.end(); it++)
Если вы пользуетесь GNU C++, то Traversing Macros будет весьма кстати. Показательный пример:

set < pair> > SS; . int total = 0; tr(SS, it) < total += it->second.first; >

Обратите внимание на синтаксис it->second.first . Ввиду того, что it является итератором, перед использованием его необходимо разыменовать. «Верным» синтаксисом было бы (*it).second.first . Однако, в C++ есть негласное правило, что если при описании некоторого объекта есть возможность обеспечить тождественное равенство конструкций (*it). и it-> , то это следует сделать, дабы не вводить пользователей в заблуждение. Разработчики STL, конечно, позаботились об этом в случае с итераторами. Основным преимуществом set перед vector является, несомненно, быстродействие. В основном это быстродействие проявляется при выполнении операции поиска. (При добавлении операция поиска также неявно присутствует, потому как дубли в set не допускаются). Однако, с операцией поиска в set / map есть существенный нюанс. Нюанс заключается в том, что вместо глобального алгоритма std::find(. ) следует использовать метод set set::find(. ) . Это не означает, что std::find(. ) не будет работать с set . Дело в том, что std::find(. ) ничего не знает о типе контейнера, с которым он работает. Принцип работы std::find(. ) крайне прост: он просматривает все элементы до тех пор, пока либо не будет найден искомый элемент, либо не будет достигнут конец интервала. Основное преимущество set перед vector заключается в использовании нелинейной структуры данных, что существенно снижает алгоритмическую сложность операции поиска; использование же std::find(. ) ануллирует все старания разработчиков STL. Метод set::find(. ) имеет всего один аргумент. Возращаемое им значение либо указывает на найденный элемент, либо равно итератору end() для данного экземпляра контейнера.

set s; . if(s.find(42) != s.end()) < // 42 присутствует >else < // 42 не присутствует >

Кроме find(. ) существует также операция count(. ) , которую следует вызывать как метод set::count(x) , а не как алгоритм std::count(begin, end, x) . Ясно, что set::count(x) может вернуть только 0 или 1. Некоторые программисты считают, что вышеприведённый код лучше выглядит, если использовать count(x) вместо find(x) :

if(s.count(42) != 0)
if(s.count(42))

Мнение автора заключается в том, что подобный код вводит читателя в заблуждение: сам смысл операции count() несовместим со случаями, когда элемент либо присутствует, либо нет. Если же вам предтавляется слишком длинным каждый раз писать «[некоторая форма find]» != container.end() , сделайте следующие макросы:

#define present_member(container, element) \ (find(all(container),element) != container.end()) #define present_global(container, element) \ (container.find(element) != container.end())

Здесь all(c) означает c.begin(),c.end() Более того, в соответствии с положением cтандарта, которое называется «конкретизация шаблонов», можно написать следующий код:

template bool present(const T& c, const T2& obj) < return find(c.begin(), c.end(), (T::element_type)(obj)) != c.end(); >template bool present(const set& c, const T2& obj)

При работе с контейнером типа set present(container, element) вызовет метод set::find(element) , в других случаях — std::find(container.begin(), container.end(), element) . Для удаления элемента из set необходимо вызвать метод erase(. ) , передав ему один элемент — элемент, который следует удалить, либо итератор, указывающий на удаляемый элемент.

set s; . s.insert(54); . s.erase(29); s.erase(s.find(57));

Как и полагается erase(. ) , set::erase(. ) имеет интервальную форму.

set s; . set::iterator it1, it2; it1 = s.find(10); it2 = s.find(100); // Будет работать, если как 10, так и 100 присутствуют в множестве if(. ) < s.erase(it1, it2); // при таком вызове будут удалены // все элементы от 10 до 100 не включительно >else < // сдвинем it2 на один элемент вперёд // set::iterator является normal iterator // операция += не определена для итераторов set'а, //но ++ и -- допускаются it2++; s.erase(it1, it2); // а при таком --- от 10 до 100 включительно // приведённый код будет работать, даже если 100 был // последним элементом, входящим в set >

Также, как и полагается контейнерам STL, у set есть интервальный конструктор:

int data[5] = < 5, 1, 4, 2, 3 >; set S(data, data+5);

Кстати, данная функция set предоставляет эффективную возможность избавиться от дубликатов в vector :

vector v; . set s(all(v)); vector v2(all(s));

Теперь v2 содержит те же элементы, что и v , но без дубликатов. Приятной особенностью также является тот факт, что элементы v2 упорядочены по возрастанию, но об этом мы поговорим позже. В set можно хранить элементы любого типа, которые можно упорядочить. Об этом мы тоже поговорим позже.

Удаление элементов контейнера

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

Отслеживать
206k 28 28 золотых знаков 293 293 серебряных знака 526 526 бронзовых знаков
задан 18 ноя 2013 в 19:06
469 1 1 золотой знак 10 10 серебряных знаков 24 24 бронзовых знака

Трюк здесь в том, что std::remove_if ничего не удаляет, а просто переставляет элементы. Если не хотите ломать голову самостоятельно, то ключевые слова — remove_if и cppreference .

18 ноя 2013 в 20:47

2 ответа 2

Сортировка: Сброс на вариант по умолчанию

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

Вы должны на самом деле воспользоваться идиомой 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)), str.end()); 

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

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

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

std::set s = ; for (auto it = s.begin(); it != s.end(); /**/) < if () it = s.erase(it); else ++it; > 

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

Как удалить элемент из set c

мне нужно в цикле пробежаться ко контейнеру и удалить элементы, которые удовлетворяют условию.
/Но после удаления все итераторы битые. Гдето встречал правильный способ удаления в цикле, но не могу вспомнить (так что-то с самим итератором мутилось)

Использовать функтор не могу, т.к. помимо удаления нужно дергать кучу методов. о которых функтор не должен знать.

Сообщ. #2 , 02.06.07, 22:39
Unregistered

Ну так старые итераторы по-любому будут невалидными, а удаление можно же с remove_if() прокатить или у тебя по ситуации не получается?
Ну если в цикле, то так, но вообще не рекомендуется счетчик изменять в самом цикле:

std::set arr;
arr.insert(«shit»);
arr.insert(«not_shit»);
for (std::set::iterator iter = arr.begin(); iter != arr.end(); ++iter)
if(*iter == «shit»)
arr.erase(iter);
iter = arr.begin();
Сообщение отредактировано: Xenon_Sk — 02.06.07, 22:42
Сообщ. #3 , 02.06.07, 22:49
Рейтинг (т): 1

Не. было что-то не так. У тебя не рационально, а там за один проход все делалось.
Если найду, то сообщу как

Сообщ. #4 , 02.06.07, 22:52
Unregistered

Вроде это нереально, так как после удаления некого элемента бывшие итераторы уже невалидны . Но может есть какая хитрость — не знаю тогда уже.
А то, что тут нерационально и слону понятно

Сообщ. #5 , 02.06.07, 23:43
Рейтинг (т): 1

Для последовательных контейнеров