слов из стандартного средства ввода. Все
уникальные слова будут помещены в экземпляр класса std::set. Таким образом мы сможем перечислить все уникальные слова из потока[1].
1. Мы используем несколько разных типов STL, для чего включим некоторые заголовочные файлы:
#include <iostream>
#include <set>
#include <string>
#include <iterator>
2. Чтобы сэкономить немного времени на наборе текста, объявим об использовании пространства имен std:
using namespace std;
3. Теперь мы готовы писать саму программу, начинающуюся с функции main. В ней создается экземпляр класса std::set, в котором будут храниться строки:
int main()
{
set<string> s;
4. Далее получим данные от пользователя. Просто считаем их из стандартного потока ввода с помощью удобного итератора istream_iterator:
istream_iterator<string> it {cin};
istream_iterator<string> end;
5. Имея начальный и конечный итераторы, которые представляют данные, введенные пользователем, можем просто заполнить множество на основе этих данных с помощью std::inserter:
copy(it, end, inserter(s, s.end()));
6. На этом, в общем-то, все. Чтобы увидеть, какие уникальные слова мы получили из стандартного ввода, просто выведем на экран содержимое нашего множества:
for (const auto word : s) {
cout << word << ", ";
}
cout << 'n';
}
7. Скомпилируем и запустим программу с нашими входными данными. Взглянем на полученный результат, из которого были удалены все дубликаты, а уникальные слова теперь отсортированы по алфавиту:
$ echo "a a a b c foo bar foobar foo bar bar" | ./program
a, b, bar, c, foo, foobar,
Как это работает
В данной программе можно отметить два интересных момента. Первый из них состоит в том, что мы применяем итератор std::istream_iterator, чтобы получить доступ к данным, введенным пользователем. Второй момент: для записи этих данных в наш контейнер std::set мы задействуем алгоритм std::copy, который обернули в экземпляр класса std::inserter! Может показаться удивительным то, что всего одна строка кода выполняет всю работу по токенизации входных данных, помещению их во множество, отсортированное по алфавиту, и отсечению дубликатов.
std::istream_iterator
Этот класс очень интересен в тех случаях, когда мы хотим обрабатывать большие объемы однотипных данных, получаемые из потока, чему и посвящен наш пример: мы анализируем все входные данные слово за словом и помещаем их в множество в виде экземпляров класса std::string.
Итератор std::istream_iterator принимает один шаблонный параметр с необходимым нам типом. Мы выбрали тип std::string, поскольку ожидаем, что будем работать со словами, но это могут быть, например, и числа с плавающей точкой. По сути, здесь годится любой тип, для которого можно записать cin>>var;. Конструктор принимает экземпляр класса istream. Стандартный поток ввода представляется глобальным объектом потока ввода std::cin, который вполне подходит для нашего случая.
istream_iterator<string> it {cin};
К созданному итератору потока ввода применимы две операции. Во-первых, при разыменовании (*it) он возвращает текущий введенный символ. Поскольку мы указали, что итератор соотнесен с типом std::string с помощью шаблонного параметра, этот символ будет содержать одно слово. Во-вторых, при инкременте (++it) итератор переходит на следующее слово, к которому мы также можем получить доступ путем разыменования.
Но погодите, нужно быть аккуратными после выполнения операции инкремента и до разыменования. При пустом стандартном потоке ввода итератор нельзя разыменовывать. Вместо этого следует завершить цикл, в котором мы разыменовываем итератор, для получения каждого слова. Условие остановки, позволяющее узнать, что итератор стал некорректным, — сравнение с конечным итератором. Если сравнение it==end выполнилось, то мы дошли до последнего введенного слова.
Конечный итератор — это экземпляр std::istream_iterator, созданный с помощью стандартного конструктора без параметров. Он нужен для сравнения в условии остановки, проверяемом на каждой итерации цикла:
istream_iterator<string> end;
Как только std::cin окажется пустым, итератор it обнаружит это и наше сравнение с конечным оператором вернет результат true.
std::inserter
Мы использовали пару итераторов it и end как итераторы для работы с входными данными в вызове std::copy. Третий параметр должен быть итератором для работы с выходными данными. Здесь мы не можем просто взять итератор s.begin() или s.end(). Для пустого множества они будут одинаковыми, так что нам даже нельзя разыменовать их независимо от того, делаем мы это для чтения (из) или присваивания (в).
Тут вступает в дело std::inserter. Это функция, возвращающая итератор std::insert_iterator, который ведет себя как итератор, но при этом делает что-то отличное от того, что делают обычные итераторы. Выполнение операции инкремента для данного итератора ничего не даст. Когда мы его разыменовываем и присваиваем значение, он берет контейнер, прикрепленный к нему, и добавляет в него заданное значение как новый элемент!
При создании экземпляра std::insert_iterator с помощью std::inserter вам понадобятся два параметра:
auto insert_it = inserter(s, s.end());
Здесь s — наше множество, а s.end() — итератор, указывающий на место, куда должен быть вставлен новый элемент. Для пустого множества, с которого и начинается наш пример, этот итератор эквивалентен s.begin(). В других структурах данных наподобие векторов или списков второй параметр критически важен при определении того, куда именно итератор вставки должен добавить новые элементы.
Собираем все воедино
В конце концов все волшебство происходит во время вызова метода std::copy:
copy(input_iterator_begin, input_iterator_end, insert_iterator);
Данный вызов получает следующий токен слова из потока std::cin с помощью входного итератора и помещает его в контейнер std::set. После этого он инкрементирует оба итератора и проверяет, равен ли входной итератор конечному. Если это не так, то в потоке ввода еще остаются слова, так что все повторяется.
Повторяющиеся слова отбрасываются автоматически. При наличии в множестве конкретного слова повторное его добавление эффекта не возымеет. Этим контейнер std::set отличается от std::multiset, куда можно вставить повторяющиеся записи.
Реализуем простой ОПН-калькулятор с использованием контейнера std::stack
Класс std::stack — класс-адаптер, который позволяет помещать в себя объекты, словно в реальную стопку объектов, а также получать их. В текущем разделе на основе этой структуры данных мы создадим калькулятор, применяющий обратную польскую нотацию, ОПН (reverse polish notation, RPN).
ОПН — это нотация, которая может служить
