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

Использование STL контейнера vector. Производительность vector-а
Использование контейнеров стандартной библиотеки C++, всегда обусловлено простотой и удобством, производительностью. Но как и всякий "инструмент" его нужно использовать правильно, ведь хороший и эффективный инструмент в неумелых руках может быть бесполезен или неэффективен. В этой небольшой статье, я поведаю, как его использовать максимально эфективно и какие проблемы, подводные камни могут возникнут при первом знакомстве.

Начнем пожалуй с самого истока
STL - стандартаная библиотека шаблонов. То есть, все то, что в стандартной библиотеке выражено шаблоном(ами), и есть STL. Но по большей части STL-ем принято считать именно контейнеры, алгоритмы и итераторы.
STL уже давно вошла в стандартную библиотеку C++, но все же не все пользуются ей в полной мере во основном из-за незнания о существовании тех или иных шаблонных классов.

И так вернемся конкретно к вектору.
Контейнер vector - это то же массив, который может содержать в себе любой встроенный или пользовательский тип. Но по сравнению со встроенным массивом у него есть ряд преимуществ.

Он сам знает свой размер, (метод size())
- Можно легко менять размер(добавлять, удалять элементы), во время выполнения
- При удалении, очистки он вызывает деструкторы классов(ну это преимущество спорно=))

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

    push_back(element) - добавить элемент в конец vector-а
    pop_back(element) - удалить последний элемент vector-а
    insert(***) - три варианта(перезагрузки метода) вставки в какую либо область в векторе, первый параметр позиция вставки заданная итераторам, остальные указывают на контейнер, или количество и контейнер, или пару итераторов указывающих от какой до какой позиции из другого контейнера взять данные.
    erase(iterator или iterator от, и до) - удаляет элемент или последовательность элементов из vector-а
    begin() - возвращает итератор, указывающий на начало коллекции.
    end() - возвращает итератор, указывающий на конец коллекции. При этом он указывает не самый последний элемент, а на воображаемый элемент за последним.
    at(index) - метод доступа, к элементам коллекции, в отличии от оператора , проверяет выход из-за границ коллекции, и в случаи чего генерит исключение.
    clear() - удаляет все элементы коллекции, при этом если в нем содержаться объекты классов вызывает их деструкторы. А если же указатели на объекты, то у Вас будет утечка памяти(memory leaks=)), так delete за Вас никто не вызовет.
Пора увидеть его в действии!

При переборе вектора через итераторы, нужно приучить себя писать преинкремент(++it ), так он эфективнее .

Создание статического вектора:

Самый частый случай, проблем с созданием статического вектора - создание его в классе.
Чтобы создать в классе статический вектор, нужно его описать в.h и определить в.cpp. В данном случаи я поместил все в один файл, только ради простоты. Так можно создавать не только статический вектор, но и любой другой статический контейнер.

Теперь об эффективности

Вектор эффективен, в случаях если Вам нужен контейнер, в которые вы будете накапливать элементы. То есть - добавлять. Вектор эффективен при добавлении в конец методом push_back(), и при удалении с конца pop_back().
При вставке или удалении в произвольном месте (методы insert() и erase()), эффективность вектора хуже в сравнении со списком(list ) или двусторонней очередью(deque ). Связанно это с тем что, вектор хранит данные в памяти последовательно , что дает быстрый произвольный доступ и возможность использовать вектор, как обычный массив. К примеру в те же функции OpenGL вместо указателя на C массив, можно указать &имя_вектора.
У вектора есть не только размер(size()), но и емкость(capacity()), емкость это максимальное количество элементов которые при добавлении не вызовет переспраделении внутреннего буфера. При превышении этого значения вектор выделяет новый внутренней буфер(allocator), и копирует все элементы из старого буфера в новый, удаляя при этом из старого. То, есть если мы храним в нем большие объекты классов, то это операция будет довольно дорогостоящая. Особенно остро это "почувствуется" на больших объектах со сложным деструктором.
Емкость задана самой реализацией стандартной библиотеки.

Если же хранит в векторе указатели на объекты, то это очень повышает эффективность хранения в векторе, особенно больших объектов.
Хранить не большие объекты или встроенные типы в векторе, довольно эффективно.

