STL_ ассоциативные контейнеры и_итераторы (1114991)
Текст из файла
STL: ассоциативные контейнеры и итераторыSTL: ассоциативные контейнеры иитераторыАлександр СмальCS центр19 февраля 2014Санкт-Петербургhttp://compscicenter.ru1/23STL: ассоциативные контейнеры и итераторыSTL: введение∙ STL = Standard Template Library∙ STL описан в стандарте C++, но не упоминается там явно.∙ Авторы: Александр Степанов, Дэвид Муссер и Менг Лидля HP, а потом для SGI.∙ Основан на разработках для языка Ада.∙ Основные составляющие:∙ контейнеры (хранение объектов в памяти),∙ итераторы (доступ к элементам контейнера),∙ алгоритм (для работы с последовательностями),∙ адаптеры (обёртки над контейнерами)∙ функциональные объекты, функторы (обобщениефункций).∙ потоки ввода/вывода.∙ Всё определено в пространстве имён std.http://compscicenter.ru2/23STL: ассоциативные контейнеры и итераторыОбщие сведения о контейнерахКонтейнеры библиотеки STL можно разделить на четырекатегории:∙ последовательные,∙ ассоциативные,∙ контейнеры-адаптеры,∙ псевдоконтейнеры.Требования к хранимым объектам:1.
copy-constuctable2. assignable3. “стандартная семантика”Итераторы — объекты для доступа к элементам контейнера ссинтаксисом указателей.http://compscicenter.ru3/23STL: ассоциативные контейнеры и итераторыОбщие члены контейнеровТипы (typedef-ы или вложенные класс):1. C::value_type2. C::reference3. C::const_reference4. C::pointer5. C::iterator6. C::const_iterator7. C::size_typeМетоды:1.
Конструктор по умолчанию, конструктор копирования,оператор присваивания, деструктор.2. begin(), end()3. Операторы сравнения: ==, !=, >, >=, <, <=.4. size(), empty().5. swap(obj2)http://compscicenter.ru4/23STL: ассоциативные контейнеры и итераторыАссоциативные контейнерыОбщие методы:1. erase по key2. count3. find4.
lower_bound, upper_bound, equal_range5. insert с подсказкойОсобенности:1. Требуют отношение порядка.2. Нет произвольного доступа.http://compscicenter.ru5/23STL: ассоциативные контейнеры и итераторыset, multisetstd :: set < int > primes ;primes . insert (2);primes . insert (3);primes . insert (5);...if ( primes . find (173) != primes . end ())std :: cout << 173 << " is prime \ n " ;for ( std :: set < int >:: iterator it= primes . begin ();it != primes . end (); ++ it )std :: cout << * it << ’\ n ’;// –––––––––––––––std :: multiset < int > ms ;ms . insert (1);ms . insert (2);ms . insert (2); // ms.size() == 3std :: cout << ms .
count (2) << ’\ n ’;http://compscicenter.ru6/23STL: ассоциативные контейнеры и итераторыmap, multimapХранит пару ключ-значение std::pair.template < class F , class S >struct pair {... // constructorsFfirst ;Ssecond ;};template < class F , class S >pair <F , S > make_pair ( F const & f , S const & s );template < class Key , class T , ...
> class map {...typedef pair < const Key , T > value_type ;} ;Особые методы:∙ operator[]http://compscicenter.ru7/23STL: ассоциативные контейнеры и итераторыmap, multimapstd :: map < string , int > phonebook ;phonebook . insert ( std :: make_pair ( " Mary " , 2128506));phonebook . insert ( std :: make_pair ( " Alex " , 9286385));phonebook . insert ( std :: make_pair ( " Bob " ,2128506));...std :: map < string , int >:: iterator it = phonebook .
find ( " John " );if ( it != phonebook . end ())std :: cout << " Jonh ’s p / n is " << it - > second << " \ n " ;for ( it = phonebook . begin (); it != phonebook . end (); ++ it )std :: cout << it - > first << " : " << it - > second << " \ n " ;// –––––––––––––––std :: multmap < string , int > pb ;pb . insert ( std :: make_pair ( " Mary " , 2128506));pb .
insert ( std :: make_pair ( " Mary " , 2128507));pb . insert ( std :: make_pair ( " Mary " , 1112223)); //ms.size()==3std :: cout << pb . count ( " Mary " ) << ’\ n ’;http://compscicenter.ru8/23STL: ассоциативные контейнеры и итераторыmap::operator[]std :: map < string , int > phonebook ;phonebook . insert ( std :: make_pair ( " Mary " , 2128506));...phonebook . insert ( std :: make_pair ( " Mary " , 2128507)); // failstd :: pair < std :: map < string , int >:: iterator , bool > res =phonebook . insert ( " Mary " , 2128507); // res.second == falsestd :: map < string , int >:: iterator it = phonebook . find ( " Mary " );if ( it != phonebook . end () )it - > second = 2128507;else phonebook .
insert ( std :: make_pair ( " Mary " , 2128507));// ORphonebook [ " Mary " ] = 2128507;for ( it = phonebook . begin (); it != phonebook . end (); ++ it )std :: cout << it - > first << " : " << phonebook [ it - > first ] << " \ n " ;http://compscicenter.ru9/23STL: ассоциативные контейнеры и итераторыОграничения map::operator[]1. Работает только с неконстантным map.2.
Требует наличие конструктора по умолчанию у T.T & operator []( Key const & k ){iterator i = find ( k );if ( i == end ())i = insert ( value_type (k , T ())). first ;return i - > second ;}3. Работает за O(log n). ⇒ Не стоит работать с map как cмассивом!http://compscicenter.ru10/23STL: ассоциативные контейнеры и итераторыУдаление из set и mapНеправильный вариантstd :: map < string , int > m ;std :: map < string , int >:: iterator it = m . begin ();for ( ; it != m . end (); ++ it )if ( it - > second == 0)m . erase ( it );Непереносимый вариант (стандарт C++ 11)for ( ; it != m . end (); )if ( it - > second == 0) it = m . erase ( it );else++ it ;Правильный вариантfor ( ; it != m .
end (); )if ( it - > second == 0) m . erase ( it ++);else++ it ;http://compscicenter.ru11/23STL: ассоциативные контейнеры и итераторыИспользование собственного компаратораstruct Person {string name ;string surname ;};bool operator <( Person const & a , Person const & b ) {return a . name < b . name ||( a . name == b . name && a . surname < b . surname );}std :: set < Person > s1 ; // unique by name+surnamestruct PersonComp {bool operator ()( Person const & a , Person const & b ) const {return a . surname < b .
surname ;}};std :: set < Person , PersonComp > s2 ; // unique by surnameshttp://compscicenter.ru12/23STL: ассоциативные контейнеры и итераторыТребования к компараторуКомпаратор должен задавать отношение строгого порядка:¬(x ≺ y ) ∧ ¬(y ≺ x) ⇒ x = yhttp://compscicenter.ru13/23STL: ассоциативные контейнеры и итераторыinsert с подсказкойstd :: map <K , V > m ;K k = ...;V v = ...;std :: map <K , V >:: iterator i = m .
find ( k ); // returns m.end()std :: map <K , V >:: iterator hint = m . lower_bound ( k );if ( hint != m . end () && !( k < hint - > first ))// gotcha!else// use hintm . insert ( hint , std :: make_pair (k , v ));http://compscicenter.ru14/23STL: ассоциативные контейнеры и итераторыКатегории итераторовИтератор — синтаксически похожий на указатель объект длядоступа к элементам последовательности.Итераторы делятся на пять категорий.∙ Random access iterator. ++, --, арифметика, read-write∙ Bidirectional iterator.
++, --, read-write∙ Forward iterator. ++, read-write∙ Input iterator. ++, read∙ Output iterator. ++, writeФункции для работы с итераторами:voidadvance( Iterator & it , size_t n );size_t distance ( Iterator f , Iterator l );voiditer_swap ( Iterator i , Iterator j );http://compscicenter.ru15/23STL: ассоциативные контейнеры и итераторыiterator_traits// <iterator>template < class Iterator >struct iterator_traits {typedef difference_t y peIterator :: d if f er en c e_ ty p e ;typedef value_typeIterator :: value_type ;typedef pointerIterator :: pointer ;typedef referenceIterator :: reference ;typedef i te rat or_ ca t e g o r y Iterator :: i t e r a t o r _ c a t e g o r y ;};template < class Iterator >void iter_swap ( Iterator i , Iterator j ) {// Iterator::value_type t = *i;typename iterator_traits < Iterator >:: value_type t = * i ;*i = *j;*j = t;}http://compscicenter.ru16/23STL: ассоциативные контейнеры и итераторыiterator_traits для указателей// <iterator>template < class T >struct iterator_traits < T * > {typedef difference_t y peptrdiff_t ;typedef value_typeT;typedef pointerT *;typedef referenceT &;typedef i te rat or_ ca t e g o r y r a n d o m _ a c c e s s _ i t e r a t o r _ t a g ;};http://compscicenter.ru17/23STL: ассоциативные контейнеры и итераторыiterator_categorystruct b i d i r e c t i o n a l _ i t e r a t o r _ t a g {};struct f o r w a r d _ i t e r a t o r _ t a g {};struct in pu t _i t er a to r _t a g {};struct o u t p ut _ i t e r a t o r _ t a g {};struct r a n d o m _ a c c e s s _ i t e r a t o r _ t a g {};template < class Iterator >void advance ( Iterator & i , size_t n ) {advance_impl (i , n , typename iterator_traits < Iterator >::i t e r a t o r _ c a t e g o r y ());}template < class Iterator >void advance_impl ( Iterator & i , size_t n , r a n d o m _ a c c e s s _ i t e r a t o r _ t a g ){ i += n ; }template < class Iterator >void advance_impl ( Iterator & i , size_t n , ...
) {for ( size_t k = 0; k != n ; ++ k , ++ i );http://compscicenter.ru18/23STL: ассоциативные контейнеры и итераторыreverse_iteratorУ стандартных контейнеров есть обратные итераторы:list < int > l ;for ( list < int >:: reve r s e _ i t e r a t o r i= l . rbegin ();i != l . rend (); ++ i )...Конвертация итераторов:iteratori;r e v erse_iterator ri = i ;i = ri . base ();Есть возможность сделать reverse итератор по RA или BiDi.# include < iterator >template < class Iterator >class r everse_iterator ;http://compscicenter.ru19/23STL: ассоциативные контейнеры и итераторыAdvanced итераторыОпределены следующие специальные итераторы итераторов:1.
back_inserter, front_inserter, inserter2. istream_iterator, ostream_iteratorvector < Person > db ;template < class OutIt >void findByName ( vector < Person > const & db ,string name , OutIt out );...vector < Person > res ; // size is not knownfindByName ( db , " Ivan " , std :: back_inserter ( res ));ifstream file ( " input . txt " );vector < double > v (( istream_iterator < double >( file )) ,istream_iterator < double >());copy ( v . begin () , v .
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
