Требования к библиотеке базовых классов
Библиотека должна содержать универсальные структуры данных и алгоритмы, способные удовлетворить потребности большинства стандартных приложении C++. Кроме того, библиотека должна быть:
| • Полной | Библиотека должна содержать семейство классов, объединенных согласованным внешним интерфейсом, но с разными представлениями, так чтобы разработчики могли выбрать то, семантика которого наиболее точно соответствует приложению. |
| • Адаптируемой | Все фрагменты кода, зависящие от платформы, должны быть выделены и изолированы в отдельные классы для обеспечения возможности локальных изменений в них. В частности, разработчик должен иметь контроль над механизмами хранения данных и синхронизации процессов. |
| • Эффективной | Процедура подключения различных фрагментов библиотеки к приложению должна быть простой (эффективность при компиляции). Непроизводительные затраты оперативной памяти и процессорного времени на обслуживание и подключение должны быть сведены к минимуму (эффективность при исполнении). Библиотека должна обеспечивать более надежную работу, чем механизмы, разработанные пользователем вручную (эффективность при разработке). |
| • Безопасной | Каждая абстракция должна быть безопасной с точки зрения типов, так чтобы статические предположения о поведении класса могли быть обеспечены компилятором. Для выявления нарушений динамической семантики классов должен быть использован механизм исключений. Возбуждение исключения не должно испортить состояние объекта, вызвавшего исключение. |
| • Простой | Библиотека должна иметь прозрачную структуру, дающую возможность пользователю легко находить и подключать к приложению ее фрагменты. |
| • Расширяемой | Для пользователя должна быть реализована возможность включения в библиотеку новых классов. При этом архитектурная целостность среды разработки не должна нарушаться. |
Библиотека должна быть относительно небольших размеров; надо всегда помнить, что пользователь с большей охотой займется разработкой собственного кода, чем изучением чужого малопонятного класса.
Предполагается наличие трансляторов языка C++, поддерживающих параметризованные классы и обработку исключений. В целях обеспечения переносимости библиотеки она не должна зависеть от служб операционной системы.
Таким образом, первым результатом нашего анализа будет разделение всех абстракций на две категории:
| • Структуры | Содержит все структурные абстракции. |
| • Инструменты | Содержит все алгоритмические абстракции. |
Как мы скоро увидим, между этими двумя категориями существует отношение использования: некоторые инструменты построены на базе более примитивных свойств, обеспечиваемых структурами.
На втором этапе анализа мы постараемся выделить базовые классы, которые могут быть использованы в различных стандартных программах (чем шире будет круг рассмотренных приложений, тем лучше). Если в результате окажется, что некоторые из данных классов имеют много общего с абстракциями, определенными на первой стадии анализа, это будет знаком того, что ключевые абстракции были выявлены правильно. Можно составить длинный список специфических абстракций, присущих конкретным видам человеческой деятельности: валюта, астрономические координаты, единицы измерения массы и длины. Мы не будем включать подобные абстракции в нашу библиотеку, так как они либо слишком плохо поддаются формализации (валюта), либо очень специфичны (астрономические координаты), либо настолько примитивны, что нет смысла организовывать специально для них отдельные классы (единицы измерения массы и длины).
Проведя анализ, мы выделим следующие типы структур:
| • Набор | Множество различных элементов (в том числе дубликатов). |
| • Множество | Набор неповторяющихся элементов. |
| • Коллекция | Индексируемое множество элементов. |
| • Список | Последовательность элементов, имеющая начало; структурное разделение допускается. |
| • Стек | Последовательность элементов; элементы могут удаляться и добавляться только с одного конца. |
| • Очередь | Последовательность элементов, к которой можно добавлять элементы с одного конца, а удалять - с другого. |
| • Дека | Последовательность элементов, к которой можно добавлять и из которой можно удалять элементы с обоих концов. |
| • Кольцо | Последовательность элементов, к которой можно добавлять и из которой можно удалять элементы, находящиеся на вершине круговой структуры. |
| • Строка | Индексируемая последовательность элементов, в которой возможны операции с подстроками. |
| • Ассоциативный массив | Словарь пар "элемент/значение". |
| • Дерево | Набор (имеющий начало - корень дерева) вершин и ребер, которые не могут образовывать циклы и пересекаться; структурное разделение допускается. |
| • Граф | Множество вершин и ребер (без выделенного начального элемента), которое может содержать циклы и пересечения; структурное разделение допускается. |
Как уже говорилось в главе 4, упорядочение представленных выше абстракций есть проблема классификации. Мы выбрали именно такую модель из-за того, что она обеспечивает закрепление определенного поведения за каждой категорией объектов.
Обратите внимание на типы поведения, которые использовались в качестве критериев при разбиении на классы: некоторые структуры ведут себя как коллекции (наборы и множества), а другие - как последовательности (деки и стеки). В некоторых структурах (графы, списки и деревья) возможно структурное разделение, в то время как остальные более монолитны и не допускают структурного разделения своих элементов. Как мы увидим далее, подобная классификация поможет в дальнейшем сформировать достаточно простую архитектуру системы.
Для некоторых классов в процессе анализа выявилась желательность их функциональной изменчивости. В частности, нам могут понадобиться упорядоченные коллекции, деки и очереди (последние часто называют приоритетными очередями). Кроме того, мы можем различать ориентированные и неориентированные графы, односвязные и двусвязные списки, бинарные, множественные и AVL-деревья [AVL-дерево - предложенная Г.М.Адельсон-Вольским и Е.М.Ландисом конструкция подравниваемого бинарного дерева. - Примеч. ред.]. Эти специализированные абстракции могут быть получены уточнением одной из вышеперечисленных; их не следует выделять в отдельные большие категории.
Несмотря на то, что мы уже обнаружили признаки общности поведения, мы пока не будем заниматься проработкой иерархической структуры. На этапе анализа важно разобраться в ролях каждой абстракции.
Мы выделим следующие типы инструментов:
| • Дата/Время | Операции с датой и временем. |
| • Фильтры | Ввод, обработка и вывод. |
| • Поиск по образцу | Операции поиска последовательностей внутри других последовательностей. |
| • Поиск | Операции поиска элементов внутри структур. |
| • Сортировка | Операции упорядочивания структур. |
| • Утилиты | Составные операции, базирующиеся на базовых структурных операциях. |
Несомненно, существует масса различных функциональных вариантов этих абстракций. Можно, например, выделить несколько видов сортировок (быстрая сортировка методом пузырька, сортировка кучи и т.д.) или поиска (последовательный, двоичный, различные способы обхода дерева и т.д.). Как и раньше, мы отложим решения относительно наследования этих абстракций.
