Программирование — страница 39 из 57

“Пишите программы, которые делают что-то одно

и делают это хорошо. Пишите программы,

чтобы работать вместе”.

Дуг Мак-Илрой (Doug McIlroy)

Эта и следующая главы посвящены библиотеке STL — части стандартной библиотеки языка С++, содержащей контейнеры и алгоритмы. Библиотека STL — это масштабируемый каркас для обработки данных в программе на языке С++. Сначала мы рассмотрим простой пример, а потом изложим общие идеи и основные концепции. Мы обсудим понятие итерации, манипуляции со связанными списками, а также контейнеры из библиотеки STL. Связь между контейнерами (данными) и алгоритмами (обработкой) обеспечивается последовательностью и итераторами. В настоящей главе изложены основы для универсальных, эффективных и полезных алгоритмов, описанных в следующей главе. В качестве примера простого приложения рассматривается редактирование текста.

20.1. Хранение и обработка данных

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

Потребуем, чтобы программы Джека и Джилл записывали значения в файл, чтобы мы могли считать их в своей программе. В этом случае мы не будем зависеть от выбора структур данных и интерфейсов, сделанных Джеком и Джилл. Довольно часто такая изоляция целиком оправданна. Для ее реализации в наших вычислениях можно использовать приемы ввода, описанные в главах 10 и 11, и класс vector.

Однако что делать, если использовать файлы для решения нашей задачи слишком сложно? Допустим, что код для регистрации данных оформлен в виде функции, которая каждую секунду поставляет новый набор данных. В таком случае каждую секунду мы будем вызывать функции Джека и Джилл, чтобы получить данные для обработки.

double* get_from_jack(int* count); // Джек записывает числа
 // типа double 
в массив и возвращает
 // количество
 элементов в массиве *count
vector* get_from_jill();   // Джилл заполняет вектор
void fct()
{
  int jack_count = 0;
  double* jack_data = get_from_jack(&jack_count);
  vector* jill_data = get_from_jill();
  // ...обрабатываем...
  delete[] jack_data;
  delete jill_data;
}

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

20.1.1. Работа с данными

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

Что мы хотим делать с этими данными? Упорядочить их? Найти наибольшее значение? Вычислить среднее? Найти все значения, большие 65? Сравнить данные Джилл с данными Джека? Определить количество элементов? Возможности бесконечны. Когда мы пишем реальную программу, то просто выполняем требуемые вычисления. В данном случае мы хотим выяснить, как обработать данные и выполнить вычисления с большим массивом чисел. Сначала сделаем нечто совсем простое: найдем наибольший элемент в каждом из наборов данных. Для этого комментарий ...обработка... следует заменить соответствующими инструкциями.

// ...
double h = –1;
double* jack_high;   // jack_high — указатель на наибольший элемент
double* jill_high;   // jill_high — указатель на наибольший элемент