Вывод
Если вы не собираетесь часто удалять элементы контейнера, и Вам не нужно вставлять элементы в начало и середину. И Вы собираетесь хранить не большие объекты, встроенные типы, или указатели на любые объекты(большие или не очень=)). То лучше предпочесть вектор, и помнить какие операции с ним, что делают, внутри него, в том числе. И какие из них будут не слишком дорогостоящие.

Понравилась публикация? Сохраните ее, чтобы вернуться к изучению материала!

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

Предисловие

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

Доктор Зюсс, «Как Гринч украл Рождество»

Я впервые написал о 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, особенно важные для профессиональных программистов.

Скотт Дуглас Мейерс Стаффорд, Орегон Апрель 2001 г.

Благодарности

За годы, которые потребовались на то, чтобы разобраться в STL, разработать учебный курс и написать эту книгу, я получил неоценимую помощь и поддержку от множества людей. Хочу особо отметить Марка Роджерса (Mark Rodgers), великодушно предложившего просматривать материалы учебного курса по мере их написания. От него я узнал об STL больше, чем от кого-либо другого. Марк также выполнял функции технического редактора этой книги, а его замечания и дополнения помогли улучшить практически весь материал.

Другим выдающимся источником информации были конференции Usenet; посвященные языку C++, особенно comp.lang.c++.moderated («clcm»), comp.std.c++ и microsoft.public.vc.stl. Свыше десяти лет участники этих и других конференций отвечали на мои вопросы и ставили задачи, над которыми мне приходилось думать. Я глубоко благодарен сообществу Usenet за помощь в работе над этой книгой и моими предыдущими публикациями по C++.

Мое понимание STL формировалось под влиянием ряда публикаций, самые важные из которых перечислены в конце книги. Особенно много полезного я почерпнул из труда Джосаттиса «The C++ Standard Library» .

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

