11.1. Векторы.

Классы векторов, списков и словарей (map) -- это шаблонные классы, параметризуемые типом объектов, которые предполагается хранить в контейнере. Значения, которые хранятся в контейнерах, могут быть базового типа (например int или double), указателями или классами, которые имеют конструктор по-умолчанию (конструктор, у которого нет входных аргументов или все входные аргументы имеют значения по-умолчанию), конструктор копирования и перегруженный оператор присваивания. Среди классов, которые отвечают этим требованиям, можно назвать QDateTime, QRegExp, QString и QVariant. Классы Qt, которые наследуют QObject, не могут быть помещены в контейнеры, поскольку у них нет конструктора копирования и оператора присваивания. Однако, это не является большой проблемой, поскольку сохраняется возможность помещать в контейнеры указатели этих типов.

В этом разделе мы рассмотрим наиболее общие операции над векторами, а в следующих двух разделах расскажем о списках и словарях (map). Большая часть примеров, рассматриваемых в этой главе, будет основана на классе Film, который хранит название фильма и его продолжительность. (Мы отказались от более подходящего для этого случая названия Movie, потому что это имя очень похоже на QMovie -- класс Qt, который предназначен для показа анимированных изображений.)

Ниже приводится определение класса Film:

class Film 
{ 
public: 
  Film(int id = 0, const QString &title = "", int duration = 0); 
  
  int id() const { return myId; } 
  void setId(int catalogId) { myId = catalogId; } 
  QString title() const { return myTitle; } 
  void setTitle(const QString &title) { myTitle = title; } 
  int duration() const { return myDuration; } 
  void setDuration(int minutes) { myDuration = minutes; } 
  
private: 
  int myId; 
  QString myTitle; 
  int myDuration; 
};

int operator==(const Film &film1, const Film &film2); 
int operator<(const Film &film1, const Film &film2);
      

Мы не включили в класс явное определение конструктора копирования и оператора присваивания, потому что они предоставляются C++ автоматически. Если бы наш класс выполнял дополнительное резервирование памяти, под данные-члены, тогда нам пришлось бы включить в него явную реализацию конструктора копирования и оператора присваивания.

В дополнение к классу мы реализовали два оператора сравнения -- "равно" и "меньше". Оператор "равно" используется для поиска элемента в контейнере. Оператор "меньше" -- используется для нужд сортировки. В данной ситуации нет необходимости реализовать четыре других оператора сравнения ("!=", "<=", ">", ">="), поскольку STL никогда ими не пользуется.

Ниже приводится исходный код трех функций:

Film::Film(int id, const QString &title, int duration) 
{ 
  myId = id; 
  myTitle = title; 
  myDuration = duration; 
} 

int operator==(const Film &film1, const Film &film2) 
{ 
  return film1.id() == film2.id(); 
} 

int operator<(const Film &film1, const Film &film2) 
{ 
  return film1.id() < film2.id(); 
}
      

При сравнивании экземпляров Film, используются их числовые идентификаторы, а не названия, поскольку к названию фильма не предъявляется требование уникальности.
Вектор -- это структура данных, которая хранит элементы, подобно обычному массиву. Главное отличие вектора от массива C++ состоит в том, что вектор всегда "знает", сколько элементов он хранит, и может динамически изменять свой размер. Добавление новых элементов в конец вектора выполняется очень быстро, но операция по вставке новых элементов в начало или в середину вектора требует значительных затрат по времени.

В STL, класс вектора носит имя std::vector<T> и определен в заголовке <vector>. Объявить вектор, который будет хранить массив экземпляров класса Film, можно так:

vector<Film> films;
      

Эквивалентное объявление, использующее класс Qt -- QValueVector<T>:

QValueVector<Film> films;
      

Вектор, созданный подобным образом, изначально имеет размер 0. Если заранее известно количество элементов в векторе, можно явно указать начальный размер в определении и с помощью оператора "[ ]" присвоить значения его элементам.

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

