Важным свойством списка является возможность вставлять и удалять элементы без перемещения других элементов списка. Исследуем простой пример, иллюстрирующий этот факт. Посмотрим, как представить символы в текстовом документе в простом текстовом редакторе. Это представление должно быть таким, чтобы операции над документом стали простыми и по возможности эффективными.
Какие операции? Допустим, документ будет храниться в основной памяти компьютера. Следовательно, можно выбрать любое удобное представление и просто превратить его в поток байтов, которые мы хотим хранить в файле. Аналогично, мы можем читать поток байтов из файла и превращать их в соответствующее
представление в памяти компьютера. Решив этот вопрос, можем сконцентрироваться на выборе подходящего представления документа в памяти компьютера. По существу, это представление должно хорошо поддерживать пять операций.
• Создание документа из потока байтов, поступающих из потока ввода.
• Вставка одного или нескольких символов.
• Удаление одного или нескольких символов.
• Поиск строки.
• Генерирование потока байтов для вывода в файл или на экран.
В качестве простейшего представления можно выбрать класс
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 ближайшим аналогом нашего бытового представления о списке (например, список дел, товаров или расписание) является последовательность, а большинство последовательностей лучше всего представлять с помощью класса
vector
.
20.6.1. Строки
Как решить, что такое строка в нашем документе? Есть три очевидные альтернативы.
1. Полагаться на индикаторы новых строк (например,
'\n'
) в строке ввода.
2. Каким-то образом разделить документ и использовать обычную пунктуацию (например,
.
).
3. Разделить строку, длина которой превышает некий порог (например, 50 символов), на две.
Кроме этого, несомненно, существуют менее очевидные варианты. Для простоты выберем первую альтернативу.
Представим документ в нашем редакторе в виде объекта класса
Document
. Схематически наш тип должен выглядеть примерно так:
typedef vector<char> Line; // строка — это вектор символов
struct Document {
list<Line> line; // документ — список строк
Document { line.push_back(Line); }
};
Каждый объект класса
Document
начинается с пустой строки: конструктор класса
Document
сначала создает пустую строку, а затем заполняет список строка за строкой.
Чтение и разделение на строки можно выполнить следующим образом:
, возвращающую ссылку на последний элемент. Для ее использования вы должны быть уверены, что она действительно ссылается на последний элемент, — функцию
back
нельзя применять к пустому контейнеру. Вот почему в соответствии с определением каждый объект класса
Document
должен содержать пустой объект класса
Line
. Обратите внимание на то, что мы храним каждый введенный символ, даже символы перехода на новую строку (
'\n'
). Хранение символов перехода на новую строку сильно упрощает дело, но при подсчете символов следует быть осторожным (простой подсчет символов будет учитывать пробелы и символы перехода на новую строку).
20.6.2. Итерация
Если бы документ хранился как объект класса
vector<char>
, перемещаться по нему было бы просто. Как перемещать итератор по списку строк? Очевидно, что перемещаться по списку можно с помощью класса
list<Line>::iterator
. Однако, что, если мы хотим пройтись по символам один за другим, не беспокоясь о разбиении строки? Мы могли бы использовать итератор, специально разработанный для нашего класса