Файл: Лабораторная работа 1 5 Бинарные деревья 5 Цель работы 5 Краткие теоретические сведения 5 Постановка задачи 6.docx

– массив строк с фамилиями людей, проживающих в данной квартире.

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

Библиотека STL предлагает четыре типа ассоциативных контейнеров set, multiset, map и multimap. Первые два типа объявлены в заголовочном файле set (set.h и multiset.h), а вторые два типа объявлены в заголовочном файле map (map.h и multimap.h).

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

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

Контейнер vector

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

Для использования контейнера вектор требуется подключить библиотеку , добавление элементов в конец будет осуществлять функция push_back (значение элемента), инициализируем вектор таким образом:

vector<тип данных вектора> название;

Итераторы

Итератор – вспомогательный объект, обеспечивающий доступ к элементам контейнера. Действие над итераторами: инкремент ++, декремент --, увеличение +.

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

Работа итераторов аналогично тому, как работают указатели. Итератор может быть объектом, для которого определены операции над указателями, такие как разыменовывание и инкремент. Итераторы необходимы для того, чтобы предоставлять однотипный интерфейс для множества классов-контейнеров, включая те, для которых обычные указатели не работают. Например, чтобы пройти по списку, не получится использовать обычный указатель, так как элементы списка не обязательно находятся в ячейках памяти последовательно. В этом случае создаётся класс «итератор», который, за счёт своей внутренней реализации, позволит последовательно перемещаться по списку, и будет иметь интерфейс, аналогичный указателю.

Для подключения итератора добавим библиотеку . Создадим итератор на вектор таким образом:

Vector a; //создаем вектор
vector <int>::iterator название итератора = a.begin();

//итератор указывает на начало вектора

Обращаться к элементам вектора будем, используя разыменование *it.

