На этом шаге мы рассмотрим использование списков.

    Класс list реализуется в виде двусвязного списка элементов. Это означает, что каждый элемент списка занимает отдельный блок памяти и содержит ссылки на предыдущий и следующий элементы. Списки не поддерживают произвольный доступ к элементам. Например, чтобы обратиться к десятому элементу, необходимо сначала перебрать первые девять элементов по цепочке ссылок. Тем не менее переход к следующему или предыдущему элементу выполняется с постоянным временем, поэтому обобщенная операция доступа к произвольному элементу имеет линейную сложность (среднее расстояние перехода пропорционально количеству элементов). Это гораздо хуже, чем амортизированное постоянное время доступа, обеспечиваемое векторами и деками.

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

    В следующем примере мы создаем пустой список символов, заносим в него символы от "а" до "z" и выводим все элементы в цикле, который в каждой итерации выводит и удаляет первый элемент коллекции.

//---------------------------------------------------------------------------

#include <vcl.h>
#include <iostream>
#include <list>
#include <conio.h> //необходимо для getch()
#pragma hdrstop

//---------------------------------------------------------------------------

#pragma argsused
using namespace std;
std::string ToRus(const std::string &in)
{
  char *buff = new char [in.length()+1];
  CharToOem(in.c_str(),buff);
  std::string out(buff);
  delete [] buff;
  return out;
}

int main(int argc, char* argv[])
{
  list<char> coll; // Список с символьными элементами
  // Присоединение элементов от 'a' по 'z'
  for (char c='a'; c<='z'; ++c) {
    coll.push_back(c);
  }
  cout << ToRus("Элементы списка: ");
  // Вывод содержимого списка:
  // пока в списке остаются элементы,
  // вывести и удалить первый элемент.
  while (!coll.empty()) {
    cout << coll.front() << ' ';
    coll.pop_front();
  }
  cout << endl;

  getch();
  return 0;
}
//---------------------------------------------------------------------------

    Как обычно, заголовочный файл <list> используется для определения коллекции типа list, содержащей символьные элементы:

  list <char> coll;

    Функция empty() возвращает логический признак отсутствия элементов в контейнере. Цикл выполняется до тех пор, пока функция возвращает false(), то есть пока контейнер содержит элементы:

  while (!coll.empty()) {
    .    .    .
  }

    В теле цикла функция front() возвращает первый элемент:

    cout << coll.front() << ' ';

    Функция pop_front() удаляет первый элемент из контейнера:

    coll.pop_front();

    Учтите, что функция pop_front() не возвращает удаляемый элемент, поэтому эти две команды не удается заменить одной командой.

    Результат выполнения программы зависит от кодировки. В кодировке ASCII он выглядит так:

Рис.1. Результат работы приложения

    Конечно, процедура "вывода" содержимого цикла, которая выводит и удаляет первый элемент, выглядит несколько странно - обычно в цикле перебираются все элементы. Тем не менее списки не поддерживают произвольный доступ к элементам, поэтому оператор [] будет работать недостаточно эффективно. Существует другой способ перебора и вывода элементов, основанный на применении итераторов.

    На следующем шаге мы рассмотрим строки.

Предыдущий шаг Содержание Следующий шаг