Standard Template Library

STL

STL (Standard Template Library, стандартная библиотека шаблонов) - набор согласованных обобщённых алгоритмов, контейнеров, средств доступа к их содержимому и различных вспомогательных функций. Является одной из самых важных составляющих языка C++ . Стандартная библиотека шаблонов до включения в стандарт C++ была сторонней разработкой, в начале — фирмы HP , а затем SGI (Silicon Graphics, Inc.).

Стандарт языка не называет её « STL », так как эта библиотека стала неотъемлемой частью языка, однако многие люди до сих пор используют это название, чтобы отличать её от остальной части стандартной библиотеки (потоки ввода/вывода ( iostream ), подраздел Си и др.).

Библиотека содержит большое количество широко распространённых алгоритмов и структур данных. Например, в ней определены шаблонные классы векторов, списков, очередей и стеков, а так же многочисленные функции для работы с ними.

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

Основу STL составляют пять основных компонентов:

1. Контейнер (container) - хранение набора объектов в памяти.

2. Итератор (iterator) - обеспечение средств доступа к содержи-мому контейнера.

3. Алгоритм (algorithm) - определение вычислительной процедуры.

4. Адаптер (adaptor) - адаптация компонентов для обеспечения различного интерфейса.

5. Функциональный объект (functor) - сокрытие функции в объекте для использования другими компонентами.

В дополнение к ним STL содержит один из наиболее важных классов — string . Этот класс определяет тип данных, позволяющих работать с символьными строками как обычно — с помощью операторов, а не функций.

Взаимодействие этих элементов обеспечивает стандартные решения очень широкого круга задач программирования.

Контейнеры — это объекты, хранящие внутри себя другие объекты.

Контейнеры библиотеки STL можно разделить на четыре категории: последовательные , ассоциативные , контейнеры-адаптеры и псевдоконтейнеры .

Контейнер

Описание

Последовательные контейнеры

Заголовок

vector

C-подобный динамический массив произвольного доступа с автоматическим изменением размера при добавлении/удалении элемента.

list

deque

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

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

Ассоциативные контейнеры

set

Множество, в которое каждый элемент может входить лишь один раз.

multiset

То же что и set, но позволяет хранить повторяющиеся элементы.

map

Хранит пары "ключ"-"значение", в которых каждому ключу соответствует лишь одно значение.

multimap

То же что и map, но каждому ключу может соответствовать несколько значений.

Контейнеры-адаптеры

stack

Стек — контейнер, в котором добавление и удаление элементов осуществляется с одного конца.

queue

priority_queue

Очередь — контейнер, с одного конца которого можно добавлять элементы, а с другого — вынимать.

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

Псевдоконтейнеры

bitset

Служит для хранения битовых масок.

basic_string

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

valarray

Шаблон служит для хранения числовых массивов и оптимизирован для достижения повышенной вычислительной производительности. В некоторой степени похож на vector, но в нём отсутствует большинство стандартных для контейнеров операций.

Фцвфвфцв

Каждый контейнерный класс определяет набор функций, которые можно к нему применять. Например, класс list содержит функции для вставки, удаления и слияния элементов, а класс stack предусматривает функции для выталкивания и заталкивания элементов.

Алгоритмы

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

Итераторы

Итератор — объект, напоминающий указатель. Он позволяет перемещаться по содержимому контейнера так, как указатель перемещается по элементам массива. В STL для доступа к элементам контейнера используется итератор. Каждый контейнер поддерживает «свой» вид итератора, который представляет собой «модернизированный» интеллектуальный указатель, «знающий» как получить доступ к элементам конкретного контейнера. Стандарт C++ определяет пять категорий итераторов, описанных в следующей таблице:

Итератор

Описание

Произвольного доступа

Хранит и извлекает значения. Обеспечивает произвольный доступ к элементам. Эквивалентны обычным указателям: поддерживают арифметику указателей, синтаксис индексации массивов и все формы сравнения.

Прямой (однонаправленный)

Хранит и извлекает значения. Перемещается только вперёд.

Двунаправленный

Хранит и извлекает значения. Перемещается вперёд и назад

Ввода (входной)

Извлекает, но не хранит элементы. Перемещается только вперёд.

Вывода (выходной)

Хранит, но не извлекает значения. Перемещается только вперёд.

Как правило, итераторы, обладающие более широкими возможностями, можно использовать вместо более слабых. Например, вместо итератора ввода можно использовать прямой итератор.

Итераторы действуют как указатели. Их можно увеличивать, уменьшать, разыменовывать. Итераторы, т.е. объекты типа iterator, объявляются в различных контейнерах.

Распределители

