СП - Краткие ответы на экзаменационные вопросы (1115082), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Priority_queue <T> – очередь с приоритетом.

Set <T> – множество с уникальными элементами.

Bitset <N> – множество битов.

Multiset <T> – множество не обязательно с уникальными элементами.

Map <key, val> – ассоциативный список, в котором хранятся пары ключ/значение, с каждым ключом связано одно значение.

Multimap <key, val> – ассоциативный список, в котором хранятся пары ключ/значение, с каждым ключом связано не обязательно одно значение.

Основные типы:

Следующие типы определены в public-части для каждого контейнера:

value_type

allocator_type - распределитель памяти

size_type

iterator, const_iterator

reverse_iterator, const_reverse_iterator

pointer, const_pointer - указатель на элементы

reference, const_reference - ссылка на элементы

Распределитель памяти.

У каждого контейнера есть свой распределитель памяти allocator, который управляет процессом выделения памяти для объектов контейнера. По умолчанию распределитель памяти – это объект класса allocator. Также можно написать свой распределитель памяти и использовать его в программах, если STL не используем.

Рассматриваем только интерфейс функций:

template <class T> class allocator {

………………………………………

public:

typedef T*pointer;

typedef T&reference;

………………………………………

allocator( ) throw( );//- конструктор по умолчанию

………………………………………

pointer allocate (size_type n);

}

По умолчанию берётся стандартный распределитель памяти, он берёт память из области динамической памяти.

Алгоритмы.

<algorithm>

В STL имеется 60 алгоритмов. Алгоритмы реализуют некоторые распространённые операции с контейнерами, которые не включены в контейнер. Т.е алгоритм – шаблонная функция, поэтому их можно использовать с контейнерами любых типов.

Алгоритмы подразделяются на 3 группы:

• немодифицирующие алгоритмы – действия сводятся к просмотру контейнера или выделению из него какой-либо функции:

find ( ); - поиск элемента, выдаёт место, на котором находится элемент.

count ( ); - подсчёт

for_each( );

• модифицирующие:

transform ( );

reverse ( );

copy ( ); - копируется содержимое одного контейнера в другой

• сортировки:

sort ( ); - простая сортировка

stable_sort( ); - сортировка, гарантирующая сохранение относительно порядка элементов

merge( ); - слияние двух списков.

Итераторы.

Итераторы – это что-то вроде указателей на элементы контейнера.

Типы итераторов перечислены в контейнере. В public-части контейнера есть итераторные функции с одинаковыми именами.

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

Итераторный класс определяется внутри контейнера.

Следует обратить внимание, что при использовании нужно писать оператор расширения видимости, чтобы знать, к какому итератору относится написанное:

list <int> :: iterator

Для итераторов нет константы NULL, обозначающей пустой указатель.

reverse_iterator - обратный итератор, выдаёт последовательность в обратном порядке.

Различие между этими итераторами:

b egin A B C .

end

r begin C B A .

rend

Типы итераторов:

Существуют следующие типы итераторов, которые позволяют соответствующие функции:

1. Итераторы вывода.

*p_ , p++

1. Итераторы ввода.

*=p, ->, ++, ==, !=

1. Однонаправленные.

*p=, =*p, ->, ++, ==, !=

- положить в контейнер

- взять из контейнера

1. Двунаправленные.

*p=, =*p, -> , ++, ==, !=, --

1. C произвольным доступом.

*p=, =*p, -> , ++, ==, !=, --, [ ], +, -, +=, -=, <, >, <=, >=

С 1 до 5 увеличивается мощность итераторов.

1. Стандартная библиотека шаблонов STL: шаблонные классы vector и list.

Пример. Контейнер vector. (схематично)

template <class T, class A = allocator <T>> class vector {

- параметр распределения памяти, по умолчанию берётся

стандартный распределитель памяти

……………………………………………..

public:

//типы

//итераторные функции

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

/*const*/reference operator [ ] (size_type n); //доступ без контроля выхода за

диапазон вектора

/*const*/reference at (size_type n); //с контролем

/*const*/reference front ( ); //указатель на первый элемент контейнера

/*const*/reference back ( ); // указатель на последний элемент контейнера

explicit vector (const A& = A( ));

// - здесь опускается имя формального параметра, работает

конструктор по умолчанию

// explicit vector - вектор нулевой длины (когда данные записываются в вектор,

// сначала создаётся такой вектор)

explicit vector (site_type n; const T& value = T( ); const A& = A( ));

…

iterator erase (iterator i);

iterator insert (iterator i, const T& value = T( )); // - вставка перед этим элементом, возвращает итератор вставленного элемента

void push_back ( );

void pop_back ( ); // - удаляем последнюю запись вставленного элемента

sizetype size ( ) const;

bool empty ( ) const;

void clear ( ); // - очищаем вектор

………………………….

}

Пример. Контейнер – список.

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

public:

//типы

//итераторные функции

/*const*/reference front ( ); //указатель на первый элемент контейнера

/*const*/reference back ( ); // указатель на последний элемент контейнера

explicit list (const A& = A( ));

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

//explicit – для безопасности, не позволяет делать присваивание векторов.

…………………………

iterator erase (iterator i);

iterator insert (iterator i, const T& value = T( )); // - вставка перед этим элементом

void push_back ( );

void pop_back ( ); // - удаляем последнюю запись вставленного элемента

sizetype size ( ) const;

bool empty ( ) const;

void clear ( ); // - очищаем вектор

…………………………. }

Пример. Написать функцию, формирующую вектор.

#include <iostream>

#include <vector>

#include <list>

using name_space std;

void g (vector <int> &v, list <int> lst) {

// - ставить здесь ссылку является хорошим стилем

int i;

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

// функция size для вектора v

if (!(v[i]%2)) lst.push_back (v[i]);

lst <int> :: const_iterator p=lst.begin( );

// - показываем на первый элемент

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

cout << *p << endl;

p++;

}

}

int main ( ) {

vector <int> v (20);

list <int> lst; //- первый конструктор без параметров, создающий список 0 длины

int i;

for (i=0; i<20; i++) v[i]=i;

g (v,lst); return 0; }

Характеристики

Список файлов ответов (шпаргалок)