Свойство|_|_|_|_
--|--|--|--|--
Изменяемость | Неизменяемые объекты\
String в Java| Изменяемые объекты\
std::string в C++|
Порядок\
первый/последний,\
следующий/предыдущий (опционально)|Определяется программистом\
Список, Очередь|Определяется значениями\
Очередь с приоритетами|Не важен\
Множество, Таблица в базе данных
Доступ к элементам|Последовательный,\
через итератор\
Список|Произвольный, по номеру\
Массив|Произвольный, по ключу\
Словарь|Частичный\
Стек (только верхний элемент)
Модель|Линейный (одномерный)\
Список, Очередь с приоритетами|Многомерный\
Матрица|Нелинейный\
Граф, DOM для HTML
Модель АТД не связана с используемыми для представления структурами данных. Модель служит для объяснения поведения АТД, а не требованиями к реализации. Например, линейный АТД Двухсторонняя очередь в C++ реализуется через нелинейные структуры данных, чтобы минимизировать количество операций с динамической памятью в критических приложениях. Нелинейный АТД Граф может быть реализован через матрицу смежности или список ребер, и выбор наиболее эффективного варианта будет зависеть от реализуемого алгоритма.
Также название АТД не означает, что используется одноименный (с соответствующим английским названием) класс (тип) из языка программирования, и не означает, что операции будут вызываться одинаково.
Для создания массива в языке C нужно написать\
``int a[100];``\
а в С++ нужно использовать\
``std::vector<int> a(100);``\
``std::array<int,100> a;``
Для получения размера массива в C++ нужно написать ``a.size()``, а в C -- ``(sizeof(a)/sizeof(a[0]))``. Совпадает только операция доступа к элементу: ``a[i]``.
Но программист может определить свою реализацию АТД Массив, в котором для получения размера нужно писать ``a.length``, а для получения элемента ``a.at(i)``.
С другой стороны, класс STL может поддерживать операции нескольких АТД: ``std::vector`` может использоваться как Стек, Массив и Список.
Начало
Учебные материалы
Абстракция и разработка программ