Говоря так о данных, мы подразумеваем много разных данных: десятки фигур, сотни значений температуры, тысячи регистрационных записей, миллионы точек, миллиарды веб-страниц и т.д.; иначе говоря, мы говорим о работе с контейнерами данных потоками данных и т.д. В частности, мы не рассматриваем вопросы, как лучше выбрать набор данных, представляющих небольшой объект, такой как комплексное число, запись о температуре или окружность. Эти типы описаны в главах 9, 11 и 14.
Рассмотрим простые примеры, которые иллюстрируют наше понятие о крупном наборе данных.
• Сортировка слов в словаре.
• Поиск номера в телефонной книге по заданному имени.
• Поиск максимальной температуры.
• Поиск всех чисел, превышающих 8800.
• Поиск первого появления числа 17.
• Сортировка телеметрических записей по номерам устройств.
• Сортировка телеметрических записей по временным меткам.
• Поиск первого значения, большего, чем строка “Petersen”.
• Поиск наибольшего объема.
• Поиск первого несовпадения между двумя последовательностями.
• Вычисление попарного произведения элементов двух последовательностей.
• Поиск наибольшей месячной температуры.
• Поиск первых десяти лучших продавцов по записям о продажах.
• Подсчет количества появлений слова “Stroustrup” в сети веб.
• Вычисление суммы элементов.
Обратите внимание на то, что каждую из этих задач мы можем описать, не упоминая о способе хранения данных. Очевидно, что мы как-то должны работать со списками, векторами, файлами, потоками ввода и т.д., но мы не обязаны знать, как именно хранятся (и собираются) данные, чтобы говорить о том, что будем делать с ними. Важен лишь тип значений или объектов (тип элементов), способ доступа к этим значениям или объектам, а также что именно мы хотим с ними сделать.
Эти виды задач носят универсальный характер. Естественно, мы хотим написать код, который решал бы эти задачи просто и эффективно. В то же время перед нами, как программистами, стоят следующие проблемы.
• Существует бесконечное множество вариантов типов данных (виды данных).
• Существует огромное количество способов организации коллекций данных.
• Существует громадное количество задач, которые мы хотели бы решить с помощью коллекций данных.
Для того чтобы минимизировать влияние этих проблем, мы хотели бы как можно больше обобщить наш код, чтобы он с одинаковым успехом мог работать с разными типами данных, учитывать разные способы их хранения и решать разные задачи, связанные с обработкой данных. Иначе говоря, мы хотим обобщить наш код, чтобы охватить все варианты. Мы действительно не хотим решать каждую задачу с нуля; это слишком утомительная потеря времени.
Для того чтобы понять, какая поддержка нам нужна, чтобы написать наш код, рассмотрим, что мы можем делать с данными, более абстрактно. Итак, можно сделать следующее.
• Собирать данные в контейнерах
• например, собирать их в объектах классов
vector
,
list
и массивах.
• Организовывать данные
• для печати;
• для быстрого доступа.
• Искать данные
• по индексу (например, найти 42-й элемент);
• по значению (например, найти первую запись, в которой в поле “age” записано число 7);
• по свойствам (например, все записи, в которых значение поля “temperature” больше 32 и меньше 100).
• Модифицировать контейнер
• добавлять данные;
• удалять данные;
• сортировать (в соответствии с каким-то критерием).
• Выполнять простые математические операции (например, умножить все элементы на 1,7).
Мы хотели бы делать все это, не утонув в море информации, касающейся отличий между контейнерами, способами доступа к элементам и их типами. Если нам это удастся, то мы сделаем рывок по направлению к своей цели и получим эффективный метод работы с большими объемами данных.
Оглядываясь назад на методы и инструменты программирования, описанные в предыдущих главах, мы видим, что уже можем писать программы, не зависящие от типа используемых данных. Этот вывод основан на следующих фактах.
• Использование типа
int
мало отличается от использования типа
double
.
• Использование типа
vector<int>
мало отличается от использования типа
vector<string>
.
• Использование массива чисел типа
double
мало отличается от использования типа
vector<double>
.
Мы хотели бы организовать наш код так, чтобы новый код пришлось бы писать, только если нам действительно нужно сделать что-то совершенно новое и резко отличающееся от предыдущих задач. В частности, мы хотели бы иметь код, решающий универсальные задачи программирования, и не переписывать программы каждый раз, когда изменяется способ хранения данных или их интерпретация. В частности, хотелось бы выполнялись следующие условия.
• Поиск значения в объекте класса
vector
не должен отличаться от поиска значения в массиве.
• Поиск объекта класса
string
без учета регистра не должен отличаться от поиска объекта класса
string
с учетом нижнего и верхнего регистров.
• Графическое изображение экспериментальных данных с точными значениями не должно отличаться от графического изображения экспериментальных данных с округленными значениями.
• Копирование файла не должно отличаться от копирования вектора.
Учитывая сказанное, мы хотим писать код, удовлетворяющий следующим условиям:
• его легко читать;
• легко модифицировать;
• он имеет систематический характер;
• он короткий;
• быстро работает.
Для того чтобы минимизировать объем работы программиста, мы должны решить следующие задачи.
• Единообразный доступ к данным:
• независимость от способа хранения данных;
• независимость от типа данных.
• Доступ к данным, безопасный с точки зрения типа:
• легкое перемещение по данным;
• компактное хранение данных.
• Скорость работы:
• поиск данных;
• добавление данных;
• удаление данных.
• Стандартные версии большинства широко распространенных алгоритмов таких как
copy
,
find
,
search
,
sort
,
sum
, ...
Библиотека STL обеспечивает не только эти возможности. Мы изучим эту библиотеку не только потому, что она представляет собой очень полезный набор инструментов, но и потому, что является примером максимальной гибкости и эффективности. Библиотека STL была разработана Алексом Степановым (Alex Stepanov) для того, чтобы создать базу для универсальных, правильных и эффективных алгоритмов, работающих с разнообразными структурами данных. Ее целью были простота, универсальность и элегантность математики.
Если бы в нашем распоряжении не было библиотеки с ясно выраженными идеями и принципами, то каждый программист должен был бы разрабатывать каждую программу, используя лишь основные языковые конструкции и придерживаясь идей, которые в данный момент кажутся хорошими. Для этого пришлось бы выполнить много лишней работы. Более того, в результате часто получается беспринципная путаница; часто такие программы не может понять никто, кроме их авторов, и очень сомнительно, что эти программы можно использовать в другом контексте.