В совете 1 замечание о том, что узловые контейнеры обеспечивают лучшую поддержку транзакционной семантики, позаимствовано из раздела 5.11.2 «The C++ Standard Library» . Пример использования typedef при изменении типа распределителя памяти из совета 2 был предложен Марком Роджерсом. Совет 5 вдохновлен статьeй Ривса (Reeves) «STL Gotchas» . В основу совета 8 заложен совет 37 книги Саттера «Exceptional C++» , а Кевлин Хенни (Kevlin Henney) предоставил важную информацию о проблемах, возникающих при использовании контейнеров auto_ptr. В конференциях Usenet Мэтт Остерн (Matt Austem) предоставил примеры использования распределителей памяти, включенные мной в совет 11. Совет 12 основан на материалах сайта SGI STL , посвященных потоковой безопасности. Информация о подсчете ссылок в многопоточной среде из совета 13 почерпнута из статьи Саттера . Идея совета 15 была подсказана статьей Ривса «Using Standard string in the Real World, Part 2» . Методика непосредственной записи данных в vector , продемонстрированная в совете 16, была предложена Марком Роджерсом. В совет 17 была включена информация из Usenet, авторы - Симел Наран (Siemel Naran) и Карл Баррон (Carl Barron). Совет 18 был позаимствован из статьи Саттера «When Is a Container Not a Container?» . Для совета 20 Марк Роджерс предложил идею преобразования указателя в объект посредством разыменования, а Скотт Левандовски (Scott Lewandowski) разработал представленную версию DereferenceLess. Совет 21 основан на сообщении Дуга Харрисона (Doug Harrison) в конференцию microsoft.public.vc.stl, но решение о том, чтобы ограничить рамки этого совета проблемой равенства, принял я сам. Совет 22 основан на статье Саттера «Standard Library News: sets and maps» . Совет 23 был подсказан статьей Остерна «Why You Shouldn"t Use set - and What to Use Instead» ; Дэвид Смоллберг (David Smallberg) усовершенствовал мою реализацию DataCompare. Описание хэшированных контейнеров Dinkumware основано на статье Плаугера (Plauger) «Hash Tables» . Марк Роджерс не согласен с выводами совета 26, но первоначально этот совет был подсказан его замечанием относительно того, что некоторые функции контейнеров принимают только аргументы типа iterator. Работа над советом 29 вдохновлялась дискуссиями в Usenet с участием Мэтта Остерна и Джеймса Канце (James Kanze); на меня также повлияла статья Клауса Крефта (Klaus Kreft) и Анжелики Лангер (Angelika Langer) «А Sophisticated Implementation of User-Defined Inserters and Extractors» . Совет 30 основан на материалак раздела 5.4.2 книги Джосаттиса «The C++ Standard Library» . В совете 31 Марко Далла Гасперина (Marco Dalla Gasperina) предложил пример использования nth_element для вычисления медианы, а использование этого алгоритма для поиска процентилей взято прямо из раздела 18.7.1 книги Страуструпа (Stroustrup) «The C++ Programming Language». Совет 32 был вдохновлен материалами раздела 5.6.1 книги Джосаттиса «The C++ Standard Library». Совет 35 появился под влиянием статьи Остерна «How to Do Case-Insensitive String Comparison» , а сообщения Джеймса Канце и Джона Поттера (John Potter) помогли мне лучше разобраться в сути происходящего. Реализация copy_if, приведенная в совете 36, позаимствована из раздела 18.6.1 книги Страуструпа «The C++ Programming Language» . В основу совета 39 заложены публикации Джосаттиса, который впервые упомянул о «предикатах с состоянием» в своей книге «The C++ Standard Library» и в статье «Predicates vs. Function Objects» . В своей книге я использую его пример и рекомевдую предложенное им решение, хотя термин «чистая функция» принадлежит мне. В совете 41 Мeтт Остерн подтвердил мои подозрения относительно происхождения имен mem_fun и mem_fun_ref. Совет 42 берет свое начало из лекции, прочитанной мне Марком Роджерсом, когда я нарушил рекомендацию этого совета. Марку Роджерсу также принадлежит приведенное в совете 44 замечание о том, что при внешнем поиске в контейнерах map и multimap анализируются оба компонента пары, тогда как при поиске функциями контейнера учитывается только первый компонент (ключ). В совете 45 использована информация от разных участников clem, среди которых Джон Поттер, Марсин Касперски (Marcin Kasperski), Pete Becker (Пит Бекер), Деннис Йель (Dennis Yelle) и Дэвид Абрахаме (David Abrahams). Дэвид Смоллберг подсказал мне идею применения equal_range для поиска на базе эквивалентности и подсчета результатов в сортированных последовательных контейнерах. Андрей Александреску (Andrei Alexandrescu) помог разобраться в условиях возникновения проблемы «ссылки на ссылку», упоминаемой в совете 50; приведенный в книге пример основан на аналогичном примере Марка Роджерса, взятом с сайта Boost .


Во многих книгах описываются возможности 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, особенно важные для профессиональных программистов.

Скотт Дуглас Мейерс Стаффорд, Орегон Апрель 2001 г.

Название : Эффективное использование STL.

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


