Программирование

Эта и следующая главы посвящены библиотеке 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;