Последовательные контейнеры. Списки

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

   
Класс 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. Результат работы приложения

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

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



Вы можете оставить комментарий, или Трекбэк с вашего сайта.

Оставить комментарий