Но погодите, нужно быть аккуратными после выполнения операции инкремента и до разыменования. При пустом стандартном потоке ввода итератор нельзя разыменовывать. Вместо этого следует завершить цикл, в котором мы разыменовываем итератор, для получения каждого слова. Условие остановки, позволяющее узнать, что итератор стал некорректным, — сравнение с конечным итератором. Если сравнение
it==end
выполнилось, то мы дошли до последнего введенного слова.Конечный итератор — это экземпляр
std::istream_iterator
, созданный с помощью стандартного конструктора без параметров. Он нужен для сравнения в условии остановки, проверяемом на каждой итерации цикла:
istream_iterator 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).ОПН — это нотация, которая может служить для записи математических выражений таким образом, чтобы их было проще анализировать. В ОПН выражение
1 + 2
выглядит как 1 2 +
. Сначала идут операнды, а затем — оператор. Еще один пример: выражение (1 + 2) * 3
в ОПН выглядит как 1 2 + 3 *
, оно уже показывает, почему подобные выражения проще анализировать, и нам не нужны скобки, чтобы определить подвыражения (рис. 2.4).
Как это делается
В этом примере мы считаем математическое выражение, записанное в формате ОПН, из стандартного потока ввода, а затем передадим его в функцию, которая вычислит его значение. Наконец, выведем на экран численный результат.
1. Мы будем использовать множество вспомогательных объектов из STL, поэтому сначала разместим несколько директив включения:
#include
#include
#include
#include
#include
#include
#include
#include
#include
2. Мы также объявляем, что используем пространство имен
std
, чтобы сэкономить немного времени, которое ушло бы на набор текста:
using namespace std;
3. Далее немедленно начнем реализовывать наш анализатор ОПН. Он станет принимать пару итераторов, указывающих на начало и конец математического выражения, передаваемого в качестве строки, которое будет проработано токен за токеном:
template
double evaluate_rpn(IT it, IT end)
{
4. Пока мы итерируем по токенам, нам следует запоминать все операнды до тех пор, пока мы не встретим операцию. Для этого и нужен стек. Все числа будут проанализированы и сохранены с удвоенной точностью, поэтому мы заводим стек элементов типа
double
:
stack val_stack;
5. Чтобы удобным образом получить доступ к элементам стека, реализуем вспомогательную функцию. Она изменяет стек, извлекая значение с его вершины, а затем возвращает это значение. Таким образом мы сможем выполнить нашу задачу за один шаг:
auto pop_stack ([&](){
auto r (val_stack.top());
val_stack.pop();
return r;
}
);
6. Еще одним приготовлением будет определение всех поддерживаемых математических операций. Мы сохраним их в ассоциативный массив, где каждый токен операции будет связан с самой операцией. Операции представлены вызываемыми лямбда-выражениями, которые принимают два операнда, а затем, например, складывают или умножают их и возвращают результат:
map ops {
{"+", [](double a, double b) { return a + b; }},
{"-", [](double a, double b) { return a - b; }},
{"*", [](double a, double b) { return a * b; }},
{"/", [](double a, double b) { return a / b; }},
{"^", [](double a, double b) { return pow(a, b); }},
{"%", [](double a, double b) { return fmod(a, b); }},
};
7. Теперь наконец можно проитерировать по входным данным. Предположив, что входные итераторы передали строки, мы передаем данные в новый поток
std::stringstream
токен за токеном, поскольку он может анализировать числа:
for (; it != end; ++it) {
stringstream ss {*it};
8. Теперь, когда у нас есть все токены, попробуем получить на их основе значение типа
double
. Если эта операция завершается успешно, то у нас появляется операнд, который мы помещаем в стек:
if (double val; ss >> val) {
val_stack.push(val);
}
9. Если же операция завершается неудачно, то перед нами нечто отличное от оператора. Это может быть только операнд. Зная, что все поддерживаемые нами операции бинарны, нужно вытолкнуть два последних операнда из стека:
else {
const auto r {pop_stack()};
const auto l {pop_stack()};
10. Теперь мы получаем операнд путем разыменования итератора
it
, который возвращает строки. Обратившись в ассоциативный массив