Каждый итератор имеет свой распределитель ( allocator ), подобранный специально для него. Распределители управляют выделением памяти для контейнера. По-умолчанию, он является объектом класса allocator . При необходимости можно найти собственный распределитель, ориентированный на специфические приложения.

Предикаты

Некоторые алгоритмы и контейнеры используют специальный тип функций, называемый предикатом. Существуют два вида предикатов: бинарный и унарный . Эти функции возвращают true или false , однако условия, от которых зависят эти значения, можно написать самостоятельно. Аргументами предикатов являются объекты, хранящиеся в контейнере. Существует частный случай предиката, называемый компаратором . Он используется для сравнения двух элементов и возвращает true, если первый аргумент меньше второго.

Функторы

Шаблоны, определённые в заголовке , позволяют создавать объекты, в которых определена операторная функция operator() . Такие объекты называются функторами ( или функциональными объектами ). Их часто применяют вместо указателей на функции. Искользование функторов вместо указателей на функции повышает эффективность кода. Полный список функторов можно узнать из справки по STL .

Одни из самых широко применяемых функторов: редакторы связей ( binders ) и инверторы ( negators ). Редакторы связей связывают аргумент с функтором. Инвертор возвращает отрицание предиката.

Адаптеры

Адаптер - адаптация компонентов для обеспечения различного интерфейса. Проще говоря, адаптер превращает одну сущность в другую. Например, контейнер queue, создающий стандартную очередь, является адаптером по отношению к контейнеру deque.

class vector Type определяет тип данных, хранящихся в контейнере, а класс Allocator определяет механизм распределения памяти. По-умолчанию используется стандартный распределитель. Класс vector содержит следующие конструкторы: explicit vector ( const Allocator & a = Allocator ()); explicit vector ( size_type num , const T & val = T (), const Allocator & a = Allocator ()); vector ( const vector Type , Allocator & ob ); template class InIter vector ( InIter start , InIter end , const Allocator & a = Allocator ()); примечание: explicit запрещает неявное преобразование и указывает на требования явной формы конструктора копий. " width="640"

Векторы

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

Шаблонная спецификация класса vector :

template class Type , class Allocator = allocator Type class vector

Type определяет тип данных, хранящихся в контейнере, а класс Allocator определяет механизм распределения памяти. По-умолчанию используется стандартный распределитель.

Класс vector содержит следующие конструкторы:

explicit vector ( const Allocator & a = Allocator ());

explicit vector ( size_type num , const T & val = T (), const Allocator & a = Allocator ());

vector ( const vector Type , Allocator & ob );

template class InIter vector ( InIter start , InIter end , const Allocator & a = Allocator ());

примечание:

explicit запрещает неявное преобразование и указывает на требования явной формы конструктора копий.

iv ; //создаётся пустой вектор типа int vector char cv ( 5 ); //создаётся вектор типа char, состоящий из //пяти элементов vector char cv2 ( 5 , 'x' ); //инициализируется вектор типа char, //состоящий из пяти элементов со значениями х vector int iv2 ( iv ); //создаётся вектор типа int, который //инициализируется другим целочисленным //вектором В классе vector определены следующие операторы сравнения: ==, , = Для доступа к элементам вектора определён оператор [ ], работающий, как и в простом массиве. " width="640"

Первый конструктор создаёт пустой вектор. Второй — вектор, состоящий из num элементов., имеющих значение val , которое можно задавать по умолчанию. Третий конструктор создаёт вектор, содержащий элементы вектора ob . Четвёртый — вектор, состоящий из элементов, лежащих в диапазоне, определённом на интервале start и end .

Пример объявления векторов:

vector int iv ; //создаётся пустой вектор типа int

vector char cv ( 5 ); //создаётся вектор типа char, состоящий из //пяти элементов

vector char cv2 ( 5 , 'x' ); //инициализируется вектор типа char, //состоящий из пяти элементов со значениями х

vector int iv2 ( iv ); //создаётся вектор типа int, который //инициализируется другим целочисленным //вектором

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

==, , =

Для доступа к элементам вектора определён оператор [ ], работающий, как и в простом массиве.

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

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

Описание

reference back( );

const_reference back( ) const;

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

const_iterator begin() const;

iterator begin();

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

void clear();

Удаляет из вектора все элементы.

bool empty() const;

Возвращает true , если вектор пуст и false в противном случае.

iterator end( );

const_iterator end( ) const;

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

iterator erase(iterator i );

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

iterator erase(iterator start, iterator end);

Удаляет все элементы из диапазона, заданного итераторами start и end . Возвращает итератор на элемент, следующий за последним удалённым

reference front( );

const_reference front( ) const;

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

