Шаблоны

Шаблоны позволяют параметризовать не только значения, но и типы, позволяют применять классы к разным типам объектов.

С помощью шаблонов можно написать код, который не будет зависеть не только от задаваемых значений, но и от типов этих значений!

Например, вместо создания отдельных классов-стеков для хранения int-значений, объектов типа char и double, можно написать одно определение стекового класса, которое будет использоваться для любого из этих типов.

По историческим причинам для задания параметров-типов шаблона вместо ключевого слова typename можно использовать ключевое слово class. В результате во многих книгах и программах используется такой синтаксис: template <class Т>.

Спецификатор template действует всю последующую инструкцию.

Пример:

template <typename T>

class matrix{

T** _array;

int _width;

int _height;

public:

matrix(int width; int height);

operator+(matrix<T>);

matrix(const matrix<T>&);

};

Шаблонных параметров может быть несколько: template <typename T, typename U>

В качестве шаблонных параметров может быть задан размер матрицы

Тогда matrix<int, 4, 5> и matrix<int, 6, 7> - объекты разных классов.

!константные параметры должны быть в конце описания.

Для каждого параметра шаблона выполняется своя компиляция. То есть, при объявлении в коде программы объектов классов A<int> и A<char>, компилятор создаст 2 совершенно разных класса – один для типа int, а второй для типа char

Например, конструктор копирования может принимать в себя также шаблонный параметр:

template <typename T>

class matrix{

…

public:

template <typename U>

matrix(const matrix<U>&);

};

В описании конструктора будем выполнять приведение типа U к T.

1. Stl: итераторы

Что такое итераторы?

Итератор – обобщенная абстракия, используемая для доступа к элементам контейнера.

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

Какие бывают итераторы?

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

Чем принципиально отличаются итератор по элементам контейнера set и по элементам контейнера vector?

vector – итераторы произвольного доступа

(обеспечивает произвольный доступ к элементам вектора)

set – двунаправленный итератор

(разрешен только последовательный обход контейнера)

Какие функции и операторы должны быть определены для итератора по элементам двухсвязного списка?

Контейнеры также поддерживают метод begin(), который возвращает итератор, ссылающийся на первый элемент контейнера.

Метод end() возвращает ссылку на значение, расположенное "за последней чертой" данной последовательности элементов контейнера. Другими словами, метод end() возвращает итератор, который равен результату применения оператора operator++ к итератору, ссылающемуся на последний элемент в данной последовательности.

Вместе методы begin () и end () образуют полуоткрытый диапазон, который включает первый элемент последовательности, но не последний. Причина такого нюанса — в поддержке пустых диапазонов (т.е. контейнеров, не содержащих элементов), для которых результат вызова метода begin() совпадал бы с результатом вызова метода end().

Итак:

• Operator++

• Operator--

• Operator*

• Operator==

• Operator=

Итератор с произвольным доступом

Читают и пишут значения с произвольным доступом. Самые мощные итераторы, сочетающие функциональность двунаправленных итераторов и возможность выполнения арифметики указателей и сравнений указателей.

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

Vector

vector<T> - последовательный контейнер, предназначен, как и массив, для хранения объектов. К элементам вектора тоже можно обращаться с помощью оператора индексирования [ ]. Но в отличие от массива, который имеет фиксированный размер, размер вектора можно изменять в процессе добавления или удаления элементов.

Вектор всегда расширяется в 2 раза.

Устройство

Все элементы вектора должны принадлежать одному типу. Например, нельзя совместно хранить данные типов char и int в одном экземпляре вектора. Класс vector обладает стандартным набором методов для доступа к элементам, добавления и удаления элементов, а также получения количества хранимых элементов. Вектор хранится в памяти непрерывным блоком.

Основные операции и их стоимость

• swap(vector& v) - O(1)

• back() и front() возвращают ссылку на первый и последний элементы - O(1)

• begin() и end() возвращают итератор указывающий на первую и следующую после последнего элемента вектора позицию - O(1)