films.push_back(Film(4812, "A Hard Day's Night", 85)); 
films.push_back(Film(5051, "Seven Days to Noon", 94)); 
films.push_back(Film(1301, "Day of Wrath", 105)); 
films.push_back(Film(9227, "A Special Day", 110)); 
films.push_back(Film(1817, "Day for Night", 116));
      

Как правило, Qt предоставляет функции с теми же именами, что и STL, но в некоторых случаях Qt добавляет к классам дополнительные методы, с более интуитивно понятными именами. Например, классы Qt могут добавлять элементы как с помощью метода push_back(), так и с помощью дополнительного метода append().

Еще один способ заполнения вектора состоит в том, чтобы задать при объявлении его начальный размер, а потом выполнить инициализацию отдельных элементов:

vector<Film> films(5);

films[0] = Film(4812, "A Hard Day's Night", 85); 
films[1] = Film(5051, "Seven Days to Noon", 94); 
films[2] = Film(1301, "Day of Wrath", 105); 
films[3] = Film(9227, "A Special Day", 110); 
films[4] = Film(1817, "Day for Night", 116);
      

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

Векторы допускают обход всех элементов в цикле, с использованием оператора "[ ]":

  for (int i = 0; i < (int)films.size(); ++i) 
    cerr << films[i].title().ascii() << endl;
      

В качестве альтернативы -- можно использовать итератор:

  vector<Film>::const_iterator it = films.begin(); 
  while (it != films.end()) { 
    cerr << (*it).title().ascii() << endl; 
    ++it; 
  }
      

Каждый контейнерный класс имеет два типа итераторов: iterator и const_iterator. Различие между ними заключается в том, что const_iterator не позволяет модифицировать элементы вектора.

Функция-член контейнера -- begin() возвращает итератор, который ссылается на первый элемент в контейнере (например, films[0]). Функция-член контейнера -- end() возвращает итератор, который ссылается на элемент "следующий за последним" (например, films[5]). Если контейнер пуст, значения, возвращаемые функциями begin() и end(), эквивалентны. Это обстоятельство может использоваться для проверки наличия элементов в контейнере, хотя для этой цели гораздо удобнее использовать функцию empty().

Итераторы обладают интуитивно понятным синтаксисом, который напоминает синтаксис указателей языка C++. Для перемещения к следующему или предыдущему элементу, можно использовать операторы "++" b "--", а унарный "*" -- для получения доступа к элементу контейнера, находящемуся в позиции итератора.

Если необходимо отыскать некоторый элемент в векторе, можно воспользоваться функцией STL -- find():

  vector<Film>::iterator it = find(films.begin(), films.end(), 
                                      Film(4812)); 
  if (it != films.end()) 
    films.erase(it);
      

Она возвращает итератор, указывающий на первый встретившийся элемент вектора, отвечающий критериям поиска (элементы контейнера сравниваются перегруженным operator==() с последним аргументом функции). Определение функции находится в заголовке <algorithm>, где вы найдете множество других шаблонных функций. Qt предоставляет аналоги некоторых из них, правда под другими именами (например, qFind()). Вы можете использовать их, если не желаете пользоваться библиотекой STL.

Сортировка элементов вектора может быть произведена функцией sort():

  sort(films.begin(), films.end());
      

Для сравнения элементов вектора она использует оператор "<", если явно не указывается другая функция сравнения. На отсортированных векторах, для поиска некоторого элемента может использоваться функция binary_search(). Она дает результат, аналогичный find() (при условии, что в векторе нет двух фильмов с одинаковыми числовыми идентификаторами), но при этом работает намного быстрее.

  int id = 1817; 
  if (binary_search(films.begin(), films.end(), Film(id))) 
    cerr << "Found " << id << endl;
      

В позицию итератора, с помощью функции insert(), может быть вставлен новый элемент или удален существующий, с помощью функции erase():

  films.erase(it);
      

Элементы, которые следуют за удаляемым будут перемещены на одну позицию влево (или выше, если хотите) и размер вектора будет уменьшен на 1 элемент.