Лекция 1. Стандартная (1114993)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Лекция 1. СтандартнаябиблиотекаКонтейнерыValery Lesin. C++ In-Depth, 2014Стандартная библиотека• Минимальный полный наборвозможностей для обеспечения базовыхпотребностейю.• Если что-то содержит, должнареализовывать лучшим образом (статьстандартом де-факто).• Алгоритмически эффективна.• Расширяема (может использовать какстандартные, так и пользовательские типы).Valery Lesin.

C++ In-Depth, 2014Состав стандартной библиотеки• Включает в себя CRT (C Run Time Library) иSTL (Standard Template Library)• Содержит– контейнеры: vector, list, map,unordered_set, …– утилиты: пары, аллокаторы, …– итераторы– алгоритмы: for_each, sort, lower_bound, …– диагностика: assert, exception, …– строки: string, wstring– ввод/вывод: потоки cout, cin; printf, …Valery Lesin. C++ In-Depth, 2014Состав стандартной библиотеки (2)• Содержит (продолжение):– локализацию– поддержку языка: numeric_limits, typeinfo,new/delete– числовые операции: complex, <cmath>• Для хидера <name.h> из CRT есть хидер<cname> с теми же объявлениями впространстве имен std• Используйте только стандартные хидерадля объявления стандартных типов ифункцийValery Lesin. C++ In-Depth, 2014Контейнеры STL• Реализуют стандартные операции ссоответствующими именами и смыслом.• Однородны – все хранимые объекты одноготипа.

Но могут хранить указатели(желательно умные) на полиморфные.• Требуют минимум от хранимого типа.• Универсально итерируемы.• Можно настроить (аллокаторы,компараторы).Valery Lesin. C++ In-Depth, 2014Типы контейнеров• Списочные: array, vector, list, deque,forward_list• Ассоциативные: map, set, multiset,multimap• Unordered: unordered_map,unordered_multiset, …• Адапторы: stack, queue, priority_queue• «Почти» контейнеры: bitset, string, …Valery Lesin.

