Особенности реализации класса.

Если параметризованный класс применяется для производных типов данных (классы и структуры), то для производных типов следует выделить 2 важных момента:

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

2. Для возвращения значения функцией pop и присвоения значения переменной класса необходимо:

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

2. Перегрузить оператор присвоения в производном классе.

Примеры:

A(const A&) – присваивающий конструктор.

{

……….

}

A& operator =(const A&) – оператор присвоения

{

…………

}

24 Stl. Контейнеры. Вектор (vector), список (list), дек (deque). Множество (set), словарь (map), стек (stack).

STL – Standard Template Library (стандартная библиотека шаблонов).

Основной целью проектирования библиотеки STL является объединение разных структур данных с алгоритмами, которые их(структуры данных) обрабатывают для обеспечения простоты использования и оптимального быстродействия. Библиотека STL основана на использовании шаблонов (т.e. на использовании параметризованных классов и функций). Вся библиотека STL реализована в пространстве имен std. Библиотека содержит 5 основных компонентов:

1. Контейнеры.

2. Итераторы.

3. Алгоритмы.

4. Аллокаторы.

5. Функциональные объекты.

Контейнеры.

Контейнеры обеспечивают размещение в динамической памяти коллекций данных различных типов.

Типы контейнеров:

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

vector - динамический массив;

list – двусвязный динамический список;

deque – двусторонняя очередь или очередь с двусторонним доступом.

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

set – множество, в котором каждый элемент уникален;

multiset – множество с дубликатами (каждый элемент необязательно уникален);

map – словарь (отображение). Хранит пары “ключ-значение”, в котором каждый ключ связан только с одним значением;

multimap – словарь с дубликатами (мультиотображение). Хранит пары “ключ-значение”, в которых каждый ключ может быть связан с двумя или более значениями;

hash_set – хеш-множество (хешированный ассоциативный контейнер) (не применимо отношение порядка) (хранит объекты типа “ключ”) (знакомая нам структура, которая позволяет добавлять, удалять и проверять наличие элемента во множестве) (Для быстрого доступа используются хеш-функции, также используется бинарный предикат, для проверки ключей на равенство);

hash_multiset – (хешированный ассоциативный контейнер) хеш-множество с дубликатами (в отличие от hash_set, может иметь несколько одинаковых элементов);

hash_map – (хешированный ассоциативный контейнер) хеш-отображение(реализует интерфейс Map (что подразумевает хранение данных в виде пар ключ/значение). Ключи и значения могут быть любых типов, в том числе и null. Данная реализация не дает гарантий относительно порядка элементов с течением времени. Для быстрого доступа к элементу по ключу используется специальная хеш-функция. Также используется бинарный предикат для проверки двух ключей на равенство);

hash_multimap – (хешированный ассоциативный контейнер) хеш-отображение с дубликатами (в отличие от hash_map, некоторые элементы hash_multimap могут иметь один и тот же ключ).

3)Адаптеры контейнеров:

stack – стек;

queue – очередь;

priority_queue – очередь с приоритетом.

Vector

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

Пример:

#include <vector>

using namespace std;

void main()

{ vector<int> m;

int v;

m.push_back(10); //m[0]=10

m.push_back(20); //m[1]=20

v=m[0]; //v=10

v=m[1]; //v=20

}

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

1. все операторы сравнения (= = , !=, <, >, <=, >=);

2. [] – доступ к элементу по индексу.

Основные функции:

push_back – добавление элемента в конец (увеличивает размер массива);

pop_back – удаление элемента с конца (уменьшает размер массива);

insert – вставка элемента в указанную позицию;

clear – очистка массива (удаление всех элементов);

size – определение количества элементов в динамическом массиве;

swap – меняет два элемента в массиве местами.

List

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

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

Пример:

#include <list>

using namespace std;

void main ()

{

list <int> m;

int v;

m.push_back(10);

m.push_back(20);

m.push_front(1);

……

}

Основные функции.

push_back(front) – добавление элемента в конец (начало) списка (увеличивается размер списка);

pop_back(front) – выталкивание элемента с конца (начала) списка (уменьшается размер списка);

insert – вставка элемента в список;

clear – очистка списка;

size – получение сведений о количестве элементов;

swap – замена двух элементов местами (по указателям).

Deque

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

Пример:

#include <deque>

using namespace std;

void main()

{

deque<int> m;

int v;

m.push_back(10);

m.push_front(20);

m.push_back(30);

v=m[0]; //20

v=m[1]; //10

v=m[2]; //30

}

Основные функции.

Функционал такой же как у list.