Особенности языков программирования
Мы подошли к двум наиболее интересным с точки зрения изучения 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 золотых знаков 291 291 серебряный знак 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 .
Удалить элементы из набора в C++
1. Удалить один элемент из набора в C++.
2. Условно удалить элементы из набора в C++, которые удовлетворяют предикату.
1. Удаление одного элемента
Удалить один элемент из контейнера set в C++ очень просто. Идея состоит в том, чтобы передать данный элемент в set::erase функция, которая стирает его из набора.
std :: unordered_set < char >s = < 'a' , 'b' , 'c' , 'd' >;
int key = ‘d’ ;
s . erase ( key ) ;
for ( char const &c : s ) <
std :: cout << c << ' ' ;
результат:
c b a
2. Удаление всех элементов, удовлетворяющих предикату
Мы даже можем условно удалить элементы из набора, удовлетворяющего предикату. Идея состоит в том, чтобы использовать итераторы для итерации набора и вызова unordered_set::erase функция, если текущий элемент соответствует условию. Обратите внимание, что вызов erase() Функция во время итерации требует особого внимания, поскольку она делает итератор недействительным. Мы можем справиться с этим несколькими способами:
1. В C++11 и выше, erase() возвращает итератор к следующему элементу или к unordered_set::end если последний элемент удален. Идея состоит в том, чтобы использовать возвращаемое значение erase() для установки итератора на следующий элемент, как показано ниже:
Контейнер 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);