iterator insert( iterator i, const Type& val );

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

void insert( iterator i, size_type num, const Type& val);

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

v ( 10 ); //создаём вектор из 10 элементов int i ; //выводим на экран размер вектора cout "Size of v = " v . size () '\n' ; //присваиваем элементам вектора значения for ( i = 0 ; i 10 ; i ++) v [ i ] = i + 'a' ; " width="640"

template void insert( iterator i, InputIterator start, InputIterator end );

Вставляет перед элементом, на который ссылается итератор i, последовательность элементов, заданную итераторами start и end

void pop_back();

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

void push_back(const T& val);

Добавляет элемент val в конец вектора

size_type size() const;

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

Рассмотрим пример, иллюстрирующий основные операции над векторами.

#include

#include

#include

#include

using namespace std ;

int _tmain ( int argc , _TCHAR * argv [])

{

vector char v ( 10 ); //создаём вектор из 10 элементов

int i ;

//выводим на экран размер вектора

cout "Size of v = " v . size () '\n' ;

//присваиваем элементам вектора значения

for ( i = 0 ; i 10 ; i ++)

v [ i ] = i + 'a' ;

//выводим на экран содержимое вектора

cout "Current contents:\n" ;

for ( i = 0 ; i 10 ; i ++)

cout v [ i ] ' ' ;

cout "\n\n" ;

cout "Extended vector\n" ;

//добавляем в конец вектора новые элементы,

//размер вектора увеличивается автоматически

for ( i = 0 ; i 10 ; i ++)

v . push_back ( i + 10 + 'a' );

//выводим на экран размер вектора

сout "New size = " v . size () '\n' ;

//выводим на экран содержимое вектора

cout "Current contents:\n" ;

for ( i = 0 ; i v . size (); i ++)

cout v [ i ] ' ' ;

cout "\n\n" ;

//изменяем содержимое вектора

for ( i = 0 ; i v . size (); i ++)

v [ i ]= toupper ( v [ i ]);

cout "Modified contents:\n" ;

for ( i = 0 ; i v . size (); i ++)

cout v [ i ] ' ' ;

_getch ();

return 0 ;

}

Результат выполнения программы:

Size of v = 10

Current contents:

a b c d e f g h i j

Extended vector

New size = 20

Current contents:

a b c d e f g h i j k l m n o p q r s t

Modified contents:

A B C D E F G H I J K L M N O P Q R S T

v ( 10 ); vector char :: iterator p ; //создаём итератор p int i = 0 ; //устанавливаем итератор на начало вектора p = v . begin (); while ( p != v . end ()){ * p = i + 'a' ; p ++; i ++; } " width="640"

На данном примере можно заметить большое преимущество вектора над обычными динамическими массивами — функция size() . С её помощью можно определить размер вектора в любой момент.

Доступ к элементам массива с помощью итератора

Как известно, доступ к элементам массива осуществляется через указатель, либо по индексу. В STL роль массивов играют векторы , а роль указателей — итераторы . Доступ к элементам вектора осуществляется по индексу или через итератор.

#include

#include

#include

#include

using namespace std ;

int _tmain ( int argc , _TCHAR * argv [])

{

vector char v ( 10 );

vector char :: iterator p ; //создаём итератор p

int i = 0 ;

//устанавливаем итератор на начало вектора

p = v . begin ();

while ( p != v . end ()){

* p = i + 'a' ;

p ++;

i ++;

}

cout "Starting contents\n" ;

p = v . begin ();

while ( p != v . end ()){

cout * p ' ' ;

p ++;

}

cout "\n\n" ;

p = v . begin ();

while ( p != v . end ()){

* p = toupper (* p );

p ++;

}

cout "Modified contents\n" ;

p = v . begin ();

while ( p != v . end ()){

cout * p ' ' ;

p ++;

}

_getch ();

return 0 ;

}

Очень важный момент в этом примере — объявление итератора. Так как тип iterator объявлен внутри каждого контейнерного класса, то итератор нужно создавать, указывая имя контейнера и спецификатор iterator . В данной программе для доступа к элементам используется итератор. Для этого p устанавливается на begin() , после чего вектор "проходится", пока итератор не будет равен v.end() .

v(10); vector char v2; char str[]= "" ; int i; for (i=0; i v[i] = i + 'a' ; for (i=0; str[i]; i++) v2.push_back(str[i]); cout "Starting contents of v:\n" ; for (i=0; i cout ' ' ; cout "\n\n" ; " width="640"

Вставка и удаление элементов вектора

Для вставки элемента в произвольное место вектора используется функция insert(). Для удаления любого элемента — erase().

#include

#include

#include

using namespace std;

int _tmain( int argc, _TCHAR* argv[])

{

vector char v(10);

vector char v2;

char str[]= "" ;

int i;

for (i=0; i

v[i] = i + 'a' ;

for (i=0; str[i]; i++)

v2.push_back(str[i]);

cout "Starting contents of v:\n" ;

for (i=0; i

cout ' ' ;

cout "\n\n" ;

::iterator p = v.begin(); p+=2; v.insert(p, 10, 'X' ); cout "Size of v = " '\n' ; cout "Contents after insert:\n" ; for (i=0; i cout ' ' ; cout "\n\n" ; p=v.begin(); p+=2; v.erase(p, p+10); cout "Size of v = " '\n' ; cout "Contents after erase:\n" ; for (i=0; i cout ' ' ; cout "\n\n" ; p=v.begin()+2; v.insert(p, v2.begin(), v2.end()); cout "Size of v = " '\n' ; cout "Contents after insert:\n" ; for (i=0; i cout ' ' ; _getch(); return 0; } Результат выполнения программы Starting contents of v: a b c d e f g h i j Size of v = 20 Contents after insert: a b X X X X X X X X X X c d e f g h i j Size of v = 10 Contents after erase: a b c d e f g h i j Size of v = 18 Contents after insert: a b c d e f g h i j " width="640"

vector char ::iterator p = v.begin();

p+=2;

v.insert(p, 10, 'X' );

cout "Size of v = " '\n' ;

cout "Contents after insert:\n" ;

for (i=0; i

cout ' ' ;

cout "\n\n" ;

p=v.begin();

p+=2;

v.erase(p, p+10);

cout "Size of v = " '\n' ;

cout "Contents after erase:\n" ;

for (i=0; i

cout ' ' ;

cout "\n\n" ;

p=v.begin()+2;

v.insert(p, v2.begin(), v2.end());

cout "Size of v = " '\n' ;

cout "Contents after insert:\n" ;

for (i=0; i

cout ' ' ;

_getch();

return 0;

}

Результат выполнения программы

Starting contents of v:

a b c d e f g h i j

Size of v = 20

Contents after insert:

a b X X X X X X X X X X c d e f g h i j

Size of v = 10

Contents after erase:

a b c d e f g h i j

Size of v = 18

Contents after insert:

a b c d e f g h i j

=) и присваивания. Поэтому важно не забывать переопределять данные операторы в классе , который будет использоваться в качестве элемента вектора. " width="640"

Вектор, содержащий объекты класса

Так как вектор является шаблонным классом, из этого следует, что его элементами могут быть не только экземпляры стандартных типов ( int , double , и т.п.), но и пользовательские классы. При использовании пользовательских объектов в качестве элементов вектора необходимо помнить, что вектор содержит встроенные операторы сравнения (==, , =) и присваивания. Поэтому важно не забывать переопределять данные операторы в классе , который будет использоваться в качестве элемента вектора.

class list ; Шаблонный параметр Type задаёт тип данных, хранящихся в списке. Распределитель памяти задаётся классом Allocator , причём по-умолчанию используется стандартный распределитель памяти. Класс list имеет следующий конструкторы: explicit list ( const Allocator & a = Allocator ()); explicit list ( size_type num , const Type & val = Type (), const Allocator & a = Allocator ()); list ( const list Type , Allocator & ob ); template class InIter list ( InIter start , InIter end , const Allocator & a = Allocator ()); Первый конструктор создаёт пустой список. Второй — список, состоящий из num элементов., имеющих значение val , которое можно задавать по-умолчанию. " width="640"

Списки

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

Шаблонная спецификация класса list имеет следующий вид

template class Type , class Allocator = allocator Type class list ;

Шаблонный параметр Type задаёт тип данных, хранящихся в списке. Распределитель памяти задаётся классом Allocator , причём по-умолчанию используется стандартный распределитель памяти.

Класс list имеет следующий конструкторы:

explicit list ( const Allocator & a = Allocator ());

explicit list ( size_type num , const Type & val = Type (), const Allocator & a = Allocator ());

list ( const list Type , Allocator & ob );

template class InIter list ( InIter start , InIter end , const Allocator & a = Allocator ());

Первый конструктор создаёт пустой список. Второй — список, состоящий из num элементов., имеющих значение val , которое можно задавать по-умолчанию.

= В классе list определены функции-члены для работы с элементами класса. Так как данный класс содержит в себе все функции, что и vector (кроме оператора [ ] - его список не поддерживает), внизу приведена таблица функций-членов, специфичных только для списка (т.е. для работы со списком необходимо знать принципы работы с вектором). Функция-член void merge(listtemplate void merge(listОписание void pop_front(); Внедряет упорядоченный список, содержащийся в объекте ob , в заданный список. В результате возникает упорядоченный список. После внедрения список, содержащийся в ob , становится пустым. Вторая функция merge получает в качестве параметра функцию, позволяющую сравнивать элементы списка между собой Удаляет первый элемент списка void push_front(); Добавляет элемент val в начало списка " width="640"

Третий конструктор создаёт список, содержащий элементы объекта ob . Четвёртый — формирует список, состоящий из элементов, лежащих в диапазоне, заданном итераторами start и end .

Как видно из конструкторов — они имеют такой же вид, как и конструкторы векторов. Такая унификация — одна из особенностей STL , благодаря которой, программист может не задумываться об особенностях конструктора определённого контейнера.

Как и в векторе, в list определены следующие операторы сравнения:

==, , =

В классе list определены функции-члены для работы с элементами класса. Так как данный класс содержит в себе все функции, что и vector (кроме оператора [ ] - его список не поддерживает), внизу приведена таблица функций-членов, специфичных только для списка (т.е. для работы со списком необходимо знать принципы работы с вектором).

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

void merge(list

template

void merge(list

Описание

void pop_front();

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

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

void push_front();

Добавляет элемент val в начало списка

void remove (const T &val);

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

void reverse();

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

void sort();

template

void sort(Comp cmpfn);

Упорядочивает список. Вторая версия упорядочивает список, используя для сравнения элементов функцию cmpfn

void splice(iterator i, list &ob);

Вставляет в позицию, указанную итератором i , содержимое вектора ob . После выполнения операции список ob становится пустым

void splice(iterator i, list &ob, iterator el);

Элемент, на который ссылается итератор el , удаляется из списка ob и вставляется в вызывающий список в позицию, заданную итератором i

void splice(iterator i, list &ob, iterator start, iterator end);

Элементы списка ob , расположенные в диапазоне, заданном итераторами start и end , удаляются из списка ob и вставляются в вызывающий список в позицию, заданную итератором i

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

Рассмотрим пример, демонстрирующий основы работы с классом list :

lst ; // Создаём пустой список int i ; for ( i = 0 ; i 10 ; i ++) lst . push_back ( i ); cout "Size of list = " lst . size () '\n' ; cout "Contents: " ; list int :: iterator p = lst . begin (); while ( p != lst . end ()){ cout * p ' ' ; p ++; } cout "\n\n" ; //Изменяем содержимое списка p = lst . begin (); while ( p != lst . end ()){ * p =* p + 100 ; p ++; } cout "Modified contents: " ; p = lst . begin (); while ( p != lst . end ()){ cout * p ' ' ; p ++; } _getch (); return 0 ; } Результат выполнения программы Size of list = 10 Contents: 0 1 2 3 4 5 6 7 8 9 Modified contents: 100 101 102 103 104 105 106 107 108 109 " width="640"

#include

#include

#include

using namespace std ;

int _tmain ( int argc , _TCHAR * argv [])

{

list int lst ; // Создаём пустой список

int i ;

for ( i = 0 ; i 10 ; i ++)

lst . push_back ( i );

cout "Size of list = " lst . size () '\n' ;

cout "Contents: " ;

list int :: iterator p = lst . begin ();

while ( p != lst . end ()){

cout * p ' ' ;

p ++;

}

cout "\n\n" ;

//Изменяем содержимое списка

p = lst . begin ();

while ( p != lst . end ()){

* p =* p + 100 ;

p ++;

}

cout "Modified contents: " ;

p = lst . begin ();

while ( p != lst . end ()){

cout * p ' ' ;

p ++;

}

_getch ();

return 0 ;

}

Результат выполнения программы

Size of list = 10

Contents: 0 1 2 3 4 5 6 7 8 9

Modified contents: 100 101 102 103 104 105 106 107 108 109

Эта программа создаёт список целых чисел. Сначала формируется пустой список, после чего в него с помощью push_back() записываются 10 целых чисел, причём каждое записывается в конец существующего списка. После этого на экран выводится размер и содержимое этого списка. Затем каждое число увеличивается на 100 и снова выводятся на экран.

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

Функция end()

Во всех предыдущих примерах можно обратить внимание, что для "обхода" контейнера используется цикл с предусловием, а в качестве условия — неравенство итератора концу контейнера. Важное свойство функции end() - она возвращает указатель не на последний элемент контейнера, а на следующий за ним элемент. Таким образом, последнему элементу соответствует значение end() - 1 . Это позволяет создавать очень эффективные алгоритмы обхода всех элементов контейнера, включая последний элемент. Если значение итератора становится равным значению end() , значит, все элементы контейнера пройдены. Эту особенность следует помнить всегда, чтобы избежать ошибок в использовании данной функции.

lst ; // Создаём пустой список int i ; for ( i = 0 ; i 10 ; i ++) lst . push_back ( i ); cout "Size of list = " lst . size () '\n' ; cout "Contents: " ; list int :: iterator p = lst . begin (); while ( p != lst . end ()){ cout * p ' ' ; p ++; } cout "\n\n" ; cout "Reversed contents: " ; p = lst . end (); while ( p != lst . begin ()){ p --; //обратите внимание на то, где стоит уменьшение итератора cout * p ' ' ; } _getch (); return 0 ; } Результат работы программы Size of list = 10 Contents: 0 1 2 3 4 5 6 7 8 9 Reversed contents: 9 8 7 6 5 4 3 2 1 0 " width="640"

#include

#include

#include

using namespace std ;

int _tmain ( int argc , _TCHAR * argv [])

{

list int lst ; // Создаём пустой список

int i ;

for ( i = 0 ; i 10 ; i ++)

lst . push_back ( i );

cout "Size of list = " lst . size () '\n' ;

cout "Contents: " ;

list int :: iterator p = lst . begin ();

while ( p != lst . end ()){

cout * p ' ' ;

p ++;

}

cout "\n\n" ;

cout "Reversed contents: " ;

p = lst . end ();

while ( p != lst . begin ()){

p --; //обратите внимание на то, где стоит уменьшение итератора

cout * p ' ' ;

}

_getch ();

return 0 ;

}

Результат работы программы

Size of list = 10

Contents: 0 1 2 3 4 5 6 7 8 9

Reversed contents: 9 8 7 6 5 4 3 2 1 0

lst1 , lst2 ; int i ; for ( i = 0 ; i 10 ; i ++) lst1 . push_back ( i ); for ( i = 0 ; i 10 ; i ++) lst2 . push_front ( i ); " width="640"

Особое внимание следует обратить на кусок кода, выводящий содержимое списка в обратном порядке. Сначала итератор p устанавливается на конец списка с помощью end() . Но поскольку эта функция возвращает итератор, установленный на объект, расположенный за последним элементом, но сначала p следует уменьшить на единицу. Никогда не следует забывать об этой особенности функции.

Сравнение функций push_front() и push_back()

Список можно создавать, добавляя элементы либо в его конец, либо в начало. Для добавления элементов в начало списка используется функция push_front() . В конец списка элементы добавляются с помощью push_back() .

#include

#include

#include

using namespace std ;

int _tmain ( int argc , _TCHAR * argv [])

{

list int lst1 , lst2 ;

int i ;

for ( i = 0 ; i 10 ; i ++)

lst1 . push_back ( i );

for ( i = 0 ; i 10 ; i ++)

lst2 . push_front ( i );

:: iterator p ; cout "Contents of lst1:\n" ; p = lst1 . begin (); while ( p != lst1 . end ()){ cout * p ' ' ; p ++; } cout "\n\n" ; cout "Contents of lst2:\n" ; p = lst2 . begin (); while ( p != lst2 . end ()){ cout * p ' ' ; p ++; } _getch (); return 0 ; } Поскольку при создании списка lst2 элементы добавлялись в начало, порядок их следования противоположен порядку следования элементов в списке lst1 , при создании которого они добавлялись в конец. Сортировка списка Список можно упорядочить, вызвав функцию sort() . По-умолчанию, она сортирует список в порядке возрастания. Пример вызова функции: lst.sort(); Результат работы программы Contents of lst1: 0 1 2 3 4 5 6 7 8 9 Contents of lst2: 9 8 7 6 5 4 3 2 1 0 " width="640"

list int :: iterator p ;

cout "Contents of lst1:\n" ;

p = lst1 . begin ();

while ( p != lst1 . end ()){

cout * p ' ' ;

p ++;

}

cout "\n\n" ;

cout "Contents of lst2:\n" ;

p = lst2 . begin ();

while ( p != lst2 . end ()){

cout * p ' ' ;

p ++;

}

_getch ();

return 0 ;

}

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

Сортировка списка

Список можно упорядочить, вызвав функцию sort() . По-умолчанию, она сортирует список в порядке возрастания.

Пример вызова функции:

lst.sort();

Результат работы программы

Contents of lst1:

0 1 2 3 4 5 6 7 8 9

Contents of lst2:

9 8 7 6 5 4 3 2 1 0

lst1 , lst2 ; int i ; for ( i = 0 ; i 10 ; i += 2 ) lst1 . push_back ( i ); for ( i = 1 ; i 11 ; i += 2 ) lst2 . push_back ( i ); list int :: iterator p ; lst1 . merge ( lst2 ); if ( lst2 . empty ()) cout "lst2 is empty\n" ; " width="640"

Вставка одного списка в другой

Упорядоченный список можно вставить в другой список. Результатом этой операции является упорядоченный список , состоящий из элементов исходных списков. Новый список хранится в вызывающем объекте, а второй список становится пустым . Эта операция иллюстрируется приведённым ниже примером. Первый список состоит их чётных чисел от 0 до 9. Второй — из нечётных . После их слияния образуется последовательность вида: 0 1 2 3 4 5 6 7 8 9.

#include

#include

#include

using namespace std ;

int _tmain ( int argc , _TCHAR * argv [])

{

list int lst1 , lst2 ;

int i ;

for ( i = 0 ; i 10 ; i += 2 )

lst1 . push_back ( i );

for ( i = 1 ; i 11 ; i += 2 )

lst2 . push_back ( i );

list int :: iterator p ;

lst1 . merge ( lst2 );

if ( lst2 . empty ())

cout "lst2 is empty\n" ;

, всегда их переопределять. Проблема состоит не только в доступе к информационным полям объектов, но и в особенностях класса list , который использует эти операторы для реализации функций-членов класса. Например, сортировка списка, внедрение, поиск и т.д. Результат работы программы: lst2 is empty Contents of lst1 after merge: 0 1 2 3 4 5 6 7 8 9 " width="640"

cout "Contents of lst1 after merge:\n" ;

p = lst1 . begin ();

while ( p != lst1 . end ()){

cout * p ' ' ;

p ++;

}

_getch ();

return 0 ;

}

Список, содержащий объекты класса

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

Результат работы программы:

lst2 is empty

Contents of lst1 after merge:

0 1 2 3 4 5 6 7 8 9

(myclass &ob1, myclass &ob2){ return ob1.getsum() ob2.getsum(); } friend bool operator ==(myclass &ob1, myclass &ob2){ return ob1.getsum() == ob2.getsum(); } friend bool operator !=(myclass &ob1, myclass &ob2){ return ob1.getsum() != ob2.getsum(); } }; " width="640"

#include

#include

#include

using namespace std;

class myclass{

int a, b;

public :

myclass( int i=0, int j=0){

a=i;

b=j;

}

int getsum(){

return a+b;

}

friend bool operator

return ob1.getsum()

}

friend bool operator (myclass &ob1, myclass &ob2){

return ob1.getsum() ob2.getsum();

}

friend bool operator ==(myclass &ob1, myclass &ob2){

return ob1.getsum() == ob2.getsum();

}

friend bool operator !=(myclass &ob1, myclass &ob2){

return ob1.getsum() != ob2.getsum();

}

};

int _tmain( int argc, _TCHAR* argv[])

{

list lst1; //Создаём первый список

int i;

for (i=0; i

lst1.push_back(myclass(i, i));

cout "First list: " ;

list::iterator p = lst1.begin();

while (p!=lst1.end()){

cout getsum() ' ' ;

p++;

}

list lst2; //Создаём второй список

for (i=0; i

lst2.push_back(myclass(i*2, i*3));

cout "\nSecond list: " ;

p = lst2.begin();

while (p!=lst2.end()){

cout getsum() ' ' ;

p++;

}

lst1.merge(lst2); //Выполняем слияние

cout "\nMerged list: " ;

p = lst1.begin();

while (p!=lst1.end()){

cout getsum() ' ' ;

p++;

}

_getch();

return 0;

}

, class Allocator = allocator pair const Key , Type class map Класс Key определяет тип ключа, шаблонный параметр Type задаёт тип данных, хранящихся в ассоциативном массиве, а функтор Comp позволяет сравнивать два ключа. По-умолчанию в качестве функции Comp применяется стандартный функтор less() . Распределитель задаётся классом Allocator . " width="640"

Ассоциативные контейнеры

Класс map создаёт ассоциативный контейнер, в котором каждому ключу соответствует единственное значение. Сам ключ представляет собой имя, с помощью которого можно получить требуемое значение. Если в контейнере хранится некоторое значение, доступ к нему возможен только через ключ. Таким образом, ассоциативный контейнер хранит пары "ключ-значение" . Преимущество таких контейнеров — в доступе к значениям по ключам. К примеру, по имени или фамилии человека ( ключ ) можно узнать его номер телефона ( значение ).

Как указывалось ранее, map может содержать только уникальные ключи, дубликаты не допускаются. Если необходимо создать ассоциативный контейнер, который может хранить дубликаты, применяется класс multimap или multiset .

Шаблонная спецификация класса map имеет следующий вид:

template class Key , class Type , class Comp = less Key , class Allocator = allocator pair const Key , Type class map

Класс Key определяет тип ключа, шаблонный параметр Type задаёт тип данных, хранящихся в ассоциативном массиве, а функтор Comp позволяет сравнивать два ключа. По-умолчанию в качестве функции Comp применяется стандартный функтор less() . Распределитель задаётся классом Allocator .

& ob ); template class InIter map ( InIter start , InIter end , const Comp & cmpfn = Comp (), const Allocator & a = Allocator ()); Первый конструктор создаёт пустой ассоциативный массив. Второй — контейнер, содержащий элементы объекта ob . Третий — создаёт массив, состоящий из элементов, лежащих в диапазоне, заданном итераторами start и end . Функция cmpfn определяет порядок следования элементов массива. Как правило, любой объект, использующийся в качестве ключа, должен определять конструктор по-умолчанию, а так же операторы сравнения. Для каждого компилятора имеются свои требования к ключам. В классе map определены следующие операторы сравнения: ==, , = Функции-члены, определённые в этом классе перечислены в таблице ниже. Класс key_type представляет собой тип ключа, а класс value_type определяет тип pair " width="640"

Класс map имеет следующие конструкторы

explicit map ( const Comp & cmpfn = Comp (), const Allocator & a = Allocator ());

map ( const map Key , Type , Comp , Allocator & ob );

template class InIter map ( InIter start , InIter end , const Comp & cmpfn = Comp (), const Allocator & a = Allocator ());

Первый конструктор создаёт пустой ассоциативный массив. Второй — контейнер, содержащий элементы объекта ob . Третий — создаёт массив, состоящий из элементов, лежащих в диапазоне, заданном итераторами start и end . Функция cmpfn определяет порядок следования элементов массива.

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

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

==, , =

Функции-члены, определённые в этом классе перечислены в таблице ниже. Класс key_type представляет собой тип ключа, а класс value_type определяет тип pair

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

Описание

iterator begin();

const_iterator begin() const;

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

void clear();

Удаляет из ассоциативного массива все элементы

size_type count (

const key_type &k) const;

Возвращает текущее количество дубликатов элемента со значением k в контейнере

bool empty() const;

Возвращает true , если контейнер пуст, и false в обратном случае

iterator end();

const_iterator end() const;

iterator erase(iterator i);

Возвращает итератор, установленный на последний элемент ассоциативного массива

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

iterator erase (iterator start, iterator end);

Удаляет все элементы из диапазона, заданного итераторами start и end . Возвращает итератор, установленный на элемент, следующий за последним удалённым

size_type erase (const key_type &k);

Удаляет из контейнера элементы, имеющие значение k

iterator find(const key_type &k);

const_iterator find ( const key_type &k);

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

iterator insert(iterator i, const value_type &val);

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

template

void insert(InIter start, InIter end);

Вставляет элементы из диапазона, заданного итераторами start и end

Daw

struct pair { typedef Ktype first_type ; typedef Vtype second_type ; Ktype first ; Vtype second ; //Конструкторы pair (); pair ( const Ktype & k , const Vtype & v ); template class A , class B pair ( const A , B & ob ); } Значение, хранящееся в поле first, содержит ключ, а поле second хранит значение, соответствующее этому ключу. Пару можно создать, вызвав либо конструкторы типа pair, либо функцию make_pair(), создающую объекты класса pair на основе информации о типе параметров. " width="640"

pair

insert(const value_type &val);

Вставляет элемент со значением val в вызывающий ассоциативный контейнер. Возвращает итератор, ссылающийся на вставленный элемент. Элемент вставляется, только если его не было в ассоциативном массиве. В случае успеха возвращается объект класса pair , иначе — pair

mapped_type& operator[ ] ( const key_type &i);

Возвращает ссылку на элемент, заданный итератором i . Если элемента в массиве не было, он вставляется туда.

size_type size() const;

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

Пары "ключ-значение" хранятся в ассоциативном массиве как объекты типа pair. Его шаблонная спецификация имеет следующий вид:

template class Ktype , class Vtype struct pair {

typedef Ktype first_type ;

typedef Vtype second_type ;

Ktype first ;

Vtype second ;

//Конструкторы

pair ();

pair ( const Ktype & k , const Vtype & v );

template class A , class B

pair ( const A , B & ob );

}

Значение, хранящееся в поле first, содержит ключ, а поле second хранит значение, соответствующее этому ключу.

Пару можно создать, вызвав либо конструкторы типа pair, либо функцию make_pair(), создающую объекты класса pair на основе информации о типе параметров.

Прототип: