Контейнер 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);
Как удалить элемент из 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 стандарт гарантирует, что удаление итератора не инвалидирует остальных итераторов. Поэтому самый первый ответ в этом топике является самым простым и корректным.
Удаление элементов контейнера
Нужно написать алгоритм, который удаляет из диапазона [first , last) все элементы, для которых значение предиката pr равно true. Удаленные элементы сдвигаются в конец контейнера. Возвращает итератор на первый удаленный элемент. Ведь итератор это указатель на элемент контейнера, и вот как через него удалять элементы? Подскажите, пожалуйста. Спасибо.
Отслеживать
207k 28 28 золотых знаков 294 294 серебряных знака 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 .
Контейнер multiset
Контейнер multiset (он также определен в заголовочном файле set ) реализует упорядоченное множество, которое может содержать несколько равных друг другу элементов.
Во многом этот контейнер похож на set , есть некоторые отличия.
1. Метод erase если ему передать значение удаляемого элемента, удаляет все элементы, равные данному. Для удаления ровно одного элемента нужно методу erase передать итератор на удаляемый элемент. Например, чтобы удалить ровно один элемент, равный x, нужно сделать так:
2. Метод count(x) возвращает количество элементов, равных x. Сложность этого алгоритма равна $O(\log n + k)$, где $n$ — количество элементов в множестве, $k$ — количество элементов, равных x. То есть единственный способ понять, сколько в множестве содержится элементов, равных $x$ — это найти первый элемент, а затем двигаться дальше по дереву просматривая все элементы, до появления первого элемента, не равного x.