87.Fds контейнеры шаблонов списков

Контейнер список

template < class T , class A = allocator < T > > сlass list {

...........

public:

// list – имя контейнера,

// T – тип элементов, которые будут храниться в списке,

// A – распределитель памяти.

// Типы

// ……..

// Итераторы

// ……..

//

// Доступ к элементам

//

reference front (); // первый элемент списка

const_reference front () const;

reference back (); // последний элемент списка

const_reference back () const;

//

// Конструкторы и т.п.

//

explicit list (const A&=A()); //создается список нулевой длины

explicit list (size_type n; const T& value = T(); const A& = A());

// создается список из n элементов со значением value (или с "нулями" типа

// Т, если второй параметр отсутствует

template <class I> list (I first, I last, const A& = A()); // инициализация списка копированием элементов из [first, last), I - итератор для чтения

list (const list < T, A > & obj ); // конструктор копирования

list& operator = (const list < T, A > & obj );

~list();

//……

// Некоторые функции-члены класса list

//

iterator erase (iterator i ); // удаляет элемент, на который указывает данный

// итератор. Возвращает итератор элемента, следующего за удаленным.

iterator erase (iterator st, iterator fin); // удалению подлежат все элементы

// между st и fin, но fin не удаляется. Возвращает fin.

Iterator insert ( iterator i , const Т& value = T()); // вставка некоторого

// значения value перед i. Возвращает итератор вставленного элемента).

void insert (iterator i , size_type n, const T&value); // вставка n копий

// элементов со значением value перед i.

void push_back ( const T&value ) ; // добавляет элемент в конец списка

void push_front ( const T&value ) ; // добавляет элемент в начало списка

void pop_back () ; // удаляет последний элемент (не возвращает значение!)

void pop_front () ; // удаляет первый элемент списка

size_type size() const; // выдает количество элементов списка

bool empty () const; // возвращает истину, если вызывающий список пуст

void clear(); //удаляет все элементы списка

……….

}

Возможны различные реализации списков.

простой односвязный список

простой двухсвязный список

кольцевой двухсвязный список

список

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