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 <iostream>
#include <stack>
#include <iterator>
#include <map>
#include <sstream>
#include <cassert>
#include <vector>
#include <stdexcept>
#include <cmath>
2. Мы также объявляем, что используем пространство имен std, чтобы сэкономить немного времени, которое ушло бы на набор текста:
using namespace std;
3. Далее немедленно начнем реализовывать наш анализатор ОПН. Он станет принимать пару итераторов, указывающих на начало и конец математического выражения, передаваемого в качестве строки, которое будет проработано токен за токеном:
template <typename IT>
double evaluate_rpn(IT it, IT end)
{
4. Пока мы итерируем по токенам, нам следует запоминать все операнды до тех пор, пока мы не встретим операцию. Для этого и нужен стек. Все числа будут проанализированы и сохранены с удвоенной точностью, поэтому мы заводим стек элементов типа double:
stack<double> val_stack;
5. Чтобы удобным образом получить доступ к элементам стека, реализуем вспомогательную функцию. Она изменяет стек, извлекая значение с его вершины, а затем возвращает это значение. Таким образом мы сможем выполнить нашу задачу за один шаг:
auto pop_stack ([&](){
auto r (val_stack.top());
val_stack.pop();
return r;
});
6. Еще одним приготовлением будет определение всех поддерживаемых математических операций. Мы сохраним их в ассоциативный массив, где каждый токен операции будет связан с самой операцией. Операции представлены вызываемыми лямбда-выражениями, которые принимают два операнда, а затем, например, складывают или умножают их и возвращают результат:
map<string, double (*)(double, double)> 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. Если эта операция завершается успешно, то у нас появляется операнд, который мы помещаем в стек: