Question? Leave a message!




The Standard Template Library (STL)

The Standard Template Library (STL)
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Website URL
Comment
ECE 250 Algorithms and Data Structures The Standard Template Library Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering (STL) University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 2006-2013 by Douglas Wilhelm Harder. Some rights reserved.Standard Template Library 2 Outline In this topic, we will look at linked lists – The Node and List classes – Accessors and mutators – The implementation of various member functions – Stepping through a linked list – Defining the copy and assignment operator – Defining move constructors and move assignment operators – Discussed efficienciesStandard Template Library 3 Arrays The Standard Template Library has three variations on arrays: template typename T, size_t N class array; template typename T, class Alloc = allocatorT class vector; template size_t N class bitset;Standard Template Library 4 arrayT, N This is a sequence container with a linear order – Elements are accessed by their position The memory allocation is contiguous – Random access is Q(1) The memory is allocated at compile timeStandard Template Library 5 arrayT, N To make return types more standard, the C++ STL defines specific member types associated with each class: arrayT, N::value_type T arrayT, N::reference T & arrayT, N::const_reference T const & arrayT, N::pointer T arrayT, N::const_pointer T const arrayT, N::iterator arrayT, N::const_iterator arrayT, N::reverse_iterator arrayT, N::const_reverse_iterator arrayT, N::size_type size_t arrayT, N::difference_type ptrdiff_tStandard Template Library 6 arrayT, N Member functions include: – The eight iterators begin end rbegin rend cbegin cend crbegin crend iterator begin() noexcept; const_iterator begin() const noexcept; const_iterator cbegin() const noexcept; – Capacity constexpr size_type size() noexcept; constexpr size_type max_size() noexcept; constexpr bool empty() noexcept;Standard Template Library 7 arrayT, N Member functions include: – Element access reference operator( size_type ); const_reference operator( size_type ) const; reference at( size_type ); const_reference at ( size_type ) const; reference front(); const_reference front() const; reference back(); const_reference back() const; pointer data() noexcept; const_pointer data() const noexcept;Standard Template Library 8 arrayT, N Member functions include: – Modifiers void fill( const_reference ); void swap( array & ) noexcept( ... );Standard Template Library 9 arrayT, N Example: include array int main() std::arrayint, 5 v; for ( int i = 0; i 5; ++i ) vi = i; for ( auto itr = v.begin(); itr = v.end(); ++itr ) itr = (itr)2; v.fill( 7 ); int ptr = v.data(); return 0; Standard Template Library 10 bitsetNStandard Template Library 11 vectorT This is a sequence container with a linear order – Elements are accessed by their position The memory allocation is contiguous – Random access is Q(1) The array allocation is dynamic – The size of the array can change at runtime The user can specify the method of allocationStandard Template Library 12 vectorT To make return types more standard, the C++ STL defines specific member types associated with each class: vectorT::value_type T vectorT::reference T & vectorT::const_reference T const & vectorT::pointer T vectorT::const_pointer T const vectorT::iterator vectorT::const_iterator vectorT::reverse_iterator vectorT::const_reverse_iterator vectorT::allocator_type allocatevalue_type vectorT::size_type size_t vectorT::difference_type ptrdiff_tStandard Template Library 13 vectorT Member functions include: – Constructors explicit vector(); explicit vector( size_type ); vector( size_type, const_reference ); template class InputIterator vector( InputIterator first, InputIterator last ); vector( vector const & ); vector( vector && ); vector( initializer_listvalue_type );Standard Template Library 14 vectorT Member functions include: – Assignment operator vector &operator=( vector const & ); vector &operator=( vector && ); vector &operator=( initializer_listvalue_type ); – The last lets us: std::vectorint v(10); v = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10;Standard Template Library 15 vectorT Member functions include: – The eight iterators begin end rbegin rend cbegin cend crbegin crend – Each has the various signatures: iterator begin() noexcept; const_iterator begin() const noexcept; const_iterator cbegin() const noexcept;Standard Template Library 16 vectorT Member functions include: – Capacity size_type size() const noexcept; size_type capacity() const noexcept; size_type maxsize() const noexcept; void resize( size_type ); void resize( size_type, const_reference ); bool empty() const noexcept; bool empty() const noexcept; void reserve( size_type ); void shrink_to_fit();Standard Template Library 17 vectorT Member functions include: – Element access reference operator( size_type ); const_reference operator( size_type ) const; reference at( size_type ); const_reference at ( size_type ) const; reference front(); const_reference front() const; reference back(); const_reference back() const; pointer data() noexcept; const_pointer data() const noexcept;Standard Template Library 18 vectorT Member functions include: – Modifiers template class Iterator void assign( Iterator, Iterator ); void assign( size_type, const_reference ); void assign( initializer_listvalue_type ); void push_back( const_reference ); void push_back( value_type&& ); void pop_back();Standard Template Library 19 vectorT Member functions include: – Modifiers iterator insert( const_iterator position, const_reference ); iterator insert( const_iterator position, size_type n, const_reference ); template class Iterator iterator insert( const_iterator position, Iterator first, Iterator last ); iterator insert( const_iterator position, value_type&& ); iterator insert( const_iterator position, initializer_listvalue_type );Standard Template Library 20 vectorT Member functions include: – Allocator allocator_type get_allocator() const noexcept; – Non-member function overloads template typename T void swap( vectorT &, vectorT & ); template typename T bool operator==( const vectorT &, const vectorT & ); • Includes the relational operators =, , =, , and = • Uses a lexicographical comparison