План лекции
Источники информации. 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.shtml http://en.wikipedia.org/wiki/Standard_Template_Library
http://ru.cppreference.com/w/cpp/container/vector
http://www.cplusplus.com/reference/algorithm/
Введение в стандартную библиотеку шаблонов (классов коллекций), основные понятия
1.1 Как STL добавилось в С++
Изначально потребность повторно использовать код классов и структур, подпрограмм покрывалась за счет копирования, затем стали использовать средства препроцессора (пример ниже), затем появились шаблоны в языке, также параллельно шла разработка библиотеки с общим функционалом. Их было много. Наиболее популярной стала STL.
Макросы-шаблоны
До появления шаблонов были макросы. Можете оценить, как генерировались уникальные имена классов и передавались аргументы.
#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 – standard template library. Стандартная библиотека шаблонов.
Также хотели отказаться от использования массивов: людей напрягало, что массивы это нечто низкоуровневое, за массивом приходится тягать его размер, работа с массивами, как присваивание, копирование, сортировка были недостаточно комфортными: это приходилось делать руками, что отнимало время, у новичков были вопросы с выходом за границы массивов (которые, как известно, в С++ молчаливо проглатываются) и удалением данных, устойчивым в том числе к исключениям. Также хотелось сделать синтаксис работы с массивами более выразительным, чтобы код было легче читать, а, стало быть, и сопровождать.
С этого момента вам воспрещается использовать массивы в коде. Только в крайних случаях. Вместо массивов используйте, например, вектор.
