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

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

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

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

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

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

Примеры:

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

{

……….

}

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

{

…………

}

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.

 

Множество(set)

- шаблонный класс, который реализует функционал динамического отсортированного массива уникальных ключей.

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

Класс не позволяет хранить одинаковые ключи.

Пример:

#include <set>;

using namespace std;

void main()

{

set <int> m;

m.insert(20);

m.insert(10);

m.insert(30);

m.insert(30); //error

}

Ключи=данные!!!!!!!!!!!!

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

insert – вставка элемента с указанным ключом;

clear – очистка множества;

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

find – поиск элемента по ключу (получаем указатель на элемент(итератор), либо итератор эквивалентен итератору, полученному в результате использования операции end()).

 

Map(словарь)

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

Реализует принцип хеш-таблицы.

Поддерживает динамическое изменение размера массива, быстрый поиск любого элемента массива по ключу.

Класс не позволяет хранить одинаковые ключи, но позволяет хранить одинаковые значения для разных ключей.

Map – расширение set.

Ключ1	Ключ2	Ключ3	Ключ4	Ключ5
Значение1	Значение2	Значение1	Значение3	Значение4

Пример:

#include <map>

using namespace std;

void main()

{

map <int,double> m; //<тип ключа, тип значения>

m.insert(pair <int,double> (30,10.2));

m.insert(pair <int,double> (10,15.5));

m.insert(pair <int,double> (30,10.2));//error

}

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

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

Также следует отметить, что в данном контейнере реализован operator [].

Также важно помнить, что operator [] при обращении к несуществующему элементу в map создаст его. Новый элемент при этом будет инициализирован нулём (либо конструктором по умолчанию, если это не тривиальный тип данных). Данная особенность map может быть удобной, потому как выполнять операции с элементами можно не задумываясь об их присутствии в map.