Содержание
Предисловие.9
Благодарности.11
Введение.15
Определение, использование и расширение STL.16
Ссылки.16
STL и Стандарты.16
Подсчет ссылок.17
string и wstring.18
Терминология.18
Примеры.20
Вопросы эффективности.22
Рекомендации.22
Глава 1. Контейнеры. 23
Совет 1. Внимательно подходите к выбору контейнера.23
Совет 2. Остерегайтесь иллюзий контейнерно-независимого кода.27
Совет 3. Реализуйте быстрое и корректное копирование объектов в контейнерах. 31
Совет 4. Вызывайте empty вместо сравнения size() с нулем.33
Совет 5. Используйте интервальные функции вместо одноэлементных.35
Совет 6. Остерегайтесь странностей лексического разбора C++.42
Совет 7. При использовании контейнеров указателей, для которых вызывался оператор new, не забудьте вызвать delete для указателей перед уничтожением контейнера.44
Совет 8. Никогда не создавайте контейнеры, содержащие auto_ptr.48
Совет 9. Тщательно выбирайте операцию удаления.50
Совет 10. Помните о правилах и ограничениях распределителей памяти.54
Совет 11. Учитывайте область применения пользовательских
распределителей памяти.60
Совет 12. Разумно оценивайте потоковую безопасность контейнеров STL.62
Глава 2. Контейнеры vector и string. 66
Совет 13. Используйте vector и string вместо динамических массивов.66
Совет 14. Используйте reserve для предотвращения лишних операций перераспределения памяти.68
Совет 15. Помните о различиях в реализации string.71
Совет 16. Научитесь передавать данные vector и string функциям унаследованного интерфейса.75
Совет 17. Используйте «фокус с перестановкой» для уменьшения емкости.78
Совет 18. Избегайте vector .80
Глава 3. Ассоциативные контейнеры. 83
Совет 19. Помните о различиях между равенством и эквивалентностью.83
Совет 20. Определите тип сравнения для ассоциативного контейнера, содержащего указатели.87
Совет 21. Следите за тем, чтобы функции сравнения возвращали false в случае равенства.91
Совет 22. Избегайте изменения ключа «на месте» в контейнерах set и multiset.93
Совет 23. Рассмотрите возможность замены ассоциативных контейнеров
сортированными векторами.98
Совет 24. Тщательно выбирайте между map::operator и map::insert.103
Совет 25. Изучите нестандартные хэшированные контейнеры.107
Глава 4. Итераторы. 111
Совет 26. Старайтесь использовать iterator вместо const_iterator, reverse_iterator и const_reverse_iterator.111
Совет 27. Используйте distance и advance для преобразования const_iterator в iterator.114
Совет 28. Научитесь использовать функцию base.117
Совет 29. Рассмотрите возможность использования istreambufjterator при посимвольном вводе.119
Глава 5. Алгоритмы. 122
Совет 30. Следите за тем, чтобы приемный интервал имел достаточный размер.123
Совет 31. Помните о существовании разных средств сортировки.127
Совет 32. Сопровождайте вызовы remove-подобных алгоритмов вызовом erase.131
Совет 33. Будьте внимательны при использовании remove-подобных алгоритмов с контейнерами указателей.135
Совет 34. Помните о том, какие алгоритмы получают сортированные интервалы. 138
Совет 35. Реализуйте простые сравнения строк без учета регистра символов с использованием mismatch или lexicographical_compare.141
Совет 36. Правильно реализуйте copy_if.144
Совет 37. Используйте accumulate или for_each для обобщения интервальных данных.146
Глава 6. Функции, функторы и классы функций. 151
Совет 38. Проектируйте классы функторов для передачи по значению.151
Совет 39. Реализуйте предикаты в виде «чистых» функций.154
Совет 40. Классы функторов должны быть адаптируемыми.157
Совет 41. Разберитесь, для чего нужны ptr_fun, mem_fun и mem_fun_ref.161
Совет 42. Следите за тем, чтобы конструкция less означала operator<.164
Глава 7. Программирование в STL. 167
Совет 43. Используйте алгоритмы вместо циклов.167
Совет 44. Используйте функции контейнеров вместо одноименных алгоритмов.174
Совет 45. Различайте алгоритмы count, find, binary_search, lower_bound, upper_bound и equal_range.177
Совет 46. Передавайте алгоритмам объекты функций вместо функций.184
Совет 47. Избегайте «нечитаемого» кода.187
Совет 48. Всегда включайте нужные заголовки.190
Совет 49. Научитесь читать сообщения компилятора.191
Совет 50. Помните о web-сайтах, посвященных STL.198
Сайт SGI STL.198
СайтБПрог!.200
Сайт Boost.201
Литература.203
Книги, написанные мной.203
Книги, написанные другими авторами.204
Ошибки и опечатки.206
Приложение А Локальные контексты.207
Сравнение строк без учета регистра символов.207
Первая попытка.208
Локальный контекст.210
Локальные контексты в C++.211
Фасет collate.212
Сравнение строк без учета регистра.212
Приложение Б Замечания по поводу платформ STL от Microsoft . 216
Шаблоны функций классов в STL.216
MSVC версий 4-6.217
Обходное решение для MSVC4-5.218
Обходное решение для MSVC6.219
Алфавитный указатель.

