11.2. Списки.

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

Большинство алгоритмов работы с векторами не применимы к спискам, в особенности это относится к функциям sort() и binary_search(), по причине того, что списки не обладают возможностью быстрого доступа к произвольному элементу. Сортировка STL-списков выполняется функцией sort().

Класс списка в STL называется как std::list<T>, и определен в заголовке <list>. Например:

  list<Film> films;
      

Эквивалентный класс в Qt -- QValueList<T>;:

  QValueList<Film> films;
      

Новый элемент может быть добавлен в список вызовом функции push_back() или insert(). В отличие от векторов, вставка элемента в начало или в середину списка выполняется так же быстро, как и добавление элемента в конец списка.

В STL, списки не имеют оператора "[ ]", поэтому, для выбора нужного элемента приходится использовать итераторы. (Списки Qt поддерживают оператор "[ ]", но на больших списках он может работать очень медленно.) Синтаксис и порядок использования аналогичен векторам, например:

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

Списки предоставляют практически тот же набор функций, что и векторы, включая empty(), size(), erase() и clear(). Функция find() так же имеется.

Некоторые функции Qt возвращают QValueList<T>. Если есть необходимость пройти в цикле по списку, то нужно создать копию списка и выполнить проход по копии. Ниже представлен пример корректной работы со списком QValueList<int>, который возвращает QSplitter::sizes():

  QValueList<int> list = splitter->sizes(); 
  QValueList<int>::const_iterator it = list.begin(); 
  while (it != list.end()) { 
    do_something(*it); 
    ++it; 
  }
      

Следующий код -- неправильный:

  // НЕВЕРНО!
  QValueList<int>::const_iterator it = splitter->sizes().begin(); 
  while (it != splitter->sizes().end()) { 
    do_something(*it); 
    ++it; 
  }
      

Это происходит потому, что QSplitter::sizes() возвращает результат по значению. Если не сохранить его копию, C++ автоматически удалит его еще до того как начнется итерация. Всегда создавайте копию контейнера, возвращаемого по значению, когда требуется получить для него итератор.

На первый взгляд, операция создания копии может показаться ресурсоемкой, но это не так, благодаря тому, что Qt использует оптимизацию, которая называется implicit sharing (неявное совместное использование данных). Суть оптимизации заключается в том, что фактически, операция копирования может и не производиться, не смотря на то, что программа запросила ее.

Класс QStringList, широко используемый в Qt, это дочерний класс QValueList<QString>. Он расширяет набор методов предка своими, дополнительными функциями, которые делают этот класс очень мощным инструментом. Более подробно мы расскажем о нем в последнем разделе этой главы.