Как удалить элемент из 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
Оценка:

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

Лучше делать выборку в отдельное множество и с последующим вызовом метода 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>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
Оценка:

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

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

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 стандарт гарантирует, что удаление итератора не инвалидирует остальных итераторов. Поэтому самый первый ответ в этом топике является самым простым и корректным.

Контейнер set (множество)

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

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

Подробней о возможностях контейнера set можно прочитать, например, на сайте cppreference.com.

В простейшем случае множество, например, данных типа int объявляется так:

Для добавления элемента в множество используется метод insert :

Для проверки принадлежности элемента множеству используется метод count . Этот метод возвращает количество вхождения передаваемого параметра в данный контейнер, но поскольку в множестве все элементы уникальные, то count для типа set всегда возвращает 0 или 1. То есть для проверки принадлежности значения x множеству S можно использовать следующий код:

Для удаления элемента используется метод erase . Ему можно передать значение элемента, итератор, указывающий на элемент или два итератора (в этом случае удаляется целый интервал элементов, содержащийся между заданными итераторами). Вот два способа удалить элемент x :

Метод size() возвращает количество элементов в множестве, метод empty() , возвращает логическое значение, равное true , если в множестве нет элементов, метод clear() удаляет все элементы из множества.

Итераторы

С итераторами контейнера set можно выполнять операции инкремента (что означает переход к следующему элементу) и декремента (переход к предыдущему элементу). Итераторы можно сравнивать на равенство и неравенство. Операции сравнения итераторов при помощи «», «> page_code_style»>begin() , который возвращает итератор на первый элемент множества, и метод e nd() , который возвращает фиктивный итератор на элемет, следующий за последним элементом в множестве. Таким образом, вывести все элементы множества можно так:

set ::iterator it;

for (it = S.begin(); it != S.end(); ++it)

Благодаря тому, что множества хранятся в упорядоченном виде, все элементы будут выведены в порядке возрастания значений.

В стандарте C++11 разрешается перебор всех элементом множества при помощи range-based цикла:

for (auto elem: S)

Элементы также будут выведены в порядке возрастания.

Для вывода элементов в порядке убывания можно использовать reverse_iterator аналогично векторам:

for (auto it = S.rbegin(); it != S.rend(); ++it)

Функции удаления элементов могут принимать итератор в качестве параметра. В этом случае удаляется элемент, на который указывает итератор. Например, чтобы удалить наименьший элемент:

Но для удаления последнего (наибольшего) элемента в set нельзя использовать reverse_iterator, нужно взять обычный итератор, указывающий на end(), уменьшить и удалить:

auto it = S.begin();

Поиск элемента в set

Для поиска конкретного элемента в set используется метод find . Этот метод возвращает итератор на элемент, а если элемент не найден, то он возвращает итератор end() (т.е. на фиктивный элемент, следующий за последним элементом множества. Используя этот метод проверить принадлежность элемента множеству можно так:

Также есть методы lower_bound и upper_bound , которые находят первых элемент, больше или равный x и первый элемент, строго больший x (аналогично двоичному поиску элемента в массиве).

Эти методы также возвращают итераторы, а если таких элементов (больше или равных или строго больших) нет в множестве, они возвращают end() .

Например, удалить из set минимальный элемент, строго больший x можно так:

auto it = S.upper_bound(x);

Контейнер multiset

Контейнер multiset (он также определен в заголовочном файле set ) реализует упорядоченное множество, которое может содержать несколько равных друг другу элементов.

Во многом этот контейнер похож на set , есть некоторые отличия.

1. Метод erase если ему передать значение удаляемого элемента, удаляет все элементы, равные данному. Для удаления ровно одного элемента нужно методу erase передать итератор на удаляемый элемент. Например, чтобы удалить ровно один элемент, равный x, нужно сделать так:

2. Метод count(x) возвращает количество элементов, равных x. Сложность этого алгоритма равна $O(\log n + k)$, где $n$ — количество элементов в множестве, $k$ — количество элементов, равных x. То есть единственный способ понять, сколько в множестве содержится элементов, равных $x$ — это найти первый элемент, а затем двигаться дальше по дереву просматривая все элементы, до появления первого элемента, не равного x.

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

В этой статье будет дан обзор библиотеки STL с самого начального уровня, и до продвинутой, весьма полезной в ряде задач, функциональности.

Проще всего начать знакомство с STL со стандартных типов для хранения данных — контейнеров. Каждый раз, когда в программе возникает необходимость оперировать множеством элементов, в дело вступают контейнеры. Контейнер — это практическая реализация функциональности некоторой структуры данных. В языке C (не в C++) существовал только один встроенный тип контейнера: массив. Сам по себе массив имеет ряд недостатков: к примеру, размер динамически выделенного массива невозможно определить на этапе выполнения. Однако основной причиной для более внимательного ознакомления с контейнерами STL является отнюдь не вышеперечисленные недостатки массива. Истинная причина кроется несколько глубже. Дело в том, что в реальном мире структура данных, информацию о которых необходимо хранить, далеко не всегда удачно представима в виде массива. В большинстве случаев требуется контейнер несколько иной функциональности. К примеру, нам может потребоваться структура данных «множество строк», поддерживающая следующие функции:
— добавить строку к множеству;
— удалить строку из множества;
— определить, присутствует ли в рассматриваемом множестве данная строка;
— узнать количество различных строк в рассматриваемом множестве;
— просмотреть всю структуру данных, «пробежав» все присутствующие строки. Конечно, легко запрограммировать тривиальную реализацию функциональность подобной структуры данных на базе обычного массива. Но такая реализация будет крайне неэффективной. Для достижения приемлемой производительности имеет смысл реализовать хэш-таблицу или сбалансированное дерево, но задумайтесь: разве реализация подобной структуры данных (хэш либо дерево) зависит от типа хранимых объектов? Если мы потом захотим использовать ту же структуру не для строк, а, скажем, для точек на плоскости — какую часть кода придётся переписывать заново? Реализация подобных структур данных на чистом C оставляла программисту два пути. 1) Жёсткое решение (Hard-Coded тип данных). При этом изменение типа данных приводило к необходимости внести большое число изменений в самых различных частях кода. 2) По возможности сделать обработчики структуры данных независимыми от используемого типа данных. Иными словами, использовать тип void* везде, где это возможно. По какому бы пути реализации структуры данных в виде контейнера вы не пошли, скорее всего, никто другой ваш код понять, и тем более модифицировать, будет не в состоянии. В лучшем случае другие люди смогут им просто пользоваться. Именно для таких ситуаций существуют стандарты — чтобы программисты могли говорить друг с другом на одном и том же формальном языке. Шаблоны (Templates) в C++ предоставляют замечательную возможность реализовать контейнер один раз, формализовать его внешние интерфейсы, дать асимптотические оценки времени выполнения каждой из операций, а после этого просто пользоваться подобным контейнером с любым типом данных. Можете быть уверены: разработчики стандарта C++ так и поступили. В первой части курса мы на практике познакомимся с основными концепциями, положенными в основу контейнеров C++.

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