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