• empty() проверяет, пустой ли вектор - O(1)

• erase(iterator it) удаляет из вектора элемент на который указывает итератор it и возвращает, итератор указывающий на следующий элемент после удаленного - O(n)

• erase(iterator first, iterator last) удаляет из вектора последовательность определяемую итераторами (first,last) и возвращает итератор, указывающий на следующий элемент после последнего удаленного - O(n)

• clear() то же самое что и erase(begin() , end()) - O(n)

• pop_back() удаляет один элемент с конца вектора - O(1)

• push_back(value) вставляет в конец вектор элемент с значением value - O(1)

• insert(iterator it, value) вставляет элемент со значением value перед элементом, на который указывает итератор it и увеличивает размер вектора на 1 - O(n)

• insert(iterator it, n, value) вставляет n элементов со значением value перед элементом, на который указывает итератор it и увеличивает размер вектора на n O(n) – вставка в произвольное место; O(1) – в конец без перераспределен памяти.

• insert(iterator it, const_iterator first, const_iterator last) вставляет последовательность определяемую итераторами (first,last) перед элементом на который указывает итератор it - O(n)

• operator[] - O(1)

• size() возвращает число элементов вектора - O(1)

• resize(n, value=0) - если при изменении размера число элементов увеличивается то новым элементам присваивается значение value - O(n)

• capacity() возвращает значение показывающее сколько ещё свободных элементов в векторе - O(1)

• reserve(n) резервирует память необходимую для добавления n элементов - O(n)

• max_size() максимальное число элементов которое можно хранить - O(1)

Особенности использования vector

Используется как замена массиву.

Но вектор может изменять размер самостоятельно. Также нет необходимости ручного освобождения памяти.

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

List

Устройство

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

Каждый элемент списка хранит информацию о том, где найти следующий или предыдущий элемент (обычно с помощью указателей).

Итераторы, используемые для работы со списками, относятся к категории двунаправленных, а не произвольного доступа, как итераторы, работающие с векторами. Это означает, что list-итераторы нельзя подвергать сложению и вычитанию, а также другим операциям, характерным для арифметики указателей.

Подобно декам, но в отличие от векторов, списки не открывают базовую модель управления памятью. Другими словами, списки поддерживают методы size() и empty(), но не reserve() или capacity().

Основные операции и их стоимость

• begin() end() - O(1)

• empty() - O(1)

• size() - O(1)

• max_size() - O(1)

• resize (n , value=0) - O(n)

• front() back() - O(1)

• push_front() pop_front() - O(1)

• push_back() pop_back() - O(1)

• insert() - O(1) для вставки в начало или конец. O(n) – вставка в произв участок списка

• erase() - O(n)

• swap() - O(1)

• clear() - O(n)

• reverse() - O(n)

• remove() – удаляет элемент с определенным значением - O(n)

• unique() – удаляет повторения

• merge() – совмещает отсортированные списки - O(n+m)

• sort() – сортирует элементы

Особенности использования

Быстрая вставка и удаление, медленный доступ к n-му эл-ту и поиск.

При вставке или удалении элементов итераторы не теряют своей актуальности.

Например, при реализации интерактивной переписки необходимо где-то хранить имена всех текущих участников "разговора" – подойдет список. Состав участников переписки часто меняется, поэтому нужно быстро вставку и удаление. С другой стороны, поиск участников разговора требуется проводить не очень часто, поэтому время его выполнения не слишком важно в данном случае.

Deque

(double end queue)

deque<T> - последовательный контейнер, похож на vector, но с возможностью быстрой вставки и удаления элементов на обоих концах за о(1). Реализован в виде двусвязанного списка линейных массивов. С другой стороны, в отличие от vector, дек не гарантирует расположение всех своих элементов в непрерывном участке памяти, что делает невозможным безопасное использование арифметики указателей для доступа к элементам контейнера.

Устройство

Устройство: блоки, каждый из которых хранит несколько элементов. Размер n-го блока – log n.

