Пока все хорошо и не видно никаких сложностей. Более того, наш стек «слишком» универсален — он может содержать элементы разного типа!
Однако не все так прекрасно, как представляется. Во-первых, на указатели расходуется дополнительная память. Во-вторых, класс-стек понятия не имеет о реальном типе элементов в контейнере, поэтому не может выдать значение элемента, а вынужден выдавать указатель void *. Дальнейшее разыменование должна делать программа-клиент, обеспечивая еще и преобразование в нужный тип. При этом, конечно, приходится писать не самые красивые выражения.
Но гораздо более важным является то, что программа-клиент теперь обязана следить за памятью, ведь в контейнер помещается только указатель на некоторые данные. Этими данными владеет программа-клиент, и только она «знает», как с ними оперировать. И тут, как обычно это бывает при использовании указателей, может возникнуть множество проблем. Например, в стек вполне можно поместить адрес локальной переменной. Если стек имеет большее время жизни, чем эта переменная, то мы получим висячую ссылку. При использовании такого стека очень просто получить и потерянные ссылки. Если программа-клиент «забудет» освободить память, то при уничтожении стека-переменной (например, при выходе из блока) мы получим утечку памяти. Одним из решений проблем с указателями могут стать интеллектуальные указатели, которые в этой книге не рассматриваются1.
Дек (см. листинги 6.1, 6.2, 6.3) реализован для элементов типа double. Однако по сути дек тоже является универсальным контейнером, работа которого не зависит от типа элементов. К сожалению, использование указателей типа void * приведет к тем же проблемам, что и со стеком. Более того, поскольку в классе TDeque реализован деструктор, существует очень большая опасность получения утечек памяти. Поэтому применение нетипизированных указателей для универсализации дека не является самым лучшим решением.
Таким образом, мы видим, что написать универсальный контейнер, работа которого не зависит от типа элементов, не так-то просто. В С++ есть несколько вариантов решения этой проблемы. Одним из вариантов является наследование (см. главы 8 и 9), другим — шаблоны, включенные в С++ специально для решения такого рода проблем (см. главу 11).
Однако есть один очень простой, но очень полезный прием, который повышает степень универсальности динамических структур данных и позволяет повторно использовать уже разработанные классы с другим типом данных. Если еще раз взглянуть на класс TDeque (см. листинг 6.3), то ни в одном из компонентов класса мы не обнаружим спецификатор типа double. Поэтому явную зависимость класса TDeque от элементов типа double можно уменьшить, использовав оператор typedef:
Описание интеллектуальных указателей можно найти в [20, 25, 26, 28].
typedef double value_type:
После этого компоненты класса, явно зависящие от double, переписываются с типом value_type, например:
// в классе iterator
value_type& operator*() const
{ if (the_elem != 0) return the_elem->itern;
else { cout << "Null iterator!" << endl: abort(); }
}
// в классе TDeque - добавить элемент
void TDeque::push_front(const value_type &a)
{ Elem *p = new Elem(a); // образовали новый элемент
p->next = Head; p->prev = 0; // "привязали"
Head->prev = p; Head = p; // первым в деке
head = iterator(Head); // корректируем итератор
++count; // добавили элемент
}
Таким образом, изменение типа инкапсулируется в операторе typedef: если нам потребуется дек с другим типом элементов, нужно изменить единственную строку в классе, дублируя остальное определение без изменений. Это практически гарантирует нам отсутствие ошибок в новом деке.
Аналогично можно обобщить и класс ТАггау. Давайте оставим в классе только те операции, которые не учитывают специфику числового типа элементов. Тогда класс ТАггау фактически будет представлять собой определение динамического массива (листинг 6.10).
Листинг 6.10. Динамический массив
class ТАггау
{ public:
// определение типов
typedef std::size_t size_type;
typedef std::size_t index_type;
typedef double value_type;
typedef double & reference;
typedef double * iterator;
typedef double * pointer;
TArray(size_type size, value_type k=0.0);
TArray(const TArray &a);
TArray(const TArray &a, index_type begin, size_type k);
TArray(const iterator begin, const iterator end);
-TArrayO ; reference operator[](index_type index); const reference operator[](index_type index) const; TArray& operator=(const TArray &a);
TArray& assign(const TArray &a, index_type I, index_type r); TArray& assign(const iterator begin, const iterator end); size_type size()const { return size_array; }; iterator find(const value_type &a); friend ostream& operator <<(ostream& to, const TArray &a); friend istream& operator >>(istream& to, TArray &a); private:
size_type size_array; pointer data;
>:
И в этом классе нет ни одного метода, использующего числовую специфику элементов. Поэтому, заменяя объявление типов в операторах typedef, мы получаем возможность дублировать определение класса ТАггау для любого нужного нам типа элементов.
Резюме
Поскольку встроенных массивов явно не хватает для обработки групп однотипных данных, программистское сообщество предложило более общую конструкцию объединения однородных данных в группу — контейнер. Все контейнеры обладают некоторыми свойствами. Одним из важнейших характеристик контейнера является способ доступа к элементам: последовательный, прямой или ассоциативный.
Прямой и ассоциативный варианты доступа обычно реализуются посредством перегрузки операции индексирования operator!], а последовательный — реализацией класса-итератора. Такая реализация имеет еще и то преимущество, что отделяет интерфейс доступа от интерфейса контейнера. Так как итератор тесно связан с внутренней структурой контейнера, его обычно создают как вложенный класс.
Для контейнеров реализуется множество операций, однако одна из наиболее часто используемых — операция объединения контейнеров, реализуемая самыми разнообразными способами.
Динамические структуры данных, как правило, являются универсальными структурами, работа которых не зависит от типа элемента. Таковыми являются стек, очередь и дек, которые различаются только дисциплиной добавления и удаления элементов. Как правило, такие структуры реализуются с помощью связанных списков. Однако написать универсальный класс без использования механизма наследования или шаблонов достаточно сложно — как правило, приходится задействовать нетипизированные указатели, которые потенциально опасны.
|
Главная
Каталог файлов