Помните о правилах и ограничениях распределителей памяти .
Распределители памяти первоначально разрабатывались как абстракция для моделей памяти, позволяющих разработчикам библиотек игнорировать различия между near- и far-указателями в некоторых 16-разрядных операционных системах (например, DOS и ее зловредных потомках), однако эта попытка провалилась. Распределители также должны были упростить разработку объектных диспетчеров памяти, но вскоре выяснилось, что такой подход снижает эффективность работы некоторых компонентов STL.

Чтобы избежать снижения быстродействия, Комитет по стандартизации C++ включил в Стандарт положение, которое практически выхолостило объектные распределители памяти, но одновременно выражало надежду, что от этой операции их потенциальные возможности не пострадают.
Но это еще не все. Распределители памяти STL, как и operator new с operator new, отвечают за выделение (и освобождение) физической памяти, однако их клиентский интерфейс имеет мало общего с клиентским интерфейсом operator new, operator new и даже mall ос. Наконец, большинство стандартных контейнеров никогда не запрашивает память у своих распределителей. Еще раз подчеркиваю - никогда. В результате распределители производят довольно странное впечатление.

Эффективное использование 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 в том или ином виде. Например:

switch (CurrentState)

case State1: if (CurrentEvent == Event1)

if (CurrentEvent == Event2)

case State2:.. .

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

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

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

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

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

Таблица 1.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

SFiniteStateMachine A(

“empty”, “number”, “identifier”, “unknown”,

letter, “identifier”, “unknown”, “identifier”, “unknown”,

digit, “number”, “number”, “identifier”, “unknown”

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

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

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

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

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

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

FSMBEGIN(“empty”)

FSMSTATES “empty” << “number” << “identifier” << “unknown”

FSMEVENT(letter) “identifier” << “unknown” << “identifier” << “unknown”

FSMEVENT(digit) “number” << “number” << “identifier” << “unknown”

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

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

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

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

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

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

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

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

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

template

class SEmptyFunctor

{ return; }

template

class SOnEnterFunctor

inline void operator() (SState & From, const SEvent & Event, SState & To)

{ To.OnEnter(From, Event); }

template

class SOnExitFunctor

inline void operator() (SState & From, const SEvent & Event, SState & To)

{ From.OnExit(Event, To); }

template

class SOnMoveFunctor

inline void operator() (SState & From, const SEvent & Event, SState & To)

{ From.OnExit(Event, To); To.OnEnter(From, Event); }

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

template

class SFunctor = SEmptyFunctor,

class SUnknownEventStrategy = SThrowStrategy >

class SFiniteStateMachine {... };

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

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

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

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

#define FSMStateType string // Типсостояния

#define FSMEventType int // Типсобытия

#undef FSMStateType

#undef FSMEventType

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

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

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

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

#include

#include

using namespace std;

#include «FiniteStateMachine.h»

using namespace FSM;

// Определимтипдлясобытий

enum Events { letter = 0, digit = 1 };

int main(int argc, char ** argv)

#define FSMStateType string

#define FSMEventType Events

SFiniteStateMachine< StateType,

SEmptyFunctor,

SThrowStrategy

FSMBEGIN(«empty»)

FSMSTATES «empty» << «number» << «identifier» << «unknown»

FSMEVENT(letter) «identifier» << «unknown» << «identifier» << «unknown»

FSMEVENT(digit) «number» << «number» << «identifier» << «unknown»

#undef FSMStateType

#undef FSMEventType

cout << «StartState is: » << MyMachine << endl;

MyMachine << digit << digit << letter;

cout << «The "unknown" state is expected. Current state is: » << MyMachine << endl;

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

// правильный порядок выполнения операторов

cout << «Reset the machine. Current state is: » << (MyMachine << ResetMachine) << endl;

MyMachine << letter << digit << letter;

cout << «The "identifier" state is expected. Current state is: » << MyMachine << endl;

В примере намеренно опущены такие детали, как обработка исключений и введение функций, вызываемых при входе и выходе из состояния. Чтобы продемонстрировать возможность определения стратегий пользователя, в конструкторе 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