Белорусский Государственный Университет Информатики и Радиоэлектроники

Конструирование программ

Лекции

2 Часть

Лекция 4 – STL

План лекции

Источники информации 5

1Введение в стандартную библиотеку шаблонов (классов коллекций), основные понятия 6

1.1 Как STL добавилось в С++ 6

1.2 Введение в STL 7

2 Контейнеры 9

2.1 Простые контейнеры 9

2.1.1 Пара (Pair / Tuple) 9

2.2 Контейнеры с последовательным доступом 10

2.2.1 Вектор (vector) 10

2.2.2 Список (list) 11

2.2.3 forward_list 13

2.2.4 Очередь двухсторонняя (deque) 13

2.3 Контейнеры-адаптеры 13

2.3.1 Очередь односторонняя (queue) 13

2.3.2 Очередь с приоритетами (priority queue) 14

2.3.3 Стек (stack) 15

2.4 Контейнеры с доступом к случайным элементам 15

2.4.1 Упорядоченное множество элементов (set) 15

2.4.2 multiset 16

2.4.3 Словарь (map) 16

2.4.4 multimap 18

2.4.5 unordered_set, unordered_multiset, unordered_map, unordered_multimap 18

2.5 Другие типы контейнеров 19

2.5.1 bitset 19

2.5.2 valarray 19

2.6 Как работает push_back в vector. Новый метод emplace_back 19

3 Итераторы 20

4 Алгоритмы 21

4.1 Не модифицируют коллекцию 21

4.1.1 all_of / any_of / none_of 22

4.1.2 for_each 22

4.1.3 find / find_if / find_if_not / find_end / find_first_of 23

4.1.4 count / count_if 24

4.1.5 mismatch 24

4.1.6 equal / is_permutation 24

4.1.7 search / search_n 24

4.2 Модифицируют коллекцию 24

4.2.1 copy / copy_n / copy_if / copy_backward 24

4.2.2 move / move_backward 25

4.2.3 swap / swap_ranges 25

4.2.4 transform 25

4.2.5 replace / replace_if / replace_copy / replace_copy_if 25

4.2.6 fill / fill_n 26

4.2.7 generate / generate_n 26

4.2.8 remove / remove_if / remove_copy / remove_copy_if 26

4.2.9 unique / unique_copy 26

4.2.10 reverse / reverse_copy 26

4.2.11 rotate / rotate_copy 26

4.2.12 shuffle / random_shuffle 26

4.3 Расположения элементов в коллекции (партиции) 26

4.3.1 is_partioned 26

4.3.2 partition / stable_partition / partition_copy 26

4.3.3 partition_point 26

4.4 Сортировка 27

4.4.1 sort / stable_sort 27

4.4.2 partial_sort / partial_sort_copy 27

4.4.3 is_sorted / is_sorted_until 27

4.5 Бинарный поиск 27

4.5.1 lower_bound / upper_bound 27

4.5.2 equal_range 27

4.5.3 binary_search 28

4.6 Слияние (работает над отсортированными коллекциями только) 28

4.6.1 merge 28

4.6.2 includes 28

4.6.3 set_union / set_intersection / set_difference / set_symetric_difference 28

4.7 Управление кучей (не используются, рассматривать нет смысла) 28

4.7.1 push_heap / pop_heap / make_heap 28

4.7.2 sort_heap 28

4.7.3 is_heap / is_heap_until 28

4.8 min/max 28

4.8.1 min / max / minmax 28

4.8.2 min_element / max_element / minmax_element 28

5 Функторы, лямбда-выражения 29

6 Будущее STL 30

7 Наследование и работа с памятью в STL 31

Источники информации

http://www.solarix.ru/for_developers/cpp/stl/stl.shtmlhttp://en.wikipedia.org/wiki/Standard_Template_Library

http://ru.cppreference.com/w/cpp/container/vector

http://www.cplusplus.com/reference/algorithm/

1. Введение в стандартную библиотеку шаблонов (классов коллекций), основные понятия

1.1 КакSTLдобавилось в С++

Изначально потребность повторно использовать код классов и структур, подпрограмм покрывалась за счет копирования, затем стали использовать средства препроцессора (пример ниже), затем появились шаблоны в языке, также параллельно шла разработка библиотеки с общим функционалом. Их было много. Наиболее популярной стала STL.

1.1.1 Макросы-шаблоны

До появления шаблонов были макросы. Можете оценить, как генерировались уникальные имена классов и передавались аргументы.

#define LANG( cName, lName ) \

class cName \

{ \

public: \

cName()\

{ \

_langName = SET_LANG( lName ); \

_reader = new PDDefFileReader( _langName ); \

} \

~cName(){}\

\

std::string Str(){ return _langName; } \

\

private: \

PDDefFileReader* _reader; \

std::string _langName; \

}; \

С ними были проблемы: плохо отлаживать подпрограмму.

1.1.2 Появление STLв С++

В 1971 г. Дэвид Мюссер разработал некоторые концепты шаблонного программирования для вычисления алгебраических выражений.

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

1987. Они вместе выпустили библиотеку шаблонов для языка Ада. Потом увидели, что она не получила распространения из-за ограниченности применения Ады оборонными системами.

Затем они разработали библиотеку шаблонов для популярного языка на тот момент – С++.

1998. Впоследствии, эта библиотека была включена в С++ официально, поскольку язык в тот момент проходил стандартизацию ISO.

STL–standardtemplatelibrary. Стандартная библиотека шаблонов.

Также хотели отказаться от использования массивов: людей напрягало, что массивы это нечто низкоуровневое, за массивом приходится тягать его размер, работа с массивами, как присваивание, копирование, сортировка были недостаточно комфортными: это приходилось делать руками, что отнимало время, у новичков были вопросы с выходом за границы массивов (которые, как известно, в С++ молчаливо проглатываются) и удалением данных, устойчивым в том числе к исключениям. Также хотелось сделать синтаксис работы с массивами более выразительным, чтобы код было легче читать, а, стало быть, и сопровождать.

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