Абстракция и разработка программ

Абстрактный тип данных (АТД) — это математическая модель для типов данных, где тип данных определяется поведением (семантикой) с точки зрения пользователя данных, а именно в терминах возможных значений, возможных операций над данными этого типа и поведения этих операций.

Формально АТД может быть определён как множество объектов, определяемое списком операций, применимых к этим объектам, и их свойств. Вся внутренняя структура такого типа спрятана от разработчика программного обеспечения – в этом и заключается суть абстракции.

Конкретные реализации АТД называются структурами данных.

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

С другой стороны, классы STL не являются АТД, так как стандартом С++ операциям предписывается заданная эффективность, которая подразумевает использование для реализации определенных структур данных, а в некоторых классах – специальные методы для управления этими структурами. Для изменения выбора с одного классов STL на другой или собственную, более эффективную структуру данных может потребоваться существенная переделка кода.

Примером АТД в STL можно считать стек:

template<
    class T,
    class Container = std::deque<T>
> class stack;

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

• back()
• push_back()
• pop_back()

В качестве контейнера подходят vector, deque и list. Для изменения выбора достаточно поменять объявление объекта.

У такой реализации АТД через шаблон есть существенный недостаток. Так как stack является адаптером объекта, а не адаптером класса, то не выполняется принцип подстановки Барбары Лисков, и нужно менять не только объявление стека, но и заголовки всех функций, которым передается этот стек, или делать их шаблонными функциями.