14.4. Списки

Класс list поддерживает двунаправленный линейный список. В отличии от

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

Ниже представлена спецификация шаблона для класса list:

teinplate<class T, class Allocator r<T claS3 list

Здесь Т - это тип данных, предназначенных для хранения в списке, а ключевое слово Allocator задает распределитель памяти, которхй по умолчанию является стандартным распределителем памяти. В классе list определены следующие конструкторы:

explicit (const Allocator Sa - Allocator О) ; - ,

explicit type vjicyio, const T vatate = TO ,

const Allocator =

list (const list<T, Allocator>fio*bejc!r) ;

teii55late<Glass Inltar>liet (Inlter начало, Inlter конец,

const Allocator fia = Allocator () ) ;

Первая форма представляет собой конструктор пустого списка. Вторая форма - конструктор списка, число элементов которого - это число, а каждый элемент равен значению значение, которое может быть значением по умолчанию. Третья форма конструктора предназначена для списка из одинаковых элементов, каждый из которхх - это объект. Четвертая форма - это конструктор списка, содержащего диапазон элементов, заданный итераторами начало и конец.

2. В примере 4 для класса Demo были определены два конструктора - конструктор по умолчанию (конструктор без параметров) и конструктор с параметрами. Сможете ли вы объяснить, почему это так важно?

3. Ниже представлен пример класса Coord. Напишите программу для хранения

объектов типа Coord в векторе. (Подсказка: не забудьте для класса Coord определить операторы < и ==.)

. . i , i . , . -Hi

class Coord ( . М... ;.

public: ~ i. - <к

int x, у; .\

Coord () { X = у = 0; }

Coord(int a, int b) { x = a; у b; }

>;

Для класс51 определяются следующие операторы сравнения:

В табл. 14.3 представлены функции - члены класса list. Размешать элементы в конце списка можно с помощью функции push back() (как и в случае с вектором), в начале - с помощью функции ront(), а в середине - с помощью функции insertO. Для соединения (Join) двух списков нужна функция spliceO, а для слияния (merge) - функция merge().

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

Таблиц М.З. Функции - членсса list

Функция-член

Описание

template<class lnlter>

void assign(lnlter начало,

Inlter конец);

teniplate<cla8s Size, class T> void assign (Size число,

const T &значение - T())j

reference back(); const reference back() const;

iterator begln(); constjterator begln(} const;

void clear();

bool emptyO const; ,

iterator end(); const lterator end(} const;

Iterator erase (iterator /);

iterator erase (Iterator начало, iterator кОНвм]\

reference front(); const reference front() const;

allocator type

get atlocator() const;

Присваивает списку тельность, определенную итераторами начало и конец

Присваивает списку число элементов, причем значение каждого элемента равно параметру значение

Возвращает ссылку списка

на последний элемент

Возвращает итератор первого элемента списка

Удаляет все элементы списка

Возвращает истину, если вызывающий список пуст, в противном случае возвращает ложь

Возвращает итератор конца списка

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

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

Возвращает ссылку на первый элемент списка

Возвращает распределитель памяти списка

Таблица Ы. 3(продолжение)

Функция-член

Описание

iterator insert(lterator /,

const Т значение = Т());

void insert(iterator i,

size type число, const T значение];

template<clas8 lnlter> void insert(iterator/,

Inlter начало, Inlter конец);

size typ sizeO const;

void merge(ffst<T,

Allooator> &объект)\ template<class Conip>

void merge(llst<T, Allooator> Аобъект,

Comp Ф сравн];

void void

void push back(const

Т &зиачвиив);

void pus)iJront(const

T Лзначение);

reversejterator rbeglnf); const.reversejterator

rbegInO const;

void remove(const

T Дэначенив);

template<class UnPred> void reinoveJf(UnPred пред);

reverseiterator rend(); oonst reverse iterator

rendO const;

void resize(size type число,

T значение = T{));

void reverseO;

Вставляет параметр значение перед элементом, заданным итератором i. Возвращает итератор элемента

Вставляет число копий параметра значение перед элементом, заданным итератором i

Вставляем тельность, определенную между итераторами начало и конец, перед

элементом, заданным итератором i

Возвращает максимальное число элементов, которое может храниться в списке

Выполняет слияние упорядоченного списка, хранящегося в объекте объект, с вызывающим упорядоченным списком. Результат упорядочивается. После слияния список, хранящийся в объекте объект становится пустым. Во второй форме для определения того, является ли значение одного элемента меньшим, чем значение другого, может задаваться функция сравнения ф сравн

Удаляет последний элемент списка

Удаляет первый элемент списка

Добавляет в конец списка элемент, значение которого равно параметру значение

Добавляет в начало списка элемент, значение которого равно параметру значение

Возвращает обратный итератор конца списка

Удаляет из списка элементы, значения которых равны параметру значение

Удаляет из списка значения, для которых истинно значение унарного предиката пред

Возвращает обратный итератор начала списка

Изменяет размер списка в соответствии с параметром число. Если при этом список удлиняется, то добавляемые в конец списка элементы получают значение, заданное параметром значение

Выполняет реверс (т. е. реализует обратный порядок расположения элементов) вызывающего списка