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

Страуструп Бьерн
Шрифт:

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>
. Рассмотрим пример.