(Из Солтера: в деке не раскрыта схема управления памятью, как в векторе (через методы reserve() или capacity())).

Основные операции

begin()	end()	empty()	size()	max_size()	resize (n , value=0);
front()	back()	push_front()	pop_front()	push_back()	pop_back()
insert()	operator[]	erase()	swap()	clear()

Особенности применения

Аналогично вектору сохранность итераторов не гарантирована.

Быстрый доступ к элементам, быстрая вставка в начало и конец.

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

Stack и Queue

Stack

Устройство

stack<T> - контейнер-адаптер, где добавление и удаление элементов осуществляется с одного конца.

template < class T, class Container = deque<T> > class stack;

Основные операции

empty()

size()

empty()

top() – возвращает последний элемент, вставленный в стек.

push() - добавляет элемент

pop() – удаляет элемент

Особенности применения

Стек, являясь STL-контейнером, обеспечивает быструю вставку и удаление элементов. Структуру стека рекомендуется использовать в случае, когда необходимо реализовать FILO-семантику.

Например, системный администратор хотел иметь такое средство обработки ошибок, которое бы обеспечивало хранение данных об ошибках в стеке, чтобы самая последняя ошибка была доступной для изучения в первую очередь. Процесс обработки ошибок в FILO-порядке полезен потому, что "свежие" ошибки часто помогают устранить более давние.

Queue

Устройство

queue<T> - контейнер-адаптер, в один конец которого можно добавить элемент, а с другого - удалить. template < class T, class Container = deque<T> > class stack;

Шаблонный параметр Т задает тип элементов. Второй шаблонный параметр позволяет оговорить базовый контейнер, который эта очередь должна адаптировать. Поскольку очередь требует, чтобы базовый последовательный контейнер поддерживал методы push_back() и pop_back (), то у вас для выбора адаптируемого контейнера есть только два встроенных варианта: list и deque. По умолчанию дек.

Основные операции

empty()

size()

front()

back()

push() - добавляет элемент в конец очереди pop() – удаляет элемент из начала очереди

Особенности применения

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

Рассмотрим, например, рабо­ту банка.

Клиенты заходят в банк и становятся в очередь. Один из банковских служащих, отпустив текущего клиента, принимается обслуживать клиента из очереди, реализуя та­ким образом FIFO-поведение. Вы могли бы смоделировать ситуацию в банке, сохраняя объекты класса customer в очереди. По прибытии клиента в банк мы помещаем его в конец очереди. После того как банковский служащий, освободившись, будет готов к об­служиванию, к нему пригласят клиента, стоящего в очереди первым. Таким образом, клиенты обслуживаются в порядке, в котором они пришли в банк.

Map, Set

Map

Устройство

map<K,T> - упорядоченный ассоциативный массив пар ключ-значение.

Ключи должны быть уникальны.

Порядок следования элементов определяется ключами. При этом тип ключа должен реализовывать оператор сравнения operator<, либо требуется предоставить функцию-компаратор.

template < class Key, class T, class Compare = less<Key>, class Allocator =… > class map;

Основные операции

begin()	end()	empty()	size()	max_size()	insert()
operator[]	erase()	swap()	clear()

find – возвращает итератор на элемент. Поиск по ключу

count – считает количество элементов по заданному ключу

lower_bound – возвращает итератор на наименьший из элементов, перед которым будет вставлен элемент с заданным ключом

upper_bound – возвращает итератор за наибольший из элементов, перед которым будет вставлен элемент с заданным ключом

equal_range – тоже что-то делает  Особенности применения

map следует использовать в случаях, когда нужно свя­зать ключи и значения. Например, в сетевой игре, информацию об игроках можно хранить в map, используя в качестве ключа зарегистрированное (пользовательское) имя.

Set

Устройство

set<T> - ассоциативный контейнер, упорядоченное множество уникальных элементов.

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

Обеспечивает стандартные операции над множествами типа объединения, пересечения, вычитания.

Тип элементов множества должен реализовывать оператор сравнения operator< или требуется предоставить функцию-компаратор.

