Программирование. Принципы и практика использования C++ Исправленное издание - Бьёрн Страуструп

или менее взаимозаменяемо в обобщенном программировании, описанном в разделе 20.3? Сначала опишем схему решения (игнорируя для простоты распределители памяти), а затем объясним ее.

template<class T> class vector {

public:

  typedef unsigned long size_type;

  typedef T value_type;

  typedef T* iterator;

  typedef const T* const_iterator;

  // ...

  iterator begin();

  const_iterator begin() const;

  iterator end();

  const_iterator end() const;

  size_type size();

  // ...

};

 

 Оператор typedef создает синоним типа; иначе говоря, для нашего класса vector имя iterator — это синоним, т.е. другое имя типа, который мы решили использовать в качестве итератора: T*. Теперь для объекта v класса vector можно написать следующие инструкции:

vector<int>::iterator p = find(v.begin(), v.end(),32);

и

for (vector<int>::size_type i = 0; i<v.size(); ++i)

 cout << v[i] << 'n';

Дело в том, что, для того, чтобы написать эти инструкции, нам на самом деле не обязательно знать, какие именно типы называются iterator и size_type. В частности, в приведенном выше коде, выраженном через типы iterator и size_type, мы будем работать с векторами, в которых тип size_type — это не unsigned long (как во многих процессорах встроенных систем), а тип iterator — не простой указатель, а класс (как во многих широко известных реализациях языка C++).

В стандарте класс list и другие стандартные контейнеры определены аналогично. Рассмотрим пример.

template<class Elem> class list {

public:

  class Link;

  typedef unsigned long size_type;

  typedef Elem value_type;

  class iterator;        // см. раздел 20.4.2

  class const_iterator;  // как iterator, но допускает изменение

                         // элементов

  // ...

  iterator begin();

  const_iterator begin() const;

  iterator end();

  const_iterator end() const;

  size_type size();

  // ...

};

Таким образом, можно писать код, не беспокоясь о том, что он использует: класс list или vector. Все стандартные алгоритмы определены в терминах этих имен типов, таких как iterator и size_type, поэтому они не зависят от реализации контейнеров или их вида (подробнее об этом — в главе 21).

20.6. Пример: простой текстовый редактор

 

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

Какие операции? Допустим, документ будет храниться в основной памяти компьютера. Следовательно, можно выбрать любое удобное представление и просто превратить его в поток байтов, которые мы хотим хранить в файле. Аналогично, мы можем читать поток байтов из файла и превращать их в соответствующее представление в памяти компьютера. Решив этот вопрос, можем сконцентрироваться на выборе подходящего представления документа в памяти компьютера. По существу, это представление должно хорошо поддерживать пять операций.

• Создание документа из потока байтов, поступающих из потока ввода.

• Вставка одного или нескольких символов.

• Удаление одного или нескольких символов.

• Поиск строки.

• Генерирование потока байтов для вывода в файл или на экран.

В качестве простейшего представления можно выбрать класс vector<char>. Однако, чтобы добавить или удалить символ в векторе, нам пришлось бы переместить все последующие символы в документе. Рассмотрим пример.

This is he start of a very long document.

There are lots of ...

Мы могли бы добавить недостающий символ t и получить следующий текст:

This is the start of a very long document.

There are lots of ...

Однако, если бы эти символы хранились в отдельном объекте класса vector<char>, мы должны были бы переместить все символы, начиная с буквы h на одну позицию вправо. Для этого пришлось бы копировать много символов. По существу, для документа, состоящего из 70 тыс. символов (как эта глава с учетом пробелов), при вставке или удалении символа в среднем нам пришлось бы переместить 35 тыс. символов. В результате временная задержка стала бы заметной и досадной для пользователей. Вследствие этого мы решили разбить наше представление на “порции” и изменять часть документа так, чтобы не перемещать большие массивы символов. Мы представим документ в виде списка строк с помощью класса list<Line>, где шаблонный параметр Line — это класс vector<char>. Рассмотрим пример.

Теперь для вставки символа t достаточно переместить только остальные символы из этой строки. Более того, при необходимости можем добавить новую строку без перемещения каких-либо символов. Для примера рассмотрим вставку строки “This is a new line.” после слова “document.”.

This is the start of a very long document.

This is a new line.

There are lots of ...

Все, что нам для этого нужно, — добавить новую строку в середину.

Возможность вставки новых узлов без перемещения существующих узлов объясняется тем, что мы используем итераторы, ссылающиеся на эти узлы, или указатели (или ссылки), установленные на объекты в этих узлах. Эти итераторы и указатели не зависят от вставок и удалений строк. Например, в текстовом процессоре может использоваться объект класса vector<list<Line>::iterator>, в котором хранятся итераторы, установленные на начало каждого заголовка и подзаголовка из текущего объекта класса Document.

Мы можем добавить строки в “paragraph 20.2”, не нарушая целостности итератора, установленного “paragraph 20.3.”

В заключение отметим, что использование как списка строк, так и вектора всех символов имеет как логические, так и практические причины. Однако следует под- черкнуть, что ситуации, в которых эти причины становятся важными, являются настолько редкими, что правило “по умолчанию используйте класс vector” по-прежнему действует. Нужна особая причина, чтобы предпочесть класс list классу vector, — даже, если вы представляете свои данные только в виде списка! (См. раздел 20.7.) Список — это логическое понятие, которое в вашей программе можно представить с помощью как класса list (связанного списка), так и класса vector. В библиотеке STL ближайшим аналогом нашего бытового