C++ In-Depth, 2014Контейнер vector1234567891011121314151617181920template<class T, class Allocator = std::allocator<T>>class vector{typedef typename Tvalue_type;typedef Allocatorallocator_type;typedef typename Allocator::size_typesize_type;typedef typename Allocator::difference_type difference_type;typedef typename Allocator::pointerpointer;typedef typename Allocator::const_pointerconst_pointer;typedef typename Allocator::referencereference;typedef typename Allocator::const_reference const_reference;typedef impl-defined iterator;typedef impl-defined const_iterator;typedef reverse_iterator<iterator>reverse_iterator;typedef reverse_iterator<const_iterator> const_reverse_iterator;// ...};Valery Lesin.

C++ In-Depth, 2014Итераторы1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.20.21.22.23.template<class T, class Allocator = std::allocator<T>>class vector{// ...iteratorbegin();const_iterator begin() const;iteratorend();const_iterator end() const;reverse_iteratorrbegin();const_reverse_iterator rbegin() const;reverse_iteratorrend();const_reverse_iterator rend() const;const_iterator cbegin() const;const_iterator cend () const;const_reverse_iterator crbegin() const;const_reverse_iterator crend () const;// ...};Valery Lesin.

C++ In-Depth, 2014Итераторыreverse itcendItem 0begin1.2.Item 1Item 2itcbeginItem 3end&(*reverse_it) != &(*(revese_it.base()));&(*reverse_it) == &(*(std::prev(revese_it).base()));• Типы итераторов: Output; Input, Forward,Bidirectional, RandomAccessValery Lesin. C++ In-Depth, 2014По вектору в обратном направлении1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.20.// forwardfor (size_t i = 0; i < v.size(); ++i)cout << v[i] << endl;// naive backward (hmmm, with suprises)for (size_t i = v.size() - 1; i >= 0; ++i)cout << v[i] << endl;// correctfor (vector<int>::const_reverse_iterator it = v.rbegin();it != v.rend(); ++it)cout << *it << endl;// correct and tinyfor (auto it = v.rbegin(); it != v.rend(); ++it)cout << *it << endl;// range-based forfor (auto item : reverse(v))cout << item << endl;Valery Lesin.

C++ In-Depth, 2014Как устроен вектор?1.2.3.4.5.6.7.8.9.10.11.bool empty() const;size_type size () const;voidresize(size_type size, T val = T());size_type capacity() const;voidreserve (size_type size);voidclear();voidshrink_to_fit();iterator erase(const_iterator where);SizeCapacity• Вектор – динамический массив.• При нехватке места увеличивается ~ в 2 раза• Трудоемкость вставки в конец (!) –амортизированная O(1)Valery Lesin. C++ In-Depth, 2014Вставка и удаление из вектора1.2.3.4.5.6.7.8.9.10.11.12.13.// could be const_iterator since C++11vector<T>::iterator from, to, where;// random placev.insert(where, val);// usual erasev.erase(from, to);v.erase(where);// erase items with value with 'remove' function// or use 'remove_if' for predicate usagev.erase(v.begin(), remove(v.begin(), v.end(), 42));• Функция remove и remove_if ничего неудаляют, а лишь переносят в конец.Valery Lesin.

C++ In-Depth, 2014Вектор. Концевые элементы и индекс• Вектор позволяет эффективно вставлять иудалять элементы с конца. Но (!) несначала.1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.void push_back(T const& value);void push_back(T && value);template< class... Args >void emplace_back( Args&&... args );void pop_back();referenceback();const_reference back() const;referencefront();const_reference front() constpointer data(); // and constreference operator[](size_type index);referenceat(size_type index);Valery Lesin. C++ In-Depth, 2014Конструирование вектора• Конструктор по умолчанию, копирования,move-конструктор• А также:1.2.3.4.5.6.7.8.vector<T> v0(from, to);vector<T> v1(num, value);// reassign already constructed vectorv0.assign(from, to);// initializer list (since C++11)vector<int> v2 = {1, 42, 10, 20};Valery Lesin.

C++ In-Depth, 2014Контейнер sdt::list1.2.template<class T, class Alloc = std::allocator<T>>class list;• Двунаправленный список• Вставка, удаление из любого места О(1)• Нет RandomAccess итератора, толькоBidirectional• Полезны splice, sort• В отличие от вектора: pop_front, push_frontValery Lesin. C++ In-Depth, 2014Контейнер std::deque• Есть RandomAccess итератор (возможно,несколько менее эффективно, чем ввекторе)• Позволяет вставлять/удалять в начало иконец за O(1) (но не в произвольное место)• Часто реализуется через вектор векторовValery Lesin. C++ In-Depth, 2014Адаптеры• std::stack: push, pop, top• std::queue: push, pop, front, back• std::priority_queue: push, pop, top,constructor1.2.3.4.template<class T,class Container = vector<T>,class Pr = less<typename Container::value_type>>class priority_queue;Valery Lesin. C++ In-Depth, 2014Ассоциативные контейнеры• Наиболее популярный – std::map1.2.3.4.5.6.7.8.9.10.11.12.13.14.template<class Key,class Value,class Predicate = less<Key>,class Alloc = allocator<pair<const Key, Value>>>class map{// usually, some balanced tree (e.g.

red-black)public:typedef Keykey_type;typedef Valuemapped_type;typedef pair<const Key, Value> value_type;typedef Predicatekey_compare;// ...};Valery Lesin. C++ In-Depth, 2014Итерирование map1.2.3.4.5.6.7.8.map<string, size_t> marks;for (auto it = marks.begin(); it != marks.end(); ++it)cout << it->first << " " << it->second << endl;//...it->second = 5;it->first = "Vasya";// ok// nope, cannot change key• Итератор разыменовывается в пару.

Ключ –first, значение – second.Valery Lesin. C++ In-Depth, 2014Поиск и вставка в map1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.typedef std::map<string, size_t> map_t;typedef map_t::iteratoriterator;map_t m;// simple insertauto it = m.find(str);if (it != n.end())return ...;pair<iterator, bool> p =m.insert(make_pair(str, 5));// with 'hint'auto it = m.lower_bound(str);if (it != m.end() && it->second == str)return ...;m.insert(it, make_pair(str, 5));Valery Lesin. C++ In-Depth, 2014Индексирование1.2.3.4.5.6.typedef std::map<string, size_t> map_t;typedef map_t::iteratoriterator;map_t m;m[str] = 5;• Если элемента не было в map – добавит• Если был – оператора вернет ссылку ипроизойдет замена текущего значения (вотличие от insert)• Оператор [] всегда неконстантный.

Естьтолько у map, нет у set, multiset, multimap.Valery Lesin. C++ In-Depth, 2014Удаление из map (set)1.2.3.4.5.6.7.8.9.10.11.m.erase(key);m.erase(from, to);// with predicatefor (auto it = m.begin(); it != m.end(); ++it){if (predicate(*it))m.erase(it++);else++it;}Valery Lesin. C++ In-Depth, 2014Другие ассоциативные контейнеры• std::set – содержит только ключи• std::multimap, std::multiset – ключи могутповторяться• std::unordered_map/set– используют вычисление хэшей и предикатравенства вместо предиката порядка– вставка, удаление, поиск – амортизированнаяO(1)– Требуют больше памяти, чем обычные map/set– Есть более быстрые реализации: Googlesparse/dense hash map, MCT hash mapValery Lesin.

C++ In-Depth, 2014Спасибо за внимание!Вопросы?Valery Lesin. C++ In-Depth, 2014.

Характеристики

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций