Эффективное использование STL и шаблонов

Эффективное использование STL и шаблонов

Сергей Сацкий

Введение

С помощью конечных автоматов (далее просто автомат) можно успешно решать обширный класс задач. Это обстоятельство подмечено давно, поэтому в литературе по проектированию программного обеспечения часто приводятся рассуждения на тему применения автоматов ([2], [5], [8]). Однако в процессе моделирования автомат рассматривается с более высокого уровня, нежели это делается в момент его реализации с использованием конкретного языка программирования.

Последний раз журнал C / C++ User’s Journal обращался к проблеме проектирования конечных автоматов (Finite State Machine) в майском выпуске 2000 года ([1]). В этом номере была напечатана статья Дэвида Лафренье (David Lafreniere), где автор описывал использованный им подход. С тех пор прошло много времени, и в данной статье будет сделана попытка применить другой подход к проектированию конечного автомата с учетом современных тенденций в проектировании программного обеспечения.

Для удобства рассмотрим простой пример, который будет использоваться далее. Допустим, что необходимо определить, является ли входная последовательность символов целым числом, допустимым идентификатором, или недопустимой строкой. Под допустимыми идентификаторами будем понимать такие идентификаторы, которые начинаются с буквы и далее содержат буквы и "/", или цифры. Автомат, который поможет решить задачу, показан на рисунке 1. На рисунке используется нотация UML (Unified Modeling Language).

Рисунок 1. Автомат, позволяющий выяснить, что представляет собой входная строка.

Следует отметить, что различные источники наделяют подобный автомат различными атрибутами. Чемпионом по их количеству, наверное, является UML ([2]). Здесь можно найти отложенные события (deferred events), внутренние переходы (internal transitions), параметризованные триггеры событий (event triggers with parameters), дополнительные условия переходов (guard conditions), входные функции (entry action), выходные функции (exit action), события, генерируемые по таймеру (time events) и т.д. Однако здесь мы для простоты изложения опустим дополнительные атрибуты (к некоторым из них мы вернемся позже) и сосредоточимся на простой модели, где есть состояния, события и переходы между состояниями.

На данный момент все, что мы имеем – это наглядная и удобная для внесения изменений модель. Как теперь перейти от нее к коду на языке С++? Самый простой из способов реализации – это набор операторов if в том или ином виде. Например: