Скотт Мейерс - Эффективное использование STL. Предисловие

Предисловие Это издание книги является не просто дополненной, а полностью переработанной версией предыдущего. В iOS 7 изменилось все: внешний вид и функциональная сторона операционной системы, способы использования наших устройств с iOS и, самое главное, принципы

Предисловие Я уверен, что в каждом из нас есть что-то незаурядное, но масса времени уходит на то, чтобы понять, что же на самом деле важно, на то, чтобы вытянуть это из самого себя. Ты не сможешь стать незаурядным, если не любишь свое окружение, свои инструменты, свою область

Во многих книгах описываются возможности STL, но только в этой рассказано о том, как работать с этой библиотекой. Каждый из 50 советов книги подкреплен анализом и убедительными примерами, поэтому читатель не только узнает, как решать ту или иную задачу, но и когда следует выбирать то или иное решение - и почему именно такое.

Предисловие

«...На нем не было ленточки! Не было ярлыка! Не было коробки и не было мешка!»

Я впервые написал о STL (Standard Template Library) в 1995 году. Моя книга «More Effective C++» завершалась кратким обзором библиотеки. Но этого оказалось недостаточно, и вскоре я начал получать сообщения с вопросом, когда будет написана книга «Effective STL».

Несколько лет я сопротивлялся этой идее. Сначала я не обладал достаточным опытом программирования STL и не считал возможным давать советы. Но время шло, и на смену этой проблеме пришли другие. Бесспорно, появление библиотеки означало прорыв в области эффективной масштабируемой архитектуры, но в области использования STL возникали чисто практические проблемы, на которые было невозможно закрывать глаза. Адаптация любых программ STL, за исключением самых простейших, была сопряжена с множеством проблем, что объяснялось не только различиями в реализациях, но и разным уровнем поддержки шаблонов компиляторов. Учебники по STL были редкостью, поэтому постижение «дао программирования в STL» оказывалось задачей непростой. А как только программист справлялся с этой трудностью, возникала другая - поиск достаточно полной и точной справочной документации. Даже самая мелкая ошибка при использовании STL сопровождалась лавиной диагностических сообщений компилятора, длина которых достигала нескольких тысяч символов, причем в большинстве случаев речь шла о классах, функциях и шаблонах, не упоминавшихся в программе. При всем уважении к STL и разработчикам этой библиотеки я не решался рекомендовать ее программистам среднего звена. Я не был уверен в том, что STL можно использовать эффективно.

Затем я заметил нечто удивительное. Несмотря на все проблемы с переносом и скверное качество документации, несмотря на сообщения компилятора, напоминавшие бессмысленное нагромождение символов, многие из моих клиентов все равно работали с STL. Более того, они не просто экспериментировали с библиотекой, а использовали ее в коммерческих версиях своих программ! Для меня это было откровением. Я знал, что программы, использующие STL, отличались элегантной архитектурой, но любая библиотека, ради которой программист добровольно обрекал себя на трудности с переносом, на скверную документацию и невразумительные сообщения об ошибках, должна была обладать чем-то большим, чем хорошая архитектура. Все больше профессиональных программистов полагало, что даже плохая реализация STL лучше, чем ее полное отсутствие.

Более того, я знал, что ситуация с STL будет улучшаться. Библиотеки и компиляторы будут постепенно приближаться к требованиям Стандарта (так оно и было), появится качественная документация (см. список литературы на с. 203), а диагностика компилятора станет более вразумительной (в этой области ситуация оставляет желать лучшего, но рекомендации совета 49 помогут вам с расшифровкой сообщений). В общем, я решил внести свою лепту в движение STL. Так появилась эта книга - 50 практических советов по использованию STL в C++.

Сначала я намеревался написать книгу за вторую половину 1999 г. и даже набросал ее примерную структуру. Но потом планы изменились, я приостановил работу над книгой и разработал вводный курс по STL, который преподавался нескольким группам программистов. Примерно через год я вернулся к книге и значительно расширил материал на основании опыта, полученного за время преподавания. В книге я постарался осветить практические аспекты программирования в STL, особенно важные для профессиональных программистов.

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

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

Введение

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

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

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

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

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

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

Не слишком наглядно, не так ли? А теперь представим себе, что мы имеем десятки событий и десятки состояний. Такой код просматривать трудно. Особенно тяжкие проблемы возникают при сопровождении кода, когда к нему надо вернуться через несколько месяцев и внести исправления.

Другая возможная реализация состоит в наборе функций, каждая из которых представляет собой состояние. Такая функция сможет возвратить указатель на ту функцию, которая соответствует новому состоянию автомата. Такая реализация также не облегчает поддержку кода.

Подойдем к проблеме немного с другой стороны. Картинка – это хорошо, но в исходном виде она никаким образом не может быть перенесена в исходный текст. Значит, даже, если решение будет найдено, то это будет нечто промежуточное между картинкой и обычным текстом.

Подход к реализации автомата

Таким промежуточным вариантом представления автомата может быть таблица. Этот способ известен давно, например . Составим таблицу переходов для нашего автомата (таблица 1).

Таблица 1.

Здесь в первой строке перечислены возможные состояния, а в первом столбце – возможные события. На пересечениях указаны состояния, в которые должен осуществиться переход.

Представление автомата в виде таблицы гораздо нагляднее, чем “размазанное” представление того же автомата в виде условных операторов или функций переходов. Таблицу уже можно попытаться переложить на код.

Предположим, что удалось переложить таблицу на код. Каким бы хотелось видеть этот код? Сформулируем требования к нему ():

Описание автомата (читай – таблица) должно быть сконцентрировано в одном месте. Это даст легкость чтения, понимания и модификации автомата.

Представление автомата должно быть типобезопасным.

Не должно быть ограничений на количество состояний и событий.

События и состояния хотелось бы представить в виде абстрактных типов, определяемых пользователем.

По возможности, автомат хотелось бы сделать гибким и легко расширяемым.

По возможности, хотелось бы проверять описание автомата.

По возможности, хотелось бы исключить неправильное использование автомата.

Требования 1 и 7 означают, что все описание автомата хорошо бы поместить в конструктор. В конструкторе же надо проверять правильность описания – требование 6.

Требование 2 означает, что не должно использоваться никаких небезопасных операций вида reinterpret_cast.

О требовании 5 поговорим позже, а сейчас обсудим требование 3. В общем случае количество возможных состояний (то есть количество столбцов в таблице) неизвестно. Неизвестно также и количество событий (то есть количество строк в таблице). Получается, что у конструктора класса, который будет представлять собой автомат, переменное количество аргументов. С первого взгляда кажется, что эту проблему легко решить с помощью функций языка C va_arg(), va_copy(), va_end() и va_start() (). Однако, не все так просто. Для этих функций обязательно нужно предусмотреть признаки окончания списков, а у нас количество элементов в строках и столбцах неизвестно. Размерность же задавать нежелательно. Кроме того, эти функции работают гарантированно только для POD (Plain Old Data), а для произвольных типов возможны неприятности.

Подойдем с другой стороны. Напишем, каким хотелось бы видеть конструктор автомата:

При таком вызове конструктора путем форматирования текста, набранного моноширинным шрифтом, описанию автомата удастся придать вид таблицы. Пофантазируем:

Со стартовым состоянием все просто: это всего лишь объект класса, представляющего состояние. Со списком состояний и тем более со списком переходов дело сложнее. Перечислить состояния через запятую не удастся. Более того, для SFiniteStateMachine было бы удобно иметь фиксированное количество аргументов. Оказывается, это возможно. Ведь мы можем создать временные объекты, каждый из которых будет заниматься своим списком.

Рассмотрим список состояний. Здесь остается та же проблема – неопределенное количество состояний. Помочь в ее решении может перегрузка операторов и конструктор по умолчанию. Перечислить аргументы через запятую все равно не удалось бы, но вместо запятой подошел бы и другой разделитель. Таким разделителем может быть <<, то есть обработку списка состояний можно записать так:

Аналогичным образом поступим со списком переходов для одного события. Отличие будет лишь в том, что каждый список переходов имеет еще один атрибут – событие, для которого описываются переходы. Конструктор STransitionsProxy будет принимать один аргумент: событие, а перегруженный operator<< будет принимать состояния.

Перегруженный operator<< проверит, что сначала идет список состояний, что список состояний только один, что в списках переходов нет повторяющихся событий и в переходах указаны только состояния, указанные в списке состояний. operator<< также проверит, что количество состояний в списках переходов равно количеству состояний в списке состояний. В результате конструктор SFiniteStateMachine будет выглядеть так:

На конструктор SFiniteStateMachine будет возложена задача проверки начального состояния. Оно должно быть в списке состояний.

Путем форматирования текста уже удалось придать аргументам конструктора вид таблицы. Однако это еще не все. При описании автомата были опущены все детали, связанные с шаблонами. На практике это означает, что при конструировании также придется указывать типы, что дополнительно “замусорит” текст. Несмотря на проблемы, связанные с препроцессором, он здесь поможет. Запись аргументов конструктора станет примерно такой:

Такая запись уже приемлема для повседневного использования.

Детали реализации

Реализация должна включать ряд вспомогательных элементов, в частности, исключения. Автомат будет выдавать их в случае ошибки в описании состояний и переходов. При разработке своего класса исключений можно воспользоваться наследованием от класса стандартного исключения. Это даст возможность указать в блоке catch только ссылку на базовый стандартный класс исключений. Свой класс исключений можно определить так:

Вернемся к конструкторам. Поскольку они имеют дело со списками переменной длины, то для сохранения элементов логично воспользоваться контейнерами, предоставляемыми библиотекой STL (). Для хранения одномерного списка воспользуемся контейнером vector, а для таблицы переходов – вектором векторов:

Поскольку контейнер vector поддерживает operator , то для поиска состояния, в которое необходимо совершить переход, в таблице переходов можно воспользоваться подобной конструкцией:

Разумеется, класс автомата должен будет иметь функцию, принимающую и обрабатывающую событие. Существует два варианта. Первый – это функция, второй – перегрузка какого-либо оператора. Для придания дополнительной гибкости реализуем оба варианта:

Остается вопрос: что делать, если придет событие, для которого у автомата нет описания переходов? Возможны варианты: просто проигнорировать такое событие, сгенерировать исключение или сделать что-то, определяемое пользователем. Воспользуемся идеей стратегий () и включим в число аргументов шаблона функтор, который будет определять нужную стратегию поведения. Такой подход вполне соответствует требованию 5. При этом можно задать стратегию по умолчанию – например, генерировать исключение. Теперь заголовок шаблона выглядит так:

Если понадобятся другие действия, всегда можно написать собственный функтор по образу и подобию SIgnoreStrategy и передать его шаблону.

Многие источники, описывающие конечные автоматы, упоминают о возможности вызова функций при входе и выходе из состояния. Такую возможность легко предоставить, используя тот же подход стратегий. Функции входа и выхода из состояний удобно определять для класса, представляющего конкретное состояние. Вспоминая о требовании 5, дадим возможность гибкого управления такой возможностью. Предполагая, что функции класса состояния будут называться OnEnter и OnExit, можно написать несколько готовых функторов: не вызывающий ни одну из функций, вызывающий только OnEnter, вызывающий только OnExit и вызывающий обе функции.

Стратегию по умолчанию (не вызывать никакую функцию) можно передать в качестве аргумента шаблона. Стратегия вызова функций, скорее всего, будет меняться чаще, чем стратегия действий при неизвестном событии. Поэтому ее имеет смысл поместить в списке аргументов перед стратегией реакции на неизвестное событие:

Еще один вопрос, связанный с событиями, состоит в том, что событие может быть сгенерировано внутри функции, вызываемой при выходе или входе в состояние. Для обработки таких событий надо соответствующим образом спроектировать функцию, принимающую событие. С учетом таких “внутренних” событий, надо предусмотреть очередь, в которую будут помещаться события. Код, который обрабатывает переходы, должен будет делать это до тех пор, пока очередь не опустеет. В качестве контейнера, подходящего для хранения событий, воспользуемся deque из STL. Поскольку нам нужны только вставка элементов в начало и исключение из конца контейнера, без произвольного доступа, контейнер deque подойдет лучше всего.

Осталось совсем немного. Иногда нужно привести автомат в исходное состояние. Как и в случае с событиями предусмотрим два варианта: обычная функция и перегруженный operator <<. Для перегруженного operator << нужно определить специальный манипулятор:

Результатом работы автомата является состояние, в которое он перешел. Для получения текущего состояния напишем функцию и перегрузим оператор вывода в поток класса автомата:

Как уже говорилось, для сокращения времени набора кода и удобочитаемости определены несколько макросов. Они требуют предварительного определения подстановки для типов событий и состояний. Требование связано с тем, что использование вложенных директив препроцессора невозможно. Шаблон же использует Proxy классы, которым также нужны сведения о типах. Поэтому для использования макросов придется сделать так:

Альтернатива есть: полностью указывать все типы.

Осталось поместить шаблон в пространство имен. После этого им можно пользоваться.

Пример использования шаблона

Напишем код для решения поставленной в начале статьи задачи.

В примере намеренно опущены такие детали, как обработка исключений и введение функций, вызываемых при входе и выходе из состояния. Чтобы продемонстрировать возможность определения стратегий пользователя, в конструкторе MyMachine указаны все параметры, включая параметры по умолчанию.

Требования к клиентским приложениям

Требования немногочисленны. Для классов событий и состояний должны быть определены operator==, operator= и конструктор копирования. operator== используется для поиска событий и состояний в списках алгоритмом STL find. operator= используется при копировании элементов списков. Конструктор копирования используется при инициализации списков и других элементов.

Если клиент пользуется предоставленным функтором для вызова функций входа и выхода, то класс состояния должен реализовывать соответствующие функции: OnExit и OnEnter.

Преимущества и недостатки предложенного решения

Преимущества:

Шаблон строго типизирован. Это означает, что неправильно написанный код не будет принят компилятором, и ошибка не дойдет до времени выполнения программы.

Расширены понятия состояния и события. Теперь это произвольные классы, написанные пользователем.

Не используется оператор reinterpret_cast<…>, способный привести к неправильным результатам.

Все описание автомата сосредоточено в одном месте. Нет привязки к последовательности описания реакций на события.

Гибкость поведения определяется пользовательскими функторами. Предоставляется набор уже готовых функторов.

Возможно динамическое создание описания конечного автомата. Например, можно создать экземпляры Proxy-классов, прочитать из файла описание автомата, а затем создать экземпляр SFiniteStateMachine.

Нет операций создания и удаления объектов с помощью операторов new и delete.

Нет никаких требований к классам состояний и событий (кроме возможности их сравнения).

Недостатки:

Много операций копирования при создании автомата. Однако этот недостаток отчасти компенсируется тем, что обычно автомат создается один раз, а используется многократно.

Надо писать две директивы препроцессора или использовать длинный префикс. Однако это лишь проблема набивки текста.

Лично я готов мириться с этим коротким списком недостатков ради полученных преимуществ.

Возможные пути усовершенствования шаблона

Внимательный читатель заметит, что можно увеличить гибкость и повысить производительность шаблона. В следующем списке перечислены улучшения, лежащие на поверхности:

Можно отказаться от промежуточного класса SFiniteStateMachineProxy. Это позволит сэкономить на копированиях, но внесет потенциальную возможность неправильного использования шаблона.

Можно ввести манипуляторы, которые позволят в явном виде при описании переходов указывать такие, которые надо игнорировать, или генерировать исключение при их появлении.

Потоковая безопасность

В шаблоне используются контейнеры STL, операции с которыми в многопоточной среде могут привести к проблемам. Поскольку при проектировании шаблона ставилась цель разработать независимое от платформы решение, то никаких средств синхронизации в шаблоне нет. Наличие средств синхронизации, как известно, в зависимости от ситуации может быть как достоинством, так и недостатком. Если они не нужны, их наличие только породит дополнительные накладные расходы. Добавить же средства синхронизации в шаблон опытному разработчику не составит труда.

Список литературы

C/C++ User’s Journal, May 2000

Booch G., Rumbaugh J., Jacobson I. The Unified Modeling Language User Guide. Addison-Wesley, 2001

Meyers S. Effective STL. Addison-Wesley, 2001

Alexandrescu A. Modern C++ Design. Addison-Wesley, 2002

Lewis P., Rosenkrantz D., Stearns R. Compiler Design Theory. Addison-Wesley, 1976

Schildt H. С/С++ Programmer’s Reference. Second Edition. Williams, 2000

Meyers S. Effective C++. Second Edition. Addison-Wesley, 1998 and More Effective C++. Addison-Wesley, 1996

Sutter G. Exceptional C++. Addison-Wesley, 2002