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

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

// заполняем вектор, не используя функцию push_back:

vector* p = new vector(10);

int n = 0;    // количество элементов

double d;

while(cin >> d) {

  if (n==p–>size()) {

    vector* q = new vector(p–>size()*2);

    copy(p–>begin(),p–>end(),q–>begin());

    delete p;

    p = q;

  }

  (*p)[n] = d;

  ++n;

}

Это некрасиво. К тому же вы уверены, что этот код правильно работает? Как можно быть в этом уверенным? Обратите внимание на то, что мы внезапно стали использовать указатели и явное управление памятью. Мы были вынуждены это сделать, чтобы имитировать стиль программирования, близкий к машинному уровню при работе с объектами фиксированного размера (массивами; см. раздел 18.5). Одна из причин, обусловивших использование контейнеров, таких как класс vector, заключается в желании сделать нечто лучшее; иначе говоря, мы хотим, чтобы класс vector сам изменял размер контейнера, освободив пользователей от этой работы и уменьшив вероятность сделать ошибку. Иначе говоря, мы предпочитаем контейнеры, которые могут увеличивать свой размер, чтобы хранить именно столько элементов, сколько нам нужно. Рассмотрим пример.

vector vd;

double d;

while(cin>>d) vd.push_back(d);

  Насколько распространенным является изменение размера контейнера? Если такая ситуация встречается редко, то предусматривать для этого специальные средства было бы нецелесообразно. Однако изменение размера встречается очень часто. Наиболее очевидный пример — считывание неизвестного количества значений из потока ввода. Другими примерами являются коллекционирование результатов поиска (нам ведь неизвестно заранее, сколько их будет) и удаление элементов из коллекции один за другим. Таким образом, вопрос заключается не в том, стоит ли предпринимать изменение размера контейнера, а в том, как это сделать.

  Почему мы вообще затронули тему, посвященную изменению размера контейнера? Почему бы просто не выделить достаточно памяти и работать с нею?! Эта стратегия выглядит наиболее простой и эффективной. Тем не менее это оправдано лишь в том случае, если мы не запрашиваем слишком много памяти. Программисты, избравшие эту стратегию, вынуждены переписывать свои программы (если они внимательно и систематически отслеживают переполнение памяти) или сталкиваются с катастрофическими последствиями (если они пренебрегли проверкой переполнения памяти).

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

Структуры данных играют ключевую роль в большинстве важных приложений. О том, как организовать данные, написано множество толстых и полезных книг. В большинстве из них рассматривается вопрос: “Как лучше хранить данные?” Ответ один — нам нужны многочисленные и разнообразные контейнеры, однако это слишком обширная тема, которую в этой книге мы не можем осветить в должной мере. Тем не менее мы уже широко использовали классы vector и string (класс string — это контейнер символов). В следующих главах мы опишем классы list, map (класс map — это дерево, в котором хранятся пары значений) и матрицы. Поскольку нам нужны разнообразные контейнеры, для их поддержки необходимы соответствующие средства языка и технологии программирования. Технологии хранения данных и организации доступа к ним являются одними из наиболее фундаментальных и наиболее сложных форм вычислений.