Реферат 2
Введение 5
1 Постановка задачи 7
2 Контейнеры в STL 8
3 Последовательные контейнеры 10
4 Ассоциативные контейнеры 12
5 Проектирование пользовательской структуры 14
6 Функциональный интерфейс 18
7 Шаблон структуры 20
8 Оценка сложности базовых функций 22
9 Обобщенные алгоритмы для работы с суперпозицией контейнеров ... 52
10 Тестирование структуры 54
11 Структура программы 59
Заключение 70
Список литературы 71
Работа с разными структурами данных является неотъемлемой частью разработки программного обеспечения. Сложность реализации и качество работы программ существенно зависит от их правильного выбора. Это понимание дало начало языкам программирования, в которых именно структуры данных, а не алгоритмы, ставятся во главу архитектуры программного средства. Большая часть таких языков обладает определённым типом модульности, позволяющим структурам данных безопасно переиспользоваться в различных приложениях. Объектно-ориентированный язык C++ является примером такого подхода.
В настоящее время для языка C++ имеются библиотеки, в которых реализованы основные структуры и алгоритмы работы с ними, в частности Стандартная Библиотека Шаблонов (Standard Template Library (STL)). Для каждой структуры данных в STL определен ряд стандартных функций. Они имеют разные реализации, которые эффективно использовать для различных задач. Основные из них это функции вставки, удаления и поиска элементов, а также функции, которые реализуют доступ к элементам. От их выбора существенно зависит время работы алгоритма, так как они предлагают различные компромиссы в сложности выполнения.
Использование данной библиотеки позволяет значительно повысить универсальность программ и их переносимость, а также её использование ускоряет разработку конечного продукта.
Чаще всего приходится из основных структур STL проектировать свои составные структуры. Целью данной работы будет разработка программы, которая при помощи визуальных средств позволит делать это автоматически. Результатом её работы будет библиотека для языка C++, в которой будет содержаться реализация пользовательской структуры данных.
Так как в библиотеке будет составная структура, то необходимо учитывать особенности всех включенных в неё контейнерных классов. Выбирая различные способы работы с каждой структурой, можно сильно влиять на работу всей суперпозиции в целом. Чтобы обеспечить приемлемую сложность выполнения базовых операций в составной структуре, необходимо комбинировать предложенные стандартные функции в зависимости от текущей ситуации. Таким образом, нужно реализовать такие алгоритмы работы с полученной структурой, которые бы учитывали многие её особенности. Очевидно, что эти алгоритмы будут работать медленнее по сравнению с работой стандартных алгоритмов в наилучших и худших случаях. С другой стороны, можно обеспечить улучшенную работу по сравнению со стандартной работой алгоритмов в средних случаях.
В результате данной работы реализовано инструментальное программное средство, позволяющее проектировать структуры данных. Эти структуры базируются на выбранных контейнерах из STL и имеют минимальный набор функций для работы с ними. В результате проектирования мы получаем библиотеку для языка C++, которую очень просто подключить к проекту и использовать свою структуру любым образом. При создании кода структуры учитываются особенности используемых контейнеров для увеличения скорости работы. Эти особенности подтвердились в результате тестирования всех базовых функции рассматриваемых контейнеров из Стандартной библиотеки шаблонов. На этих результатах предложены алгоритмы работы с суперпозицией этих контейнеров. Эти алгоритмы учитывают основные особенности входящих контейнерных классов, позволяя обеспечить улучшенную работу по сравнению с работой стандартных алгоритмов в средних случаях.