#include  
#include //подключаем библиотеку вектора
#include  //подключаем библиотеку итератора
using namespace std; 
void main() {
vector <int> a; //создаем вектор
for (int i = 0; i< 10; i++) 
a.push_back(i); //заполняем вектор значениями от 0 до 9
vector<int>::iterator it = a.begin(); 
//создаем итератор и указываем на начало вектора
while (it != a.end()) { /*пока итератор не указывает на конец вектора /
cout <<*it <<" "; //обращаемся к значению, разыменовывая итератор
it++; //переходим на следующий элемент
} 

}



Рисунок 4.1 – Выводим вектор через итератор

Для перемещения итератора на несколько значений нужно воспользоваться функцией advance (итератор, количество элементов).

void main() { 
vector <int> a; //создаем вектор
for (int i = 0; i< 10; i++) 
a.push_back(i);  // заполняем вектор значениями от 0 до 9
vector<int>::iterator it = a.begin(); //создаем итератор
advance(it, 5); //перемещаем итератор на 5 элементов
cout « *it « endl; //выводим новое значение итератора
}



Рисунок 4.2 – Смещение итератора.

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

Предопределенные итераторы

Библиотека STL предоставляет ряд заранее определённых итераторов.

Рассмотрим основные из них.

Потоковые итераторы

Шаблонные классы ostream_iterator и istream_iterator являются адаптерами – классами, которые преобразуют какой-то другой интерфейс в интерфейс, используемый STL. Они позволяют вставлять в поток и читать из потока данные с помощью итераторов, используя операции разыменовывания и инкремент. Итераторы этого вида можно создать, включив заголовочный файл iterator и сделав следующее объявление:

#include

// Объявление итератора out_iter типа ostream_iterator

ostream_iterator out_iter(cout, “ “);

// Использования итератора out_iter для вывода на экран

*out_iter = 15; // аналогично << 15 << “ “;

Первым шаблонным аргументом является тип элементов для итератора – int.

Первый аргумент конструктора является объектом потока ostream, второй (необязательный) существует только у класса ostream_iterator. Второй аргумент конструктора — это разделитель, который является С строкой и будет вставлен после каждой операции.

Обратные итераторы

Класс шаблона reverse_iterator предоставляет итератор, при инкрементировании которого, вызывается его декремент. Он позволяет пройти по контейнеру в обратном порядке. Для этого у некоторых контейнеров существуют специальные методы rbegin() и rend(), которые возвращают объект типа reverse_iterator. Для точного понимания, предположим, что в предыдущем примере мы бы использовали вместо begin() и end() методы rbegin() и rend(), тогда программа вместо 1|2|3|4|5|6| вывела бы 6|5|4|3|2|1|.


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

Контейнеры map и vector довольно похожи, единственное отличие в том, что в map можно поместить два значения. Например, если требуется написать словарь, лучше, чем map, альтернативы не найти.

Для использования map требуется подключить библиотеку

---

Постановка задачи

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

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

Третья программа демонстрирует использование алгоритмов STL.

В программе №1 реализовать следующие задачи:

1. Создать объект-контейнер в соответствии с вариантом задания и заполнить его данными, тип которых определяется вариантом задания.

2. Просмотреть контейнер.

3. Изменить контейнер, удалив из него одни элементы и заменив другие.

4. Просмотреть контейнер, используя для доступа к его элементам итераторы.

5. Создать второй контейнер этого же класса и заполнить его данными того же типа, что и первый контейнер.

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

7. Просмотреть первый и второй контейнеры.

В программе № 2 выполнить то же самое, но для данных пользовательского типа.

В программе № 3 реализовать следующие задачи:

1. Создать контейнер, содержащий объекты пользовательского типа. Тип контейнера выбирается в соответствии с вариантом задания.

2. Отсортировать его по убыванию элементов.

3. Просмотреть контейнер.

4. Используя подходящий алгоритм STL, найти в контейнере элемент, удовлетворяющий заданному условию, указанному в варианте.

5. Используя подходящий алгоритм STL переместить элементы, удовлетворяющие заданному условию в другой (предварительно пустой) контейнер. Тип второго контейнера определяется вариантом задания.

6. Просмотреть второй контейнер.

7. Используя подходящий алгоритм STL отсортировать первый и второй контейнеры по возрастанию элементов.

8. Просмотреть их.

9. Используя подходящий алгоритм STL получить третий контейнер путем слияния первых двух.

10. Просмотреть третий контейнер.

11. Используя подходящий алгоритм STL подсчитать, сколько элементов, удовлетворяющих заданному условию, содержит третий контейнер.

---

12. Используя подходящий алгоритм STL определить, есть ли в третьем контейнере элемент, удовлетворяющий заданному условию.

4. Варианты заданий

   № п/п	Первый контейнер	Второй контейнер	Встроенный тип данных
   1	vector	list	int
   2	list	deque	long
   3	deque	stack	float
   4	stack	queue	double
   5	queue	vector	char
   6	vector	stack	string
   7	map	list	long
   8	multimap	deque	float
   9	set	stack	int
   10	multiset	queue	char
   11	vector	map	double
   12	list	set	int
   13	deque	multiset	long
   14	stack	vector	float
   15	queue	map	int
   16	priority_queue	stack	char
   17	map	queue	char
   18	multimap	list	int
   19	set	map	char
   20	multiset	vector	int

5. Методические указания

---

1. Все программы размещаются в одной рабочей области(workspace).

2. Рабочая область должна содержать три проекта (по числу программ).

3. При создании контейнеров в программе № 2 объекты загружать из потока.

4. Для вставки и удаления элементов контейнера в программе № 2 использовать соответствующие операции, определенные в классе контейнера.

5. Для замены, удаления и копирования элементов использовать алгоритмы copy, copy_if, replace, replace_if, replace_copy_if, remove, remove_if, remove_copy_if.

6. Для поиска элемента в коллекции можно использовать алгоритм find_if, либо for_each, либо binary_search, если контейнер отсортирован.

7. Для сравнения элементов при сортировке по возрастанию используется операция <, которая должна быть перегружена в пользовательском классе. Для сортировки по убыванию следует написать функцию comp и использовать вторую версию алгоритма sort.

8. Условия поиска и замены элементов выбираются самостоятельно и для них пишутся объекты-функции либо используются стандартные объекты-функции и функциональные адаптеры.

9. Для ввода-вывода объектов пользовательского класса следует перегрузить операции “>>” и “<<”.

10. Некоторые алгоритмы могут не поддерживать используемые в вашей программе контейнеры. Например, алгоритм sort не поддерживает контейнеры, которые не имеют итераторов произвольного доступа. В этом случае следует написать свой алгоритм. Например, для стека алгоритм сортировки может выполняться следующим образом: переписать стек в вектор, отсортировать вектор, переписать вектор в стек.

11. При перемещении элементов ассоциативного контейнера в не ассоциативный контейнер перемещаются только данные (ключи не перемещаются). И, наоборот, при перемещении элементов не ассоциативного контейнера в ассоциативный должен быть сформирован ключ.

12. Там, где можно следует использовать итераторные адаптеры.

6. Содержание отчета

1. Постановка задачи (общая и для конкретного варианта)

2. Анализ задачи

• 
  Определения функций для реализации поставленных задач
  
• 
  Определение функции main()
  

3. Блок-схемы основных функций

4. Текст программы

5. Тесты

---