for (int i=0; i
  if (h
    jack_high = &jack_data [i]; // сохраняем адрес наибольшего
                                // элемента

h = –1;
for (int i=0; i< jill_data –>size(); ++i)
  if (h<(*jill_data)[i])
    jill_high = &(*jill_data)[i]; // сохраняем адрес наибольшего
                                  // элемента
cout << "Максимум Джилл: " << *jill_high
<< "; максимум Джека: " << *jack_high;
// ...

Обратите внимание на уродливую конструкцию, используемую для доступа к данным Джилл: (*jill_data)[i]. Функция get_from_jill() возвращает указатель на вектор, а именно vector*. Для того чтобы получить данные, мы сначала должны его разыменовать, получив доступ к вектору с помощью указателя *jill_ data, а затем применить к нему операцию индексирования. Однако выражение *jill_data[i] — не совсем то, что мы хотели; оно означает *(jill_data[i]), так как оператор [] имеет более высокий приоритет, чем *, поэтому нам необходимы скобки вокруг конструкции *jill_data, т.е. выражение (*jill_data)[i].

ПОПРОБУЙТЕ

Как вы изменили бы интерфейс, чтобы избежать неуклюжих конструкций, если бы могли изменить код Джилл?

20.1.2. Обобщение кода

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

Разумеется, все, что мы сделаем с данными Джека, относится и к данным Джилл. Однако между их программами есть два досадных различия: переменные jack_count и jill_data–>size(), а также конструкции jack_data[i] и (*jill_data)[i]. Последнее различие можно устранить, введя ссылку.

vector& v = *jill_data;
for (int i=0; i
  if (h
  {
    jill_high = &v[i];
    h = v[i];
  }

Это очень похоже на код для обработки данных Джека. Может быть, стоит написать функцию, которая выполняла бы вычисления как с данными Джилл, так и с данными Джека? Возможны разные пути (см. упр. 3), но, стремясь к более высокой степени обобщения кода (см. следующие две главы), мы выбрали решение, основанное на указателях.

double* high(double* first, double* last)
// возвращает указатель на наибольший элемент в диапазоне [first,last]
{
  double h = –1;
  double* high;
  for(double* p = first; p!=last; ++p)
    if (h<*p)
    {
      high = p;
      h = *p;
    }
  return high;
}

Теперь можно написать следующий код:

double* jack_high = high(jack_data,jack_data+jack_count);
vector& v = *jill_data;
double* jill_high = high(&v[0],&v[0]+v.size());

Он выглядит получше. Мы не ввели слишком много переменных и написали только один цикл (в функции high()). Если мы хотим найти наибольший элемент, то можем посмотреть на значения *jack_high и *jill_high. Рассмотрим пример.

cout << "Максимум Джилл: " << *jill_high
<< "; максимум Джека: " << *jack_high;

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

ПОПРОБУЙТЕ

В этой маленькой программе мы оставили две потенциально опасные ошибки. Одна из них может вызвать катастрофу, а другая приводит к неправильным ответам, если функция high() будет использоваться в других программах. Универсальный прием, который описывается ниже, выявит обе эти ошибки и покажет, как их устранить. Пока просто найдите их и предложите свои способы их исправления.

Функция high() решает одну конкретную задачу, поэтому она ограничена следующими условиями.

• Она работает только с массивами. Мы считаем, что элементы объекта класса vector хранятся в массиве, но наряду с этим существует множество способов хранения данных, таких как списки и ассоциативные массивы (см. разделы 20.4 и 21.6.1).

• Ее можно применять только к объектам класса vector и массивам типа double, но не к векторам и массивам с другими типами элементов, например vector и char[10].

• Она находит элемент с максимальным значением, но с этими данными можно выполнить множество других простых вычислений.

Попробуем обеспечить более высокую общность вычислений над нашими наборами данных.

Обратите внимание на то, что, решив выразить алгоритм поиска наибольшего элемента в терминах указателей, мы “случайно” уже обобщили решение задачи: при желании мы можем найти наибольший элемент массива или вектора, но, помимо этого, можем найти максимальный элемент части массива или вектора. Рассмотрим пример.

// ...
vector& v = *jill_data;
double* middle = &v[0]+v.size()/2;
double* high1 = high(&v[0], middle);          // максимум первой
                                              // половины
double* high2 = high(middle, &v[0]+v.size()); // максимум второй
                                              // половины
// ...

Здесь указатель high1 ссылается на максимальный элемент первой половины вектора, а указатель high2 — на максимальный элемент второй половины. Графически это можно изобразить следующим образом:

В качестве аргументов функции high() мы использовали указатели. Этот механизм управления памятью относится к слишком низкому уровню и уязвим для ошибок. Мы подозреваем, что большинство программистов для поиска максимального элемента в векторе написали бы нечто вроде следующего:

double* find_highest(vector& v)
{
  double h = –1;
  double* high = 0;
  for (int i=0; i
    if (h
    {
      high = &v[i];
      h = v[i];
    }
  return high;
}

Однако это не обеспечивает достаточно гибкости, которую мы “случайно” уже придали функции high(), — мы не можем использовать функцию find_highest() для поиска наибольшего элемента в части вектора. На самом деле, “связавшись с указателями”, мы достигли практической выгоды, получив функцию, которая может работать как с векторами, так и с массивами. Помните: обобщение может привести к функциям, которые позволяют решать больше задач. 

20.2. Принципы библиотеки STL

Стандартная библиотека языка С++, обеспечивающая основу для работы с данными, представленными в виде последовательности элементов, называется STL. Обычно эту аббревиатуру расшифровывают как “стандартная библиотека шаблонов” (“standard template library”). Библиотека STL является частью стандарта ISO C++. Она содержит контейнеры (такие как классы vector, list и map) и обобщенные алгоритмы (такие как sort, find и accumulate). Следовательно, мы имеем право говорить, что такие инструменты, как класс vector, являются как частью библиотеки STL, так и стандартной библиотеки. Другие средства стандартной библиотеки, такие как потоки ostream (см. главу 10) и функции для работы строками в стиле языка С (раздел B.10.3), не являются частью библиотеки STL. Чтобы лучше оценить и понять библиотеку STL, сначала рассмотрим проблемы, которые мы должны устранить, работая с данными, а также обсудить идеи их решения.

 Существуют два основных вычислительных аспекта: вычисления и данные. Иногда мы сосредоточиваем внимание на вычислениях и говорим об инструкциях if, циклах, функциях, обработке ошибок и пр. В других случаях мы фокусируемся на данных и говорим о массивах, векторах, строках, файлах и пр. Однако, для того чтобы выполнить полезную работу, мы должны учитывать оба аспекта. Большой объем данных невозможно понять без анализа, визуализации и поиска “чего-нибудь интересного”. И наоборот, мы можем выполнять вычисления так, как хотим, но такой подход оказывается слишком скучным и “стерильным”, пока мы не получим некие данные, которые свяжут наши вычисления с реальностью. Более того, вычислительная часть программы должна элегантно взаимодействовать с “информационной частью.

Говоря так о данных, мы подразумеваем много разных данных: десятки фигур, сотни значений температуры, тысячи регистрационных записей, миллионы точек, миллиарды веб-страниц и т.д.; иначе говоря, мы говорим о работе с контейнерами данных потоками данных и т.д. В частности, мы не рассматриваем вопросы, как лучше выбрать набор данных, представляющих небольшой объект, такой как комплексное число, запись о температуре или окружность. Эти типы описаны в главах 9, 11 и 14.

Рассмотрим простые примеры, которые иллюстрируют наше понятие о крупном наборе данных.

• Сортировка слов в словаре.

• Поиск номера в телефонной книге по заданному имени.

• Поиск максимальной температуры.

• Поиск всех чисел, превышающих 8800.

• Поиск первого появления числа 17.

• Сортировка телеметрических записей по номерам устройств.

• Сортировка телеметрических записей по временным меткам.

• Поиск первого значения, большего, чем строка “Petersen”.

• Поиск наибольшего объема.

• Поиск первого несовпадения между двумя последовательностями.

• Вычисление попарного произведения элементов двух последовательностей.

• Поиск наибольшей месячной температуры.

• Поиск первых десяти лучших продавцов по записям о продажах.

• Подсчет количества появлений слова “Stroustrup” в сети веб.

• Вычисление суммы элементов.

Обратите внимание на то, что каждую из этих задач мы можем описать, не упоминая о способе хранения данных. Очевидно, что мы как-то должны работать со списками, векторами, файлами, потоками ввода и т.д., но мы не обязаны знать, как именно хранятся (и собираются) данные, чтобы говорить о том, что будем делать с ними. Важен лишь тип значений или объектов (тип элементов), способ доступа к этим значениям или объектам, а также что именно мы хотим с ними сделать.

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

• Существует бесконечное множество вариантов типов данных (виды данных).

• Существует огромное количество способов организации коллекций данных.

• Существует громадное количество задач, которые мы хотели бы решить с помощью коллекций данных.

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

Для того чтобы понять, какая поддержка нам нужна, чтобы написать наш код, рассмотрим, что мы можем делать с данными, более абстрактно. Итак, можно сделать следующее.

• Собирать данные в контейнерах

• например, собирать их в объектах классов vector, list и массивах.

• Организовывать данные

• для печати;

• для быстрого доступа.

• Искать данные

• по индексу (например, найти 42-й элемент);

• по значению (например, найти первую запись, в которой в поле “age” записано число 7);

• по свойствам (например, все записи, в которых значение поля “temperature” больше 32 и меньше 100).

• Модифицировать контейнер

• добавлять данные;

• удалять данные;

• сортировать (в соответствии с каким-то критерием).

• Выполнять простые математические операции (например, умножить все элементы на 1,7).

Мы хотели бы делать все это, не утонув в море информации, касающейся отличий между контейнерами, способами доступа к элементам и их типами. Если нам это удастся, то мы сделаем рывок по направлению к своей цели и получим эффективный метод работы с большими объемами данных.

Оглядываясь назад на методы и инструменты программирования, описанные в предыдущих главах, мы видим, что уже можем писать программы, не зависящие от типа используемых данных. Этот вывод основан на следующих фактах.

• Использование типа int мало отличается от использования типа double.

• Использование типа vector мало отличается от использования типа vector.

• Использование массива чисел типа double мало отличается от использования типа vector.

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

• Поиск значения в объекте класса vector не должен отличаться от поиска значения в массиве.

• Поиск объекта класса string без учета регистра не должен отличаться от поиска объекта класса string с учетом нижнего и верхнего регистров.

• Графическое изображение экспериментальных данных с точными значениями не должно отличаться от графического изображения экспериментальных данных с округленными значениями.

• Копирование файла не должно отличаться от копирования вектора.

Учитывая сказанное, мы хотим писать код, удовлетворяющий следующим условиям:

• его легко читать;

• легко модифицировать;

• он имеет систематический характер;

• он короткий;

• быстро работает.

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

• Единообразный доступ к данным:

• независимость от способа хранения данных;

• независимость от типа данных.

• Доступ к данным, безопасный с точки зрения типа:

• легкое перемещение по данным;

• компактное хранение данных.

• Скорость работы:

• поиск данных;

• добавление данных;

• удаление данных.

• Стандартные версии большинства широко распространенных алгоритмов таких как copy, find, search, sort, sum, ...

Библиотека STL обеспечивает не только эти возможности. Мы изучим эту библиотеку не только потому, что она представляет собой очень полезный набор инструментов, но и потому, что является примером максимальной гибкости и эффективности. Библиотека STL была разработана Алексом Степановым (Alex Stepanov) для того, чтобы создать базу для универсальных, правильных и эффективных алгоритмов, работающих с разнообразными структурами данных. Ее целью были простота, универсальность и элегантность математики.

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

Итак, рассмотрев мотивы и цели, перейдем к описанию основных определений из библиотеки STL, а затем изучим примеры их применения для более простого создания более совершенного кода для обработки данных.

20.3. Последовательности и итераторы

Основным понятием в библиотеке STL является последовательность. С точки зрения авторов этой библиотеки, любая коллекция данных представляет собой последовательность. Последовательность имеет начало и конец. Мы можем перемещаться по последовательности от начала к концу, при необходимости считывая или записывая значение элементов. Начало и конец последовательности идентифицируются парой итераторов. Итератор (iterator) — это объект, идентифицирующий элемент последовательности.

Последовательность можно представить следующим образом:

Здесь begin и end — итераторы; они идентифицируют начало и конец последовательности. Последовательность в библиотеке STL часто называют “полуоткрытой” (“half-open”); иначе говоря, элемент, идентифицированный итератором begin, является частью последовательности, а итератор end ссылается на ячейку, следующую за концом последовательности. Обычно такие последовательности (диапазоны) обозначаются следующим образом: [begin:end]. Стрелки, направленные от одного элемента к другому, означают, что если у нас есть итератор на один элемент, то мы можем получить итератор на следующий.

• Что такое итератор? Это довольно абстрактное понятие.

• Итератор указывает (ссылается) на элемент последовательности (или на ячейку, следующую за последним элементом).

• Два итератора можно сравнивать с помощью операторов == и !=.

• Значение элемента, на который установлен итератор, можно получить с помощью унарного оператора * (“разыменование”).

• Итератор на следующий элемент можно получить, используя оператор ++.

Допустим, что p и q — итераторы, установленные на элементы одной и той же последовательности.

Очевидно, что идея итератора связана с идеей указателя (см. раздел 17.4). Фактически указатель на элемент массива является итератором. Однако многие итераторы являются не просто указателями; например, мы могли бы определить итератор с проверкой выхода за пределы допустимого диапазона, который генерирует исключение при попытке сослаться за пределы последовательности [begin:end] или разыменовать итератор end. Оказывается, что итератор обеспечивает огромную гибкость и универсальность именно как абстрактное понятие, а не как конкретный тип. В этой и следующей главах при приведем еще несколько примеров.

ПОПРОБУЙТЕ

Напишите функцию void copy(int* f1, int* e1, int* f2), копирующую элементы массива чисел типа int, определенного последовательностью [f1:e1] в другую последовательность [f2:f2+(e1–f1)]. Используйте только упомянутые выше итераторы (а не индексирование).

Итераторы используются в качестве средства связи между нашим кодом (алгоритмами) и нашими данными. Автор кода знает о существовании итераторов (но не знает, как именно они обращаются к данным), а поставщик данных предоставляет итераторы, не раскрывая всем пользователям детали механизма хранения данных. В результате получаем достаточно независимые друг от друга алгоритмы и контейнеры. Процитируем Алекса Степанова: “Алгоритмы и контейнеры библиотеки STL потому так хорошо работают друг с другом, что ничего не знают друг о друге”. Вместо этого и алгоритмы, и контейнеры знают о последовательностях, определенных парами итераторов.

Иначе говоря, автор кода больше не обязан ничего знать о разнообразных способах хранения данных и обеспечения доступа к ним; достаточно просто знать об итераторах. И наоборот, если поставщик данных больше не обязан писать код для обслуживания огромного количества разнообразных пользователей, ему достаточно реализовать итератор для данных. На базовом уровне итератор определен только операторами *, ++, == и !=. Это обеспечивает его простоту и быстродействие.

Библиотека STL содержит около десяти контейнеров и 60 алгоритмов, связанных с итераторами (см. главу 21). Кроме того, многие организации и отдельные лица создают контейнеры и алгоритмы в стиле библиотеки STL. Вероятно, библиотека STL в настоящее время является наиболее широко известным и широко используемым примером обобщенного программирования (см. раздел 19.3.2). Если вы знаете основы и несколько примеров, то сможете использовать и все остальное. 

20.3.1. Вернемся к примерам

Посмотрим, как можно решить задачу “найти максимальный элемент” с помощью последовательности STL.

template
Iterator high(Iterator first, Iterator last)
// возвращает итератор на максимальный элемент в диапазоне [first:last]
{
  Iterator high = first;
  for (Iterator p = first; p!=last; ++p)
    if (*high<*p) high = p;
  return high;
}

Обратите внимание на то, что мы исключили локальную переменную h, которую до сих пор использовали для хранения максимального элемента. Если вам неизвестен реальный тип элементов последовательности, то инициализация –1 выглядит совершенно произвольной и странной. Она действительно является произвольной и странной! Кроме того, такая инициализация представляет собой ошибку: в нашем примере число 1 оправдывает себя только потому, что отрицательных скоростей не бывает. Мы знаем, что “магические константы”, такие как –1, препятствуют сопровождению кода (см. разделы 4.3.1, 7.6.1, 10.11.1 и др.). Здесь мы видим, что такие константы могут снизить полезность функции и свидетельствовать о неполноте решения; иначе говоря, “магические константы” могут быть — и часто бывают — свидетельством небрежности.

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

Шаблонную функцию high() можно применять к любой последовательности, определенной парой итераторов. Например, мы можем точно воспроизвести нашу программу.

double* get_from_jack(int* count); // Джек вводит числа типа double
  // в массив 
и возвращает количество
  // элементов в переменной *count
vector* get_from_jill(); // Джилл заполняет вектор

void fct()
{
  int jack_count = 0;
  double* jack_data = get_from_jack(&jack_count);
  vector* jill_data = get_from_jill();

  double* jack_high = high(jack_data,jack_data+jack_count);
  vector& v = *jill_data;
  double* jill_high = high(&v[0],&v[0]+v.size());
  cout << "Максимум Джилл " << *jill_high
<< "; Максимум Джека" << *jack_high;
  // ...
  delete[] jack_data;
  delete jill_data;
}

Здесь в двух вызовах функции high() шаблонным типом аргумента является тип double*. Это ничем не отличается от нашего предыдущего решения. Точнее, выполняемые коды этих программ ничем не отличаются друг от друга, хотя степень общности этих кодов разнится существенно. Шаблонная версия функции high() может применяться к любому виду последовательности, определенной парой итераторов. Прежде чем углубляться в принципы библиотеки STL и полезные стандартные алгоритмы, реализующие эти принципы, и для того чтобы избежать создания сложных кодов, рассмотрим несколько способов хранения коллекций данных.

ПОПРОБУЙТЕ

В этой программе снова сделана серьезная ошибка. Найдите ее, исправьте и предложите универсальный способ устранения таких проблем. 

20.4. Связанные списки

 Еще раз рассмотрим графическое представление последовательности.

Сравним его с визуализацией вектора, хранящегося в памяти.

По существу, индекс 0 означает тот же элемент, что и итератор v.begin(), а функция v.size() идентифицирует элемент, следующий за последним, который можно также указать с помощью итератора v.end().

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

Структуру данных, которая точнее всех соответствует диаграмме последовательности в библиотеке STL, называют связанным списком (linked list). Стрелки в абстрактной модели обычно реализуются как указатели. Элемент связанного списка — это часть узла, состоящего из элемента и одного или нескольких указателей. Связанный список, в котором узел содержит только один указатель (на следующий узел), называют односвязным списком (singly-linked list), а список, в которой узел ссылается как на предыдущий, так и на следующий узлы, — двусвязным списком (doubly-linked list). Мы схематично рассмотрим реализацию двухсвязных списков, которые в стандартной библиотеке языка С++ имеют имя list. Графически список можно изобразить следующим образом.

В виде кода он представляется так:

template struct Link {
  Link* prev; // предыдущий узел
  Link* succ; // следующий узел
  Elem val;   // значение
};

template struct list {
  Link* first;
  Link* last; // узел, находящийся за последним узлом
};

Схема класса Link приведена ниже.

Существует много способов реализации и представления связанных списков. Описание списка, реализованного в стандартной библиотеке, приведено в приложении Б. Здесь мы лишь кратко перечислим основные свойства списка — возможность вставлять и удалять элементы, не трогая существующие элементы, а также покажем, как перемещаться по списку с помощью итератора, и приведем пример его использования.

Мы настоятельно рекомендуем вам, размышляя о списках, рисовать диаграммы, иллюстрирующие операции, которые вы рассматриваете. Манипуляции связанным списком — это тема, в которой один рисунок может заменить тысячу слов. 

20.4.1. Операции над списками

 Какие операции необходимы для списка?

• Операции, эквивалентные операциям над векторами (создание, определение размера и т.д.), за исключением индексирования.

• Вставка (добавление элемента) и стирание (удаление элемента).

• Нечто, что можно использовать для ссылки на элементы и перемещения по списку: итератор.

В библиотеке STL тип итератора является членом своего класса, поэтому и мы поступим так же.

template class list {
// детали представления и реализации
public:
  class iterator;      // тип — член класса :iterator
  iterator begin();    // итератор, ссылающийся на первый элемент
  iterator end( );     // итератор, ссылающийся на последний элемент

  iterator insert(iterator p, const Elem& v); // вставка v
                       // в список
 после элемента,
                       // на который установлен 
итератор p

  iterator erase(iterator p);     // удаление из списка элемента,
                       // на который установлен 
итератор p

  void push_back(const Elem& v);  // вставка v в конец списка
  void push_front(const Elem& v); // вставка v в начало списка
  void pop_front();               // удаление первого элемента
  void pop_back();                // удаление последнего элемента

  Elem& front();                  // первый элемент
  Elem& back();                   // последний элемент
  // ...
}

Так же как наш класс vector не совпадал с полной версией стандартного вектора, так и класс list — это далеко не полное определение стандартного списка. В этом определении все правильно; просто оно неполное. Цель “нашего” класса list — объяснить устройство связанных списков, продемонстрировать их реализацию и показать способы использования их основных возможностей. Более подробная информация приведена в приложении Б и в книгах о языке С++, предназначенных для экспертов.

Итератор играет главную роль в определении класса list в библиотеке STL. Итераторы используются для идентификации места вставки или удаления элементов. Кроме того, их используют для “навигации” по списку вместо оператора индексирования. Такое применение итераторов очень похоже на использование указателей при перемещении по массивам и векторам, описанном в разделах 20.1 и 20.3.1. Этот вид итераторов является основным в стандартных алгоритмах (разделы 21.1–21.3).

 Почему в классе list не используется индексирование? Мы могли бы проиндексировать узлы, но эта операция удивительно медленная: для того чтобы достичь элемента lst[1000], нам пришлось бы начинать с первого элемента и пройти все элементы по очереди, пока мы не достигли бы элемента с номером 1000. Если вы хотите этого, то можете реализовать эту операцию сами (или применить алгоритм advance(); см. раздел 20.6.2). По этой причине стандартный класс list не содержит операции индексирования.

Мы сделали тип итератора для списка членом класса (вложенным классом), потому что нет никаких причин делать его глобальным. Он используется только в списках. Кроме того, это позволяет нам называть каждый тип в контейнере именем iterator. В стандартной библиотеке есть list::iterator, vector::iterator, map::iterator и т.д.

20.4.2. Итерация

Итератор списка должен обеспечивать выполнение операций *, ++, == и !=. Поскольку стандартный список является двухсвязным, в нем также есть операция –– для перемещения назад, к началу списка.

template class list::iterator {
  Link* curr; // текущий узел
public:
  iterator(Link* p):curr(p) { }

  // вперед
  iterator& operator++() {curr = curr–>succ; return *this; }

  // назад
  iterator& operator––() { curr = curr–>prev; return *this; }

  // (разыменовать)
  Elem& operator*() { return curr–>val; } // получить значение
  bool operator==(const iterator& b) const
    { return curr==b.curr; }
  bool operator!= (const iterator& b) const
    { return curr!=b.curr; }
};

Эти функции короткие, простые и эффективные: в них нет циклов, нет сложных выражений и подозрительных вызовов функций. Если эта реализация вам не понятна, то посмотрите на диаграммы, приведенные ранее. Этот итератор списка просто представляет собой указатель на узел с требуемыми операциями. Несмотря на то что реализация (код) для класса list::iterator сильно отличается от обычного указателя, который использовался в качестве итератора для векторов и массивов, их семантика одинакова. По существу, итератор списка обеспечивает удобные операции ++, ––, *, ==, and != для указателя на узел.

Посмотрим на функцию high() еще раз.

template
Iterator high(Iterator first, Iterator last)
// возвращает итератор на максимальный элемент в диапазоне
// [first,last)
{
  Iterator high = first;
  for (Iterator p = first; p!=last; ++p)
    if (*high<*p) high = p;
  return high;
}

Мы можем применить ее к объекту класса list.

void f()
{
  list lst;
  int x;
  while (cin >> x) lst.push_front(x);

  list::iterator p = high(lst.begin(), lst.end());
  cout << "Максимальное значение = " << *p << endl;
}

Здесь значением аргумента класса Iterator argument является класс list::iterator, а реализация операций ++, * и != совершенно отличается от массива, хотя ее смысл остается неизменным. Шаблонная функция high() по-прежнему перемещается по данным (в данном случае по объекту класса list) и находит максимальное значение. Мы можем вставлять элементы в любое место списка, так что мы использовали функцию push_front() для добавления элементов в начало списка просто для иллюстрации. С таким же успехом мы могли бы использовать функцию push_back(), как делали это для объектов класса vector.

ПОПРОБУЙТЕ

В стандартном классе vector нет функции push_front(). Почему? Реализуйте функцию push_front() для класса vector и сравните ее с функцией push_back().

Итак, настало время спросить: “А что, если объект класса list будет пустым?” Иначе говоря, “что если lst.begin()==lst.end()?” В данном случае выполнение инструкции *p будет попыткой разыменования элемента, следующего за последним, т.е. lst.end(). Это катастрофа! Или, что еще хуже, в результате можно получить случайную величину, которая исказит правильный ответ.

 Последняя формулировка вопроса содержит явную подсказку: мы можем проверить, пуст ли список, сравнив итераторы begin() и end(), — по существу, мы можем проверить, пуста ли последовательность, сравнивая ее начало и конец.

Существует важная причина, по которой итератор end устанавливается на элемент, следующий за последним, а не на последний элемент: пустая последовательность — не особый случай. Мы не любим особые случаи, потому что — по определению — для каждого из них приходится писать отдельный код.

В нашем примере можно поступить следующим образом:

list::iterator p = high(lst.begin(), lst.end());
if (p==lst.end())         // мы достигли конца?
  cout << "Список пустой";
else
  cout << "максимальное значение = " << *p << endl;

Работая с алгоритмами из библиотеки STL, мы систематически используем эту проверку. Поскольку в стандартной библиотеке список предусмотрен, не будем углубляться в детали его реализации. Вместо этого кратко укажем, чем эти списки удобны (если вас интересуют детали реализации списков, выполните упр. 12–14).

20.5. Еще одно обобщение класса vector

Из примеров, приведенных в разделах 20.3 и 20.4, следует, что стандартный вектор имеет член класса, являющийся классом iterator, а также функции-члены begin() и end() (как и класс std::list). Однако мы не указали их в нашем классе vector в главе 19. Благодаря чему разные контейнеры могут использоваться более или менее взаимозаменяемо в обобщенном программировании, описанном в разделе 20.3? Сначала опишем схему решения (игнорируя для простоты распределители памяти), а затем объясним ее.

template 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::iterator p = find(v.begin(), v.end(),32);

и

for (vector::size_type i = 0; i
 cout << v[i] << '\n';

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

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

template 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. Однако, чтобы добавить или удалить символ в векторе, нам пришлось бы переместить все последующие символы в документе. Рассмотрим пример.

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

Теперь для вставки символа 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::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 Line;  // строка — это вектор символов

struct Document {
  list line;          // документ — список строк
  Document() { line.push_back(Line()); }
};

Каждый объект класса Document начинается с пустой строки: конструктор класса Document сначала создает пустую строку, а затем заполняет список строка за строкой.

Чтение и разделение на строки можно выполнить следующим образом:

istream& operator>>(istream& is, Document& d)
{
  char ch;
  while (is.get(ch)) {
    d.line.back().push_back(ch); // добавляем символ
    if (ch=='\n')
      d.line.push_back(Line());  // добавляем новую строку
  }
  if (d.line.back().size())
    d.line.push_back(Line());    // добавляем пустую строку
  return is;
}

Классы vector и list имеют функцию-член back(), возвращающую ссылку на последний элемент. Для ее использования вы должны быть уверены, что она действительно ссылается на последний элемент, — функцию back() нельзя применять к пустому контейнеру. Вот почему в соответствии с определением каждый объект класса Document должен содержать пустой объект класса Line. Обратите внимание на то, что мы храним каждый введенный символ, даже символы перехода на новую строку ('\n'). Хранение символов перехода на новую строку сильно упрощает дело, но при подсчете символов следует быть осторожным (простой подсчет символов будет учитывать пробелы и символы перехода на новую строку).

20.6.2. Итерация

 Если бы документ хранился как объект класса vector, перемещаться по нему было бы просто. Как перемещать итератор по списку строк? Очевидно, что перемещаться по списку можно с помощью класса list::iterator. Однако, что, если мы хотим пройтись по символам один за другим, не беспокоясь о разбиении строки? Мы могли бы использовать итератор, специально разработанный для нашего класса Document.

class Text_iterator { // отслеживает позицию символа в строке
  list::iterator ln;
  Line::iterator pos;
public:
  // устанавливает итератор на позицию pp в ll-й строке
  Text_iterator(list::iterator ll, Line::iterator pp)
  :ln(ll), pos(pp) { }

  char& operator*() { return *pos; }
  Text_iterator& operator++();

  bool operator==(const Text_iterator& other) const
    { return ln==other.ln && pos==other.pos; }

  bool operator!=(const Text_iterator& other) const
    { return !(*this==other); }
};

Text_iterator& Text_iterator::operator++()
{
  if (pos==(*ln).end()) {
    ++ln; // переход на новую строку
    pos = (*ln).begin();
  }
  ++pos; // переход на новый символ
  return *this;
}

Для того чтобы класс Text_iterator стал полезным, необходимо снабдить класс Document традиционными функциями begin() и end().

struct Document {
  list line;
  Text_iterator begin() // первый символ первой строки
    { return Text_iterator(line.begin(),
    (*line.begin()).begin()); }
  Text_iterator end()   // за последним символом последней строки
    { return(line.end(), (*line.end()).end));}
};

Мы использовали любопытную конструкцию (*line.begin()).begin(), потому что хотим начинать перемещение итератора с позиции, на которую ссылается итератор line.begin(); в качестве альтернативы можно было бы использовать функцию line.begin()–>begin(), так как стандартные итераторы поддерживают операцию –>.

Теперь можем перемещаться по символам документа.

void print(Document& d)
{
  for (Text_iterator p = d.begin();
  p!=d.end(); ++p) cout << *p;
}
print(my_doc);

Представление документа в виде последовательности символов полезно по многим причинам, но обычно мы перемещаемся по документам, просматривая более специфичную информацию, чем символ. Например, рассмотрим фрагмент кода, удаляющий строку n.

void erase_line(Document& d, int n)
{
  if (n<0 || d.line.size()<=n) return; // игнорируем строки,
                                       // находящиеся
                                       // за пределами диапазона
 d.line.erase(advance(d.line.begin(), n));
}

Вызов advance(p,n) перемещает итератор p на n элементов вперед; функция advance() — это стандартная функция, но мы можем сами написать подобный код.

template Iter advance(Iter p, int n)
{
   while (n>0) { ++p; ––n; } // перемещение вперед
   return p;
}

Обратите внимание на то, что функцию advance() можно использовать для имитации индексирования. Фактически для объекта класса vector с именем v выражение *advance(v.begin(),n) почти эквивалентно конструкции v[n]. Здесь слово “почти” означает, что функция advance() старательно проходит по каждому из первых n–1 элементов шаг за шагом, в то время как операция индексирования сразу обращается к n-му элементу. Для класса list мы вынуждены использовать этот неэффективный метод. Это цена, которую мы должны заплатить за гибкость списка.

Если итератор может перемещаться вперед и назад, например в классе list, то отрицательный аргумент стандартной библиотечной функции advance() означает перемещение назад. Если итератор допускает индексирование, например в классе vector, стандартная библиотечная функция advance() сразу установит его на правильный элемент и не будет медленно перемещаться по всем элементам с помощью оператора ++. Очевидно, что стандартная функция advance() немного “умнее” нашей. Это стоит отметить: как правило, стандартные средства создаются более тщательно, и на них затрачивается больше времени, чем мы могли бы затратить на самостоятельную разработку, поэтому мы отдаем предпочтение стандартным инструментам, а не “кустарным”.

ПОПРОБУЙТЕ

Перепишите нашу функцию advance() так, чтобы, получив отрицательный аргумент, она выполняла перемещение назад.

Вероятно, поиск — это самый очевидный вид итерации. Мы ищем отдельные слова (например, milkshake или Gavin), последовательности букв (например, secret\nhomestead — т.е. строка, заканчивающаяся словом secret, за которым следует строка, начинающаяся словом homestead), регулярные выражения (например, [bB]\w*ne — т.е. буква B в верхнем или нижнем регистре, за которой следует 0 или больше букв, за которыми следуют буквы ne; см. главу 23) и т.д. Покажем, как решить вторую задачу: найдем строку, используя нашу схему хранения объекта класса Document. Будем использовать простой — не оптимальный — алгоритм.

• Найдем первый символ искомой строки в документе.

• Проверим, совпадают ли эти и следующие символы с символами искомой строки.

• Если совпадают, то задача решена; если нет, будем искать следующее появление первого символа.

Для простоты примем правила представления текстов в библиотеке STL в виде последовательности, определенной парой итераторов. Это позволит нам применить функцию поиска не только ко всему документу, но и к любой его части. Если мы найдем нашу строку в документе, то вернем итератор, установленный на ее первый символ; если не найдем, то вернем итератор, установленный на конец последовательности.

Text_iterator find_txt(Text_iterator first,
  Text_iterator last, const string& s)
{
  if (s.size()==0) return last; // нельзя искать пустую строку
  char first_char = s[0];
  while (true) {
    Text_iterator p = find(first,last,first_char);
    if (p==last || match(p,last,s)) return p;
    ++first;                    // ищем следующий символ
  }
}

Возврат конца строки в качестве признака неудачного поиска является важным соглашением, принятым в библиотеке STL. Функция match() является тривиальной; она просто сравнивает две последовательности символов. Попробуйте написать ее самостоятельно. Функция find(), используемая для поиска символа в последовательности, вероятно, является простейшим стандартным алгоритмом (раздел 21.2). Мы можем использовать свою функцию find_txt() примерно так:

Text_iterator p =
  find_txt(my_doc.begin(), my_doc.end(),"secret\nhomestead");
if (p==my_doc.end())
  cout << "Не найдена ";
else {
  // какие-то действия
}

Наш текстовый процессор и его операции очень просты. Очевидно, что мы хотим создать простой и достаточно эффективный, а не “навороченный” редактор. Однако не следует ошибочно думать, что эффективные вставка, удаление и поиск произвольного символа — тривиальные задачи. Мы выбрали этот пример для того, чтобы продемонстрировать мощь и универсальность концепций последовательности, итератора и контейнера (таких как list и vector) в сочетании с правилами программирования (приемами), принятыми в библиотеке STL, согласно которым возврат итератора, установленного на конец последовательности, является признаком неудачи. Обратите внимание на то, что если бы мы захотели, то могли бы превратить класс Document в контейнер STL, снабдив его итератором Text_iterator. Мы сделали главное для представления объекта класса Document в виде последовательности значений.

20.7. Классы vector, list и string

Почему для хранения строк мы используем класс list, а для символов — класс vector? Точнее, почему для хранения последовательности строк мы используем класс list, а для хранения последовательности символов — класс vector? Более того, почему для хранения строки мы не используем класс string?

Сформулируем немного более общий вариант этого вопроса. Для хранения последовательности символов у нас есть четыре способа.

• char[] (массив символов)

• vector

• string

• list

 Какой из этих вариантов выбрать для решения конкретной задачи? Для действительно простой задачи все эти варианты являются взаимозаменяемыми; иначе говоря, у них очень похожие интерфейсы. Например, имея итератор, мы можем перемещаться по элементам с помощью операции ++ и использовать оператор * для доступа к символам. Если посмотреть на примеры кода, связанного с классом Document, то мы действительно можем заменить наш класс vector классом list или string без каких-либо проблем. Такая взаимозаменяемость является фундаментальным преимуществом, потому что она позволяет нам сделать выбор, ориентируясь на эффективность. Но, перед тем как рассматривать вопросы эффективности, мы должны рассмотреть логические возможности этих типов: что такого может делать каждый из них, чего не могут другие?

• Elem[]. Не знает своего размера. Не имеет функций begin(), end() и других контейнерных функций-членов. Не может систематически проверять выход за пределы допустимого диапазона. Может передаваться функциям, написанным на языке C или в стиле языка C. Элементы в памяти располагаются последовательно в смежных ячейках. Размер массива фиксируется на этапе компиляции. Операции сравнения (== и !=) и вывода (<<) используют указатель на первый элемент массива, а не на все элементы.

• vector. Может выполнять практически все, включая функции insert() и erase(). Предусматривает индексирование. Операции над списками, такие как insert() и erase(), как правило, связаны с перемещением элементов (что может оказаться неэффективным для крупных элементов и при большом количестве элементов). Может проверять выход за пределы допустимого диапазона. Элементы в памяти располагаются последовательно в смежных ячейках. Объект класса vector может увеличиваться (например, использует функцию push_back()). Элементы вектора хранятся в массиве (непрерывно). Сравнение элементов осуществляется с помощью операторов ==, !=, <, <=, > и >=.

• string. Предусматривает все обычные и полезные операции, а также специфические манипуляции текстами, такие как конкатенация (+ и +=). Элементы хранятся в смежных ячейках памяти. Объект класса string можно увеличивать. Сравнение элементов осуществляется с помощью операторов ==, !=, <, <=, > и >=.

• list. Предусматривает все обычные и полезные операции, за исключением индексирования. Операции insert() и delete() можно выполнять без перемещения остальных элементов. Для хранения каждого элемента необходимы два дополнительных слова (для указателей на узлы). Объект класса list можно увеличивать. Сравнение элементов осуществляется с помощью операторов (==, !=, <, <=, > и >=).

Как мы уже видели (см. разделы 17.2 и 20.5), массивы полезны и необходимы для управления памятью на самом нижнем уровне, а также для обеспечения взаимодействия с программами, написанными на языке C (подробнее об этом — в разделах 27.1.2 и 27.5). В отличие от этого, класс vector является более предпочтительным, потому что его легче использовать, к тому же он более гибкий и безопасный.

ПОПРОБУЙТЕ

Что означает этот список отличий в реальном коде? Определите массивы объектов типа char, vector, list и string со значением "Hello", передайте его в функцию в качестве аргумента, напишите количество символов в передаваемой строке, попытайтесь сравнить его со строкой "Hello" в функции (чтобы убедиться, что вы действительно передали строку "Hello"), а затем сравните аргумент со строкой "Howdy", чтобы увидеть, какое из этих слов появляется в словаре первым. Скопируйте аргумент в другую переменную того же типа.

ПОПРОБУЙТЕ

Выполните предыдущее задание ПОПРОБУЙТЕ для массива объектов типа int, vector и list со значениями { 1, 2, 3, 4, 5 } . 

20.7.1. Операции insert и erase

 В качестве контейнера по умолчанию используется стандартный класс vector. Он имеет большинство желательных свойств, поэтому альтернативу следует использовать только при необходимости. Его основной недостаток заключается в том, что при выполнении операций, характерных для списка (insert() и erase()), в векторе происходит перемещение остальных элементов; это может оказаться связано с неприемлемыми затратами, если вектор содержит большое количество элементов или элементы вектора сами являются крупными объектами. Однако слишком беспокоиться об этом не следует. Мы без заметных проблем считали полмиллиона значений с плавающей точкой в вектор, используя функцию push_back(). Измерения подтвердили, что предварительное выделение памяти не приводит к заметным последствиям. Прежде чем вносить значительные изменения, стремясь к эффективности, проведите измерения (угадать степень эффективности кода трудно даже экспертам).

 Как указывалось в разделе 20.6, перемещение элементов связано с логическим ограничением: выполняя операции, характерные для списков (такие как insert(), erase(), and push_back()), не следует хранить итераторы или указатели на элементы вектора. Если элемент будет перемещен, ваш итератор или указатель будет установлен на неправильный элемент или вообще может не ссылаться на элемент вектора. В этом заключается принципиальное преимущество класса list (и класса map; см. раздел 21.6) над классом vector. Если вам необходима коллекция крупных объектов или приходится ссылаться на объекты во многих частях программы, рассмотрите возможность использовать класс list.

Сравним функции insert() и erase() в классах vector и list. Сначала рассмотрим пример, разработанный специально для того, чтобы продемонстрировать принципиальные моменты.

vector::iterator p = v.begin();  // получаем вектор
++p; ++p; ++p;                        // устанавливаем итератор
                                      // на 4-й элемент
vector::iterator q = p;
++q;                                  // устанавливаем итератор
                                      // на 5-й элемент

p = v.insert(p,99); // итератор p ссылается на вставленный элемент

Теперь итератор q является неправильным. При увеличении размера вектора элементы могли быть перемещены в другое место. Если вектор v имеет запас памяти, то он будет увеличен на том же самом месте, а итератор q скорее всего будет ссылаться на элемент со значением 3, а не на элемент со значением 4, но не следует пытаться извлечь из этого какую-то выгоду.

p = v.erase(p); // итератор p ссылается на элемент,
                // следующий за стертым

Иначе говоря, если за функцией insert() следует функция erase(), то содержание вектора не изменится, но итератор q станет некорректным. Однако если между ними мы переместим все элементы вправо от точки вставки, то вполне возможно, что при увеличении размера вектора v все элементы будут размещены в памяти заново.

Для сравнения мы проделали то же самое с объектом класса list:

list::iterator p = v.begin(); // получаем список
++p; ++p; ++p;                     // устанавливаем итератор
                                   // на 4-й элемент
list::iterator q = p;
++q;                               // устанавливаем итератор
                                   // на 5-й элемент

p = v.insert(p,99); // итератор р ссылается на вставленный элемент

Обратите внимание на то, что итератор q по-прежнему ссылается на элемент, имеющий значение 4.

p = v.erase(p);  // итератор р ссылается на элемент, следующий
                 // за удаленным

И снова мы оказались там, откуда начинали. Однако, в отличие от класса vector, работая с классом list, мы не перемещали элементы, и итератор q всегда оставался корректным.

 Объект класса list занимает по меньшей мере в три раза больше памяти, чем остальные три альтернативы, — в компьютере объект класса list использует 12 байтов на элемент; объект класса vector — один байт на элемент. Для большого количества символов это обстоятельство может оказаться важным. В чем заключается преимущество класса vector над классом string? На первый взгляд, список их возможностей свидетельствует о том, что класс string может делать все то же, что и класс vector, и даже больше. Это оказывается проблемой: поскольку класс string может делать намного больше, его труднее оптимизировать. Оказывается, что класс vector можно оптимизировать с помощью операций над памятью, таких как push_back(), а класс string — нет. В то же время в классе string можно оптимизировать копирование при работе с короткими строками и строками в стиле языка C. В примере, посвященном текстовому редактору, мы выбрали класс vector, так как использовали функции insert() и delete(). Это решение объяснялось вопросами эффективности. Основное логическое отличие заключается в том, что мы можем создавать векторы, содержащие элементы практически любых типов. У нас появляется возможность выбора, только если мы работаем с символами. В заключение мы рекомендуем использовать класс vector, а не string, если нам нужны операции на строками, такие как конкатенации или чтение слов, разделенных пробелами.

20.8. Адаптация нашего класса vector к библиотеке STL

После добавления функций begin(), end() и инструкций typedef в разделе 20.5 в классе vector не достает только функций insert() и erase(), чтобы стать близким аналогом класса std::vector.

template> class vector {
  int sz;    // размер
  T* elem;   // указатель на элементы
  int space; // количество элементов плюс количество свободных ячеек
  A alloc;   // использует распределитель памяти для элементов
public:
  // ...все остальное описано в главе 19 и разделе 20.5...
  typedef T* iterator; // T* — максимально простой итератор

  iterator insert(iterator p, const T& val);
  iterator erase(iterator p);
};

Здесь мы снова в качестве типа итератора использовали указатель на элемент типа T*. Это простейшее из всех возможных решений. Разработку итератора, проверяющего выход за пределы допустимого диапазона, читатели могут выполнить в качестве упражнения (упр. 20).

 Как правило, люди не пишут операции над списками, такие как insert() и erase(), для типов данных, хранящихся в смежных ячейках памяти, таких как класс vector. Однако операции над списками, такие как insert() и erase(), оказались несомненно полезными и удивительно эффективными при работе с небольшими векторами или при небольшом количестве элементов. Мы постоянно обнаруживали полезность функции push_back(), как и других традиционных операций над списками.

По существу, мы реализовали функцию vector::erase(), копируя все элементы, расположенные после удаляемого элемента (переместить и удалить). Используя определение класса vector из раздела 19.3.6 с указанными добавлениями, получаем следующий код:

template
vector::iterator vector::erase(iterator p)
{
  if (p==end()) return p;
  for (iterator pos = p+1; pos!=end(); ++pos)
    *(pos–1) = *pos; // переносим элемент на одну позицию влево
  alloc.destroy(&*(end()-1)); // уничтожаем лишнюю копию
                              // последнего элемента
  ––sz;
  return p;
}

Этот код легче понять, если представить его в графическом виде.

Код функции erase() довольно прост, но, возможно, было бы проще попытаться разобрать несколько примеров на бумаге. Правильно ли обрабатывается пустой объект класса vector? Зачем нужна проверка p==end()? Что произойдет после удаления последнего элемента вектора? Не было бы легче читать этот код, если бы мы использовали индексирование?

Реализация функции vector::insert() является немного более сложной.

template
vector::iterator vector::insert(iterator p, const T& val)
{
  int index = p–begin();
  if (size()==capacity())
    reserve(size() = 0 ? 8 : 2*size()); // убедимся, что
                                        // есть место
  // сначала копируем последний элемент в неинициализированную ячейку:
  alloc.construct(elem+sz,*back());
  ++sz;
  iterator pp = begin()+index; // место для записи значения val
  for (iterator pos = end()–1; pos!=pp; ––pos)
    *pos = *(pos–1); // переносим элемент на одну позицию вправо
  *(begin()+index) = val; // "insert" val
  return pp;
}

Обратите внимание на следующие факты.

• Итератор не может ссылаться на ячейку, находящуюся за пределами последовательности, поэтому мы используем указатели, такие как elem+space. Это одна из причин, по которым распределители памяти реализованы на основе указателей, а не итераторов.

• Когда мы используем функцию reserve(), элементы могут быть перенесены в новую область памяти. Следовательно, мы должны запомнить индекс вставленного элемента, а не итератор, установленный на него. Когда элементы вектора перераспределяются в памяти, итераторы, установленные на них, становятся некорректными — их можно интерпретировать как ссылки на старые адреса.

• Наше использование распределителя памяти A является интуитивным, но не точным. Если вам придется реализовывать контейнер, то следует внимательно изучить стандарт.

• Тонкости, подобные этим, позволяют избежать непосредственной работы с памятью на нижнем уровне. Естественно, стандартный класс vector, как и остальные стандартные контейнеры, правильно реализует эти важные семантические тонкости. Это одна из причин, по которым мы настоятельно рекомендуем использовать стандартную библиотеку, а не “кустарные” решения.

По причинам, связанным с эффективностью, мы не должны применять функции insert() и erase() к среднему элементу вектора, состоящего из 100 тыс. элементов; для этого лучше использовать класс list (и класс map; см. раздел 21.6). Однако операции insert() и erase() можно применять ко всем векторам, а их производительность при перемещении небольшого количества данных является непревзойденной, поскольку современные компьютеры быстро выполняют такое копирование (см. упр. 20). Избегайте (связанных) списков, состоящих из небольшого количества маленьких элементов.

20.9. Адаптация встроенных массивов к библиотеке STL

Мы многократно указывали на недостатки встроенных массивов: они неявно преобразуют указатели при малейшем поводе, их нельзя скопировать с помощью присваивания, они не знают своего размера (см. раздел 20.5.2) и т.д. Кроме того, мы отмечали их преимущества: они превосходно моделируют физическую память.

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

template  // не вполне стандартный массив
struct array {
  typedef T value_type;
  typedef T* iterator;
  typedef T* const_iterator;
  typedef unsigned int size_type; // тип индекса

  T elems[N];
  // не требуется явное создание/копирование/уничтожение

  iterator begin() { return elems; }
  const_iterator begin() const { return elems; }
  iterator end() { return elems+N; }
  const_iterator end() const { return elems+N; }

  size_type size() const;

  T& operator[](int n) { return elems[n]; }
  const T& operator[](int n) const { return elems[n]; }

  const T& at(int n) const;  // доступ с проверкой диапазона
  T& at(int n);              // доступ с проверкой диапазона

  T * data() { return elems; }
  const T * data() const { return elems; }
};

Это определение не полно и не полностью соответствует стандарту, но оно хорошо иллюстрирует основную идею. Кроме того, оно позволяет использовать класс array, если его нет в вашей стандартной библиотеке. Если же он есть, то искать его следует в заголовке . Обратите внимание на то, что поскольку объекту класса array известен его размер N, мы можем (и должны) предусмотреть операторы =, ==, != как для класса vector.

Например, используем массив со стандартной функцией high() из раздела 20.4.2:

void f()
{
  array a = { 0.0, 1.1, 2.2, 3.3, 4.4, 5.5 };
  array::iterator p = high(a.begin(), a.end());
  cout << " максимальное значение " << *p << endl;
}

Обратите внимание на то, что мы не думали о классе array, когда писали функцию high(). Возможность применять функцию high() к объекту класса array является простым следствием того, что в обоих случаях мы придерживались стандартных соглашений.

20.10. Обзор контейнеров

В библиотеке STL есть несколько контейнеров.

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

Austern, Matt, ed. “Technical Report on C++ Standard Library Extensions,” ISO/IEC PDTR 19768. (Colloquially known as TR1.)

Austern, Matthew H. Generic Programming and the STL. Addison-Wesley, 1999. ISBN 0201309564. Koenig, Andrew, ed. The C++ Standard. Wiley, 2003. ISBN 0470846747. (Not suitable for novices.)

Lippman, Stanley B., Josée Lajoie, and Barbara E. Moo. The C++ Primer. AddisonWesley, 2005. ISBN 0201721481. (Use only the 4th edition.)

Musser, David R., Gillmer J. Derge, and Atul Saini. STL Tutorial and Reference Guide: C++ Programming with the Standard Template Library, Second Edition. AddisonWesley, 2001. ISBN 0201379236.

Stroustrup, Bjarne. The C++ Programming Language. Addison-Wesley, 2000. ISBN 0201700735.

Документацию о реализации библиотеки STL и библиотеки потоков ввода-вывода компании SGI (Silicon Graphics International) можно найти на веб-странице www.sgi.com/tech/stl>. Обратите внимание, что на этой веб-странице приводятся законченные программы.

Документацию о реализации библиотеки STL компании Dinkumware можно найти на веб-странице www.dinkumware.com/manuals/default.aspx. (Имейте в виду, что существует несколько версий этой библиотеки.)

Документацию о реализации библиотеки STL компании Rogue Wave можно найти на веб-странице www2.roguewave.com/support/docs/index.cfm.

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

С другой стороны, вы обнаружите, что, освоив классы vector, list и map, а также стандартные алгоритмы, описанные в главе 21, вы легко научитесь работать с остальными контейнерами из библиотеки STL. Вы обнаружите также, что знаете все, что требуется для работы с нестандартными контейнерами, и сможете их программировать сами.

 Что такое контейнер? Определение этого понятия можно найти в любом из указанных выше источников. Здесь лишь дадим неформальное определение. Итак, контейнер из библиотеки STL обладает следующими свойствами.

• Представляет собой последовательность элементов [begin():end()].

• Операции над контейнером копируют элементы. Копирование можно выполнить с помощью присваивания или конструктора копирования.

• Тип элементов называется value_type.

• Контейнер содержит типы итераторов с именами iterator и const_iterator. Итераторы обеспечивают операции *, ++ (как префиксные, так и постфиксные), == и != с соответствующей семантикой. Итераторы для класса list также предусматривают оператор – для перемещения по последовательности в обратном направлении; такие итераторы называют двунаправленными (bidirectional iterator). Итераторы для класса vector также предусматривает операции ––, [], + и -. Эти итераторы называют итераторами с произвольным доступом (random-access iterators) (см. раздел 20.10.1).

• Контейнеры имеют функции insert() и erase(), front() и back(), push_back() и pop_back(), size() и т.д.; классы vector и map также обеспечивают операцию индексирования (например, оператор []).

• Контейнеры обеспечивают операторы (==, !=, <, <=, > и >=) для сравнения элементов. Контейнеры используют лексикографическое упорядочивание для операций <, <=, > и >=; иначе говоря, они сравнивают элементы, чтобы начинать перемещение с первого элемента.

• Цель этого списка — дать читателям некий обзор. Более детальная информация приведена в приложении Б. Более точная спецификация и полный список операций приведены в книге The C++ Programming Language или в стандарте.

Некоторые типы данных имеют многие свойства стандартных контейнеров, но не все. Мы иногда называем их “почти контейнерами”. Наиболее интересными среди них являются следующие.

Кроме того, многие люди и организации разрабатывают собственные контейнеры, удовлетворяющие или почти удовлетворяющие требованиям стандарта.

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

20.10.1. Категории итераторов

Мы говорили об итераторах так, будто все они являются взаимозаменяемыми. Однако они эквивалентны только с точки зрения простейших операций, таких как перемещение по последовательности с однократным считыванием каждого элемента. Если вы хотите большего, например перемещаться в обратном направлении или обеспечить произвольный доступ, то вам нужны более совершенные итераторы.

Глядя на предусмотренные операции, легко убедиться в том, что вместо итераторов для записи или чтения можно использовать двунаправленный итератор. Кроме того, двунаправленный итератор также является однонаправленным, а итератор с произвольным доступом — двунаправленным. В графическом виде категории итераторов можно изобразить следующим образом:

Обратите внимание на то, что категории итераторов не являются классами. Это не иерархия классов, реализованных с помощью наследования.

Задание

1. Определите массив чисел типа int с десятью элементами { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }.

2. Определите объект класса vector с этими же десятью элементами.

3. Определите объект класса list с этими же десятью элементами.

4. Определите второй массив, вектор и список, каждый из которых инициализируется первым массивом, вектором или списком соответственно.

5. Увеличьте значение каждого элемента в массиве на два; увеличьте значение каждого элемента в массиве на три; увеличьте значение каждого элемента в массиве на пять.

6. Напишите простую операцию copy()

template
Iter2 copy(Iter f1, Iter1 e1, Iter2 f2);

копирующую последовательность [f1,e1] в последовательность [f2,f2+(e1–f1)] и, точно так же, как стандартная библиотечная функция копирования, возвращающую число f2+(e1–f1). Обратите внимание на то, что если f1==e1, то последовательность пуста и копировать нечего.

7. Используйте вашу функцию copy() для копирования массива в вектор или списка — в массив.

8. Используйте стандартную библиотечную функцию find() для того, чтобы убедиться, что вектор содержит значение 3, и выведите на экран соответствующую позицию этого числа в векторе, если это число в нем есть. Используйте стандартную библиотечную функцию find(), чтобы убедиться, что список содержит значение 27, и выведите на экран соответствующую позицию этого числа в списке, если это число в нем есть. Позиция первого элемента равна нулю, позиция второго элемента равна единице и т.д. Если функция find() возвращает итератор, установленный на конец последовательности, то значение в ней не найдено. Не забывайте тестировать программу после каждого этапа.

Контрольные вопросы

1. Почему программы, написанные разными людьми, выглядят по-разному? Приведите примеры.

2. Какие простые вопросы мы обычно задаем, думая о данных?

3. Перечислите разные способы хранения данных?

4. Какие основные операции можно выполнить с коллекцией данных?

5. Каких принципов следует придерживаться при хранении данных?

6. Что такое последовательность в библиотеке STL?

7. Что такое итератор в библиотеке STL? Какие операции поддерживают итераторы?

8. Как установить итератор на следующий элемент?

9. Как установить итератор на предыдущий элемент?

10. Что произойдет, если вы попытаетесь установить итератор на ячейку, следующую за концом последовательности?

11. Какие виды итераторов могут перемещаться на предыдущий элемент?

12. Почему полезно отделять данные от алгоритмов?

13. Что такое STL?

14. Что такое связанный список? Чем он в принципе отличается от вектора?

15. Что такое узел (в связанном списке)?

16. Что делает функция insert()? Что делает функция erase()?

17. Как определить, что последовательность пуста?

18. Какие операции предусмотрены в итераторе для класса list?

19. Как обеспечить перемещение по контейнеру, используя библиотеку STL?

20. В каких ситуациях лучше использовать класс string, а не vector?

21. В каких ситуациях лучше использовать класс list, а не vector?

22. Что такое контейнер?

23. Что должны делать функции begin() и end() в контейнере?

24. Какие контейнеры предусмотрены в библиотеке STL?

25. Перечислите категории итераторов? Какие виды итераторов реализованы в библиотеке STL?

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

Термины

Упражнения

1. Если вы еще не выполнили задания из врезок ПОПРОБУЙТЕ, то сделайте это сейчас.

2. Попробуйте запрограммировать пример с Джеком и Джилл из раздела 20.1.2. Для тестирования используйте несколько небольших файлов.

3. Проанализируйте пример с палиндромом (см. раздел 20.6); еще раз выполните задание из п. 2, используя разные приемы.

4. Найдите и исправьте ошибки, сделанные в примере с Джеком и Джилл в разделе 20.3.1, используя приемы работы с библиотекой STL.

5. Определите операторы ввода и вывода (>> и <<) для класса vector.

6. Напишите операцию “найти и заменить” для класса Document, используя информацию из раздела 20.6.2.

7. Определите лексикографически последнюю строку в неупорядоченном классе vector.

8. Напишите функцию, подсчитывающую количество символов в объекте класса Document.

9. Напишите программу, подсчитывающую количество слов в объекте класса Document. Предусмотрите две версии: одну, в которой слово — это последовательность символов, разделенных пробелами, и вторую, в которой слово — это неразрывная последовательность символов из алфавита. Например, при первом определении выражения alpha.numeric и as12b — это слова, а при втором — каждое из них рассматривается как два слова.

10. Напишите программу, подсчитывающую слова, в которой пользователь мог бы сам задавать набор символов-разделителей.

11. Создайте объект класса vector и скопируйте в него элементы списка типа list, передавая его как параметр (по ссылке). Проверьте, что копия полна и верна. Затем выведите на экран элементы в порядке возрастания их значений.

12. Завершите определение класса list из разделов 20.4.1 и 20.4.2 и продемонстрируйте работу функции high(). Выделите память для объекта класса Link, представляющего узел, следующий за концом списка.

13. На самом деле в классе list нам не нужен реальный объект класса Link, расположенный за последним элементом. Модифицируйте свое решение из предыдущего упражнения так, чтобы в качестве указателя на несуществующий объект класса Link (list::end()) использовалось значение 0; иначе говоря, размер пустого списка может быть равен размеру отдельного указателя.

14. Определите односвязный список slist, ориентируясь на стиль класса std::list. Какие операции из класса list стоило бы исключить из класса slist, поскольку он не содержит указателя на предыдущий элемент?

15. Определите класс pvector, похожий на вектор указателей, за исключением того, что он содержит указатели объекта и каждый объект уничтожается его деструктором.

16. Определите класс ovector, похожий на класс pvector, за исключением того, что операции [ ] и * возвращают не указатели, а ссылки на объект, на который ссылается соответствующий элемент.

17. Определите класс ownership_vector, хранящий указатели на объект как и класс pvector, но предусматривающий механизм, позволяющий пользователю решить, какие объекты принадлежат вектору (т.е. какие объекты удалены деструктором). Подсказка: это простое упражнение, если вы вспомните главу 13.

18. Определите итератор с проверкой выхода за пределы допустимого диапазона для класса vector (итератор с произвольным доступом).

19. Определите итератор с проверкой выхода за пределы допустимого диапазона для класса list (двунаправленный итератор).

20. Выполните эксперимент, посвященный сравнению временных затрат при работе с классами vector и list. Способ измерения длительности работы программы изложен в разделе 26.6.1. Сгенерируйте N случайных целых чисел в диапазоне [0:N]. Вставьте каждое сгенерированное число в вектор vector (после каждой вставки увеличивающийся на один элемент). Храните объект класса vector в упорядоченном виде; иначе говоря, значение должно быть вставлено так, чтобы все предыдущие значения были меньше или равны ему, а все последующие значения должны быть больше него. Выполните тот же эксперимент, используя класс list для хранения целых чисел. При каких значениях N класс list обеспечивает более высокое быстродействие, чем класс vector? Попробуйте объяснить результаты эксперимента. Впервые этот эксперимент был предложен Джоном Бентли (John Bentley).

Послесловие

Если бы у нас было N видов контейнеров, содержащих данные, и M операций, которые мы хотели бы над ними выполнить, то мы могли бы легко написать N*M фрагментов кода. Если бы данные имели K разных типов, то нам пришлось бы написать N*M*K фрагментов кода. Библиотека STL решает эту проблему, разрешая задавать тип элемента в виде параметра (устраняя множитель K) и отделяя доступ к данным от алгоритмов. Используя итераторы для доступа к данным в любом контейнере и в любом алгоритме, мы можем ограничиться N+M алгоритмами. Это огромное облегчение. Например, если бы у нас было 12 контейнеров и 60 алгоритмов, то прямолинейный подход потребовал бы создания 720 функций, в то время как стратегия, принятая в библиотеке STL, требует только 60 функций и 12 определений итераторов: тем самым мы экономим 90% работы. Кроме того, в библиотеке STL приняты соглашения, касающиеся определения алгоритмов, упрощающие создание корректного кода и облегчающие его композицию с другими кодами, что также экономит много времени.

Глава 21