80.Контейнер объектов List

Контейнер list (список) реализован в виде двусвязного списка: в каждом элементе, помимо собственно данных, хранятся два члена-указателя – на следующий и на предыдущий элементы. Основное преимущество списка – это эффективная вставка и удаление одного элемента или целого диапазона в произвольное место списка, а недостаток – невозможность произвольного доступа. Например, можно написать:

vector<string>::iterator vec_iter = vec.begin() + 7;

Такая форма вполне допустима и инициализирует vec_iter адресом восьмого элемента вектора, но запись

// ошибка: арифметические операции над итераторами

// не поддерживаются списком

list<string>::iterator list_iter = slist.begin() + 7;

некорректна, так как элементы списка не занимают непрерывную область памяти. Для того чтобы добраться до восьмого элемента, необходимо посетить все промежуточные.

82.Контейнеры шаблонов fds (Fundamental Data Structures).

Контейнеры Borland реализуются с помощью шаблонов. Вы можете передавать в шаблон любой тип объекта, который хотите включить в контейнер. Это облегчает, например, инициализацию массивов.

Библиотеку класса контейнера можно разделить на две категории: фундаментальные структуры данных FDS (Fundamental Data Structures) и абстрактные типы данных ADT (Abstract Data Types)

Структуры FDS - это контейнеры нижнего уровня, реализующие структуры памяти. Каждая FDS имеет фундаментальные функции добавления и отсоединения. Типы ADT обычно используются в конструкциях обработки данных. Каждый тип ADT имеет соответствующие методы, например, контейнеры стека - функции-элементы Push и Pop.

Каждый тип ADT основан на FDS. Например, TArrayAsVector реализует массив, используя в качестве соответствующей структуры FDS вектор. Контейнеры ADT используют характеристики хранения соответствующих FDS и добавляет специфические методы доступа, которые делают каждый из них уникальным.

76.Класс итераторов объектов: внешние и внутренние итераторы.

Существуют два типа итераторов:

относящиеся к внутренней реализации коллекции (например, для приведенного выше класса

SimpleCollection) и открытые внешнему миру. Они называются внутренними (internal iterator) и

внешними (external iterator) итераторами соответственно.

Внутренний итератор обычно представляет собой тупой, ненадежный итератор, который перебирает

объекты коллекции в ее текущем состоянии. Если в коллекции происходит вставка или удаление,

внутренние итераторы начинают выкидывать все те странные фортели, о которых говорилось в начале

раздела. По этой причине их тщательно прячут от шаловливых рук клиента. Как правило, внутренние

итераторы тесно связаны со структурами данных, использованными в реализации коллекции. Как и

любые другие итераторы, они могут возвращать *-указатель или курсор в зависимости от ваших

потребностей.

Внешние итераторы соблюдают принцип затенения. Затенения можно добиться многими способами,

часть из которых рассматривается далее в этой главе и в главе 9. Как всегда, суть кроется не в

конкретном алгоритме или структуре данных, а в том, как спрятать их от публики.

Временные внутренние итераторы

Если внешний итератор создает частную копию коллекции (см. предыдущий раздел) и при этом не

существует оператора преобразования или конструктора, способного превратить исходную коллекцию

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

следующем фрагменте два внутренних итератора объединяются в реализации одного внешнего:

class ExternalIterator {

private:

SimpleCollection collection;

SimpleIterator* my_iter; // Возвращается коллекцией

public:

ExternalIterator(ComplexCollection* c)

{

InternalIterator* iter = c->Iterator();

while (c->More())

collection += *(c->Next());

delete iter;

my_iter = collection->Iterator();

}

bool More() { return my_iter->More(); }

bool Next() { return my_iter->Next(); }

};

ComplexCollection предоставляет внутренний итератор, который существует ровно столько, сколько

необходимо для создания копии. SimpleCollection возвращает итератор, используемый для

реализации функции More() и Next() внешнего итератора. Конечно, все могло бы выглядеть намного

элегантнее, если бы у SimpleCollection был конструктор с аргументом ComplexCollection или у

ComplexCollection — операторная функция преобразования operator SimpleCollection(). Но

даже при их отсутствии класс итератора обеспечивает весь необходимый уровень инкапсуляции.

Устойчивые внутренние итераторы

Термин «устойчивый» (persistent) означает, что внутренний итератор существует до тех пор, пока

существует внешний итератор (my_iter в предыдущем примере). Внутренний итератор может быть

переменной класса внешнего итератора, как было показано, а при достаточной осторожности его

можно создать как производный класс посредством закрытого наследования. Вариант с закрытым

наследованием может выглядеть так:

// В файле .h

class Collection {

public:

class ExternalIterator {

public:

virtual bool More() = 0;

virtual Foo* Next() = 0;

};

ExternalIterator* Iterator();

};

// В файле .cpp

// Настоящий класс, возвращаемый клиентам

class RealExternalIterator

: public ExternalIterator, private InternalIterator

(...);

Collection:ExternalIterator* Collection::Iterator()

{

return new RealExternalIterator(this);

}