Реализован на основе самобалансирующего дерева двоичного поиска.

template < class Key, class Compare = less<Key>, class Allocator = … > class set

Основные операции

begin()	end()	empty()	size()	max_size()	insert()
operator[]	erase()	swap()	clear()

find()

lower_bound(), upper_bound()

equal_range()

count(key) – возвращает 1, если элемент найден и 0 в противном случае

Особенности применения

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

Bitset, vector<bool>

Bitset

Устройство

bitset<T> - псевдоконтейнер, служит для хранения битовых масок.

Похож на vector<bool> фиксированного размера.

Размер фиксируется тогда, когда объявляется объект bitset.

Итераторов в bitset нет.

Оптимизирован по размеру памяти.

Битовое множество— не настоящий STL-контейнер: он имеет фиксированный размер, не принимает шаблонный параметр для типа элемента и не поддерживает итеративный доступ к своим элементам.

Основные операции

operator[]

size()

set ( size_t pos, bool val = true ) - устанавливает биты

reset(pos) – устанавливает на 0 бит в позиции pos

flip(pos) – меняет значение бита на противоположное в позиции pos

count() – возвращает количество битов в bitset, которые установлены (=1)

test(pos) – возвращает значение бита на позиции pos

any – проверяет, установлены ли хоть какие-нибудь биты

none – проверяет, что никакие биты не установлены

Помимо основных методов манипуляции битами, битовое множество поддерживает реализации всех поразрядных операторов: &, |, ^, ~, «, », &=, |=, ^=, <<= и >>=. Они действуют так, как если бы обрабатывали "настоящую последовательность" битов.

Особенности применения

В качестве примера рассмотрим использование битового множества для отслеживания каналов для кабельных абонентов. Каждому абоненту можно было бы поставить в соответствие bitset-набор каналов, который он оплачивает. Такая система могла бы поддерживать даже "пакеты" каналов, также представляемые в виде битовых множеств, которые бы обозначали обычно подписываемые комбинации каналов.

vector<bool>

Специализацию vector<bool> можно представлять себе не как вектор, а как контейнер для битовых полей. Контейнер bitset обеспечивает реализацию битовых полей с более полным набором функций, чем контейнер vector<bool>. Однако к преимуществам специализации vector<bool> можно отнести его способность динамически изменять размер.

Устройство

В большинстве С++-компиляторов bool-значения имеют такой же размер, как и данные типа int. Специализация vector<Ьоо1> предполагает хранение "массива bool-значений", занимающих именно один бит, т.е. в "режиме экономии памяти".

Основные операции

К основным операциям вектора добавляется метод flip(). Его можно применить как ко всему контейнеру, так и к 1 элементу. Инвертирует биты.

Особенности применения

Позволяет в 8 раз сэкономить память

unordered_map

Устройство

unordered_map<K,T> - контейнер, который содержит пары ключ-значение. Позволяет быстро искать элементы по их ключу.

template < class Key, class T, class Hash = hash<Key> class Pred = equal_to<Key>, … > class unordered_map

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

Будучи шаблонными, их можно использовать для хранения произвольных элементов, таких как int или пользовательских классов.

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

Основные операции

empty()	size()	max_size()	size()	begin()	end()
operator[]	find()	count()	insert()	erase()	clear()
swap()

Особенности применения

priority_queue

priority_queue<T> - контейнер-адаптер являющийся очередью с приоритетом, организованной так, что самый большой элемент всегда стоит на первом месте.

template < class T, class Container = vector<T>, class Compare = less<…> > class priority_queue;

Устройство

Представляет собой вектор, который вызывает методы make_heap, push_heap и pop_heap

Основные операции

empty()

size()

top()

push()

pop() – удаляет верхний элемент

Особенности применения

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

Этот интерфейс обладает довольно ограниченными возможностями. В частности, адаптер priority_queue не предоставляет никакой итераторной поддержки и не позволяет объединять две очереди по приоритету в одну.