Простая структура данных

Материал из Википедии — свободной энциклопедии
(перенаправлено с «Простой тип данных»)
Перейти к: навигация, поиск

Простая структура данных (англ. plain old data, POD) — в современных языках программирования высокого уровня тип данных, имеющий жёстко определённое расположение полей в памяти, не требующий ограничения доступа и автоматического управления. Переменные такого типа можно копировать простыми процедурами копирования участков памяти наподобие memcpy. Противоположность — управляемая структура данных.

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

Преимущества простых структур данных[править | править вики-текст]

Простые структуры данных имеют две особенности.

Предсказуемое устройство в памяти[править | править вики-текст]

Компилятор может автоматически перестроить структуру данных по своему усмотрению (например, изменить порядок полей. В языке C++ это возможно только в случае, если между полями есть метка доступа public/private/protected. Последовательность полей, не разделенных такой меткой, обязана размещаться в памяти в порядке объявления полей). Подобная перестройка может серьёзно сэкономить память, но нарушает совместимость. В POD’ах такая оптимизация отключена.

Другими словами: типы, отмеченные как POD, устроены в памяти в точности так, как описал программист (возможно, с некоторым выравниванием). Поэтому только POD’ы можно использовать для связи между двумя библиотеками времени выполнения. В частности — для передачи данных из программы в программу, из плагина в плагин, для связи с кодом, написанным на другом языке программирования. Чтобы быстро записать на диск сложный заголовок файла наподобие BMP, можно сформировать его в памяти, а затем записать одной командой — но структура данных, в которой формируем заголовок, также должна быть POD’ом.

Отсутствие управляющего кода[править | править вики-текст]

Это значит, что при появлении объекта не нужно вызывать конструктор, при копировании — операцию присваивания, а при уничтожении — деструктор. Это, в свою очередь, даёт следующие преимущества:

  1. Статическая инициализация. Вместо того, чтобы при запуске программы скрытно от программиста вызывать конструктор, POD’ы можно собрать ещё при компиляции программы.
  2. Тривиальное копирование (в том числе копирование массивов) функциями наподобие memcpy.
  3. Опять-таки, это важно для связи между программами: ведь менеджер памяти не должен заниматься управлением в той памяти, которая ему не принадлежит.
  4. Только простые типы могут находиться в union (в Паскале соответственно record/case).
  5. Функции с побочным эффектом (наподобие системных функций, которые влияют на результат последующего вызова GetLastError[1]) плохо совместимы с автоматически управляемыми типами.

Языки, в которых все типы являются простыми[править | править вики-текст]

В C++[править | править вики-текст]

В C++ POD определяется от противного. Тип данных является POD’ом, если:

  • у него нет конструктора, деструктора и копирующей операции присваивания (то есть operator=, принимающего на входе тот же тип);
  • среди нестатических полей нет ссылок C++, не-POD’ов, private и protected;
  • нет виртуальных методов;
  • все его базовые классы, если таковые имеются, тоже являются PODами.

По стандарту C++ простой тип данных устроен в точности так, как описано (и полностью совместим побайтно по раскладке в памяти со структурой C). Управляемую же структуру компилятор может реорганизовать так, как он сочтёт наиболее эффективным (нет, не может. В стандарте C++ прописано, что последовательность полей, не разделенных меткой доступа, обязана укладываться в память в порядке объявления. Другое дело, что компилятор может добавить в структуру невидимые метаданные, например указатели на таблицы виртуальных методов и виртуальных баз, но к эффективности это отношения не имеет).

Определение POD до C++ 11:

Агрегатом называется либо массив, либо же класс, не имеющий:

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

Агрегат можно инициализировать (как в Си) списком вида = {1, 2, 3};

Скаляром называется:

  • число
  • указатель
  • "указатель на член" (ptom, в синтаксисе C::* ptom)
  • enum
  • std::nullptr_t

(то есть тип, который не есть класс, массив или ссылка)

PODом называется либо скаляр, либо массив других PODов, либо класс, который является агрегатом, и кроме того:

  • все нестатические поля есть PODы
  • нет полей-ссылок
  • нет явно написанного operator=()
  • нет явно написанного деструктора

В C++11[править | править вики-текст]

«Предсказуемое устройство в памяти» и «отсутствие управляющего кода» — сходные, но разные свойства типа. Например, структуру данных STRRET,[2] которая в Windows служит для передачи строк из одного менеджера памяти в другой, можно «обернуть» в управляющий код, но второе свойство — предсказуемое устройство — остаётся. Поэтому концепция POD’ов в C++11 разделена на три.

Класс называется "имеющим тривиальный конструктор копирования", если верно все перечисленное ниже:

  • конструктор копирования автосгенерирован (НЕ написан явно)
  • в классе нет виртуальных методов
  • у класса нет виртуальных базовых классов
  • все базовые классы, а также все поля классовых типов, также имеют тривиальный конструктор копирования.

Автосгенерированный тривиальный конструктор копирования есть memmove().

Точно таким же образом определяются понятия "имеющий тривиальный конструктор умолчания/оператор присваивания/конструктор перемещения/оператор перемещения".

Класс называется "имеющим тривиальный деструктор", если верно все перечисленное ниже:

  • деструктор автосгенерирован (НЕ написан явно)
  • деструктор не виртуален (по всей цепочке наследования, конечно же)
  • все базовые классы, а также все поля классовых типов, также имеют тривиальный деструктор.

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

Класс называется "тривиально копируемым", если у него тривиальны все вышеперечисленные специальные функции-члены (кроме конструктора умолчания, который может быть нетривиален). Скаляры, а также массивы тривиально копируемых объектов, тоже тривиально копируемы. Такие типы могут копироваться через memcpy.

Класс называется "тривиальным", если он тривиально копируем и у него к тому же тривиален конструктор умолчания.

Иными словами, класс является тривиальным, если у него тривиальны:

Класс является типом со стандартным устройством, если:

  • все нестатические поля имеют одинаковые права доступа (все private, все protected или все public).
  • нет виртуальных методов, виртуального наследования.
  • нет нестатических полей-ссылок
  • все нестатические поля и базовые классы также есть "типы со стандартным устройством".
  • не имеет базовых классов с нестатическими полями, или же не имеет нестатических полей в себе самом, при этом имея не более одного базового класса с нестатическими полями (иными словами, все нестатические поля объявлены в одном-единственном классе во всей иерархии наследования).
  • не имеет базовых классов того же типа, что первое нестатическое поле.

Поясним последнее условие: в языке не может быть двух разных объектов одного типа с одинаковым адресом, из чего следует, что размер пустого (без нестатических полей) класса не может быть 0 (как минимум 1). Однако для "части B в классе class D : B" сделано исключение, и ее размер (если она пуста) может строго равняться нулю, что приводит к отсутствию каких-либо "прокладок" между началом D и его первым полем. Но при этом, если тип первого поля тоже B, исключение применяться не может, ибо (B*)&d и &(d.field1) указывают на разные объекты одного и того же типа, и потому "прокладка" нужна. Последнее условие из списка выше означает не более чем "в классах стандартного устройства таковая прокладка запрещена".

У таких типов предсказуемое устройство в памяти (например, адрес объекта как целого совпадает с адресом его первого поля, естественно, после reinterpret_cast в один и тот же тип, например в void*), их можно передавать в другую библиотеку времени выполнения и в другие языки программирования.

Тогда POD — это массив других PODов, или скаляр, или тривиальный класс со стандартным устройством, все нестатические поля которого тоже POD’ы.

Для работы с константами, вычисляемыми при компиляции, и статической инициализации в C++11 есть более мягкое понятие — литеральный тип. А именно:

  • либо тривиальный конструктор по умолчанию T(), либо какой-нибудь конструктор (кроме конструктора копирования и перемещения) отмечен как constexpr;
  • конструктор копирования T(T&) тривиальный;
  • конструктор перемещения T(T&&) тривиальный или запрещён;
  • тривиальный деструктор ~T();
  • унаследован от литеральных типов;
  • все его нестатические поля литеральные.

PODы и инициализация "по умолчанию" и "значением"[править | править вики-текст]

Начиная с C++ 03, существует разница между записями T t; и T t();, а равно между new T и new T().

Версия с пустыми скобками называется "инициализация значением", а без них - "инициализация по умолчанию".

Инициализация по умолчанию: если конструктор умолчания тривиален, то не делается ничего, в объекте остается мусор. Если же конструктор умолчания нетривиален, то он исполняется.

Инициализация значением: если есть явно написанный конструктор умолчания, то он исполняется. Если же нет (т.е. если конструктор умолчания тривиален или же сгенерирован автоматически), то объект сначала зануляется, и только потом исполняется конструктор (если он нетривиален). Скалярные типы при инициализации значением зануляются.

В Embarcadero Delphi[править | править вики-текст]

Простыми структурами данных считаются все типы, кроме:

  • новых строк неограниченной длины (AnsiString, WideString, UnicodeString). Впрочем, если не задевать скрытые управляющие поля, а работать только с данными, System.Copy использовать можно — не забывая, конечно, что несколько строк могут ссылаться на одну память и прежде надо вызвать функцию UniqueString;
  • интерфейсов COM;
  • динамических массивов;
  • типов, которые содержат один из упомянутых трёх;
  • новых объектов типа class. Впрочем, TObject, TButton и т. д. — это указатели на объект и всегда являются простыми типами!

Примечания[править | править вики-текст]

См. также[править | править вики-текст]