Question? Leave a message!




The Standard Template Library (STL)

The Standard Template Library (STL)
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 © 20062013 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, sizet N class array; template typename T, class Alloc = allocatorT class vector; template sizet 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::valuetype T arrayT, N::reference T arrayT, N::constreference T const arrayT, N::pointer T arrayT, N::constpointer T const arrayT, N::iterator arrayT, N::constiterator arrayT, N::reverseiterator arrayT, N::constreverseiterator arrayT, N::sizetype sizet arrayT, N::differencetype ptrdifftStandard Template Library 6 arrayT, N Member functions include: – The eight iterators begin end rbegin rend cbegin cend crbegin crend iterator begin() noexcept; constiterator begin() const noexcept; constiterator cbegin() const noexcept; – Capacity constexpr sizetype size() noexcept; constexpr sizetype maxsize() noexcept; constexpr bool empty() noexcept;Standard Template Library 7 arrayT, N Member functions include: – Element access reference operator( sizetype ); constreference operator( sizetype ) const; reference at( sizetype ); constreference at ( sizetype ) const; reference front(); constreference front() const; reference back(); constreference back() const; pointer data() noexcept; constpointer data() const noexcept;Standard Template Library 8 arrayT, N Member functions include: – Modifiers void fill( constreference ); 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::valuetype T vectorT::reference T vectorT::constreference T const vectorT::pointer T vectorT::constpointer T const vectorT::iterator vectorT::constiterator vectorT::reverseiterator vectorT::constreverseiterator vectorT::allocatortype allocatevaluetype vectorT::sizetype sizet vectorT::differencetype ptrdifftStandard Template Library 13 vectorT Member functions include: – Constructors explicit vector(); explicit vector( sizetype ); vector( sizetype, constreference ); template class InputIterator vector( InputIterator first, InputIterator last ); vector( vector const ); vector( vector ); vector( initializerlistvaluetype );Standard Template Library 14 vectorT Member functions include: – Assignment operator vector operator=( vector const ); vector operator=( vector ); vector operator=( initializerlistvaluetype ); – 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; constiterator begin() const noexcept; constiterator cbegin() const noexcept;Standard Template Library 16 vectorT Member functions include: – Capacity sizetype size() const noexcept; sizetype capacity() const noexcept; sizetype maxsize() const noexcept; void resize( sizetype ); void resize( sizetype, constreference ); bool empty() const noexcept; bool empty() const noexcept; void reserve( sizetype ); void shrinktofit();Standard Template Library 17 vectorT Member functions include: – Element access reference operator( sizetype ); constreference operator( sizetype ) const; reference at( sizetype ); constreference at ( sizetype ) const; reference front(); constreference front() const; reference back(); constreference back() const; pointer data() noexcept; constpointer data() const noexcept;Standard Template Library 18 vectorT Member functions include: – Modifiers template class Iterator void assign( Iterator, Iterator ); void assign( sizetype, constreference ); void assign( initializerlistvaluetype ); void pushback( constreference ); void pushback( valuetype ); void popback();Standard Template Library 19 vectorT Member functions include: – Modifiers iterator insert( constiterator position, constreference ); iterator insert( constiterator position, sizetype n, constreference ); template class Iterator iterator insert( constiterator position, Iterator first, Iterator last ); iterator insert( constiterator position, valuetype ); iterator insert( constiterator position, initializerlistvaluetype );Standard Template Library 20 vectorT Member functions include: – Allocator allocatortype getallocator() const noexcept; – Nonmember 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 comparisonStandard Template Library 21 vectorbool One specialization of vector is for Boolean values: – Normally, each bool occupies one byte – Reasonable specializations of vectorbool use one bit per entry – One new function: void flip() noexcept; – A mechanism for referencing individual bits and interpreting them as type boolStandard Template Library 22 vectorT, Alloc One thing that has been overlooked is: how is memory allocated By default, memory allocation is performed using new and delete – What if this is too slow or inappropriate for a particular use of vector The actual class definition is: template typename T, class Alloc = allocatorT class vector;Standard Template Library 23 vectorT, Alloc An allocator class must have specific member types and functions: template class T class Allocator public: typedef T valuetype; typedef T pointer; typedef const T constpointer; typedef T reference; typedef const T constreference; typedef std::sizet sizetype; typedef std::ptrdifft differencetype; typedef propagateoncontainermoveassignment truetype; template class U struct rebind typedef AllocatorU other; ;Standard Template Library 24 vectorT, Alloc allocator() nothrow; allocator ( const allocator ) nothrow; template class U allocator( const allocatorU ) nothrow; allocator() throw; pointer address( reference ) const noexcept; constpointer address( constreference ) const noexcept; pointer allocate( sizetype, allocatorvoid::constpointer = 0 ); void deallocate( pointer, sizetype ); sizetype maxsize() const nothrow; template class U, class... Args void construct( U p, Args... args ); template class U void destroy ( U p ); ;Standard Template Library 25 vectorT, Alloc Why would you want a different allocator – Suppose you want persistent memory allocation—allocation that continues from one execution of a program to the next – Intel’s thread building blocks improve the performance of multithreaded applications by using std::vector T, tbb::scalableallocatorT – Electronic Arts has a STL optimized for gaming software—memory tends to be more restrictive on gaming platforms – Tracking allocations and deallocations for debugging or efficiency – Suppose you want to use memorymapped files—addresses in memory that are mapped not to RAM but to virtual memory From the point of view of portability, all the machine specific things which relate to the notion of address, pointer, and so on, are encapsulated within a tiny, well understood mechanism. Alex Stepanov, designer of the STL http://stackoverflow.com/questions/826569/compellingexamplesofcustomcstlallocatorsStandard Template Library 26 Linked Lists The Standard Template Library has two variations on a linked list: template typename T, class Alloc = allocatorT class list; template typename T, class Alloc = allocatorT class forwardlist;Standard Template Library 27 Stacks, Queues, and Deques The Standard Template Library has all three classes: template typename T, class Alloc = allocatorT class deque; template typename T, class Container = dequeT class stack; template typename T, class Container = dequeT class queue;Standard Template Library 28 Weakly Ordered Containers Four containers are based on weak linear orderings: template typename Key, class Compare = lessKey, class Alloc = allocatorKey class set; template typename Key, class Compare = lessKey, class Alloc = allocatorKey class multiset;Standard Template Library 29 Weakly Ordered Containers Four containers are based on weak linear orderings: template typename Key, typename T, class Compare = lessKey, class Alloc = allocator pairconst Key, T class map; template typename Key, typename T, class Compare = lessKey, class Alloc = allocator pairconst Key, T class multimap;Standard Template Library 30 Weakly Ordered Containers What’s the difference – A simple container stores objects – An associative containers stores an object related to a key were accesses are performed using the key – A weak ordering is a linear ordering of equivalence classes • With linear orderings, either a b, a = b, or a b • With weak orderings, either a b, a b, or a b • That is, if a is neither less than or greater than b, it is equivalent to b • Example: people compared using their age in years – The container may store either • Only a single item per equivalence class, or • Multiple items per equivalence classStandard Template Library 31 Weakly Ordered Containers Which are which Items per equivalence class Simple Container Associative Container At most one set map An arbitrary number multiset multimap The class definitions: – The class definitions for set and multiset are the same – map and multimap are similar with: • Two additional member functions for access via the keys • Arguments for searching are based on keys • Returns are based on what is being associated with the keyStandard Template Library 32 setKey To make return types more standard, the C++ STL defines specific member types associated with each class: setKey::keytype Key setKey::valuetype Key setKey::reference Key setKey::constreference Key const setKey::pointer Key setKey::constpointer Key const setKey::iterator setKey::constiterator setKey::reverseiterator setKey::constreverseiterator setKey::sizetype sizet setKey::differencetype ptrdifftStandard Template Library 33 Priority Queues The Standard Template Library has a priority queue classes: template typename T, class Container = vectorT, class Compare = less typename Container::valuetype class priorityqueue;Standard Template Library 34 Hashed Containers For containers are based on hashing: template typename Key, class Hash = hashKey, class Pred = equaltoKey, class Alloc = allocatorKey class unorderedset; template typename Key, class Hash = hashKey, class Pred = equaltoKey, class Alloc = allocatorKey class unorderedmultiset;Standard Template Library 35 Hashed Containers For containers are based on hashing: template typename Key, typename T, class Hash = hashKey, class Pred = equaltoKey, class Alloc = allocator pairconst Key, T class unorderedset; template typename Key, typename T, class Hash = hashKey, class Pred = equaltoKey, class Alloc = allocator pairconst Key, T class unorderedmultiset;Standard Template Library 36 unorderedsetKey This is a simple container with unordered elements – Random access is Q(1) The elements stored are unique The user can specify the method of allocationStandard Template Library 37 unorderedsetKey To make return types more standard, the C++ STL defines specific member types associated with each class: keytype Key valuetype Key hasher hashKey keyequal equaltoKey reference Key constreference Key const pointer Key constpointer Key const iterator constiterator localiterator constlocaliterator allocatortype allocatevaluetype sizetype sizet differencetype ptrdifftStandard Template Library 38 unorderedsetKey Member functions include: – Constructors explicit unorderedset( sizetype, const hasher = hasher(), const keyequal = keyequal(), const allocatortype = allocatortype() ); unorderedset( unorderedset const ); unorderedset( unorderedset ); template class InputIterator unorderedset( InputIterator first, InputInterator last, ... ); unorderedset( initializerlistvaluetype, ... );Standard Template Library 39 unorderedsetKey Member functions include: – Assignment operator unorderedset operator=( unorderedset const ); unorderedset operator=( unorderedset ); unorderedset operator=( initializerlistvaluetype );Standard Template Library 40 unorderedsetKey Member functions include: – The four forward iterators begin end cbegin cend – Each has the various signatures: iterator begin() noexcept; constiterator begin() const noexcept; localiterator begin( sizetype ); constlocaliterator begin( sizetype ) const;Standard Template Library 41 unorderedsetKey Member functions include: – Capacity sizetype size() const noexcept; sizetype maxsize() const noexcept; bool empty() const noexcept;Standard Template Library 42 unorderedsetKey Member functions include: – Element lookup iterator find( const keytype ); constiterator find( const keytype ) const; sizetype count( const keytype ); pairiterator,iterator equalrange( const keytype ); pairconstiterator,constiterator equalrange( const keytype ) const;Standard Template Library 43 unorderedsetKey Member functions include: – Modifiers template class... Args iterator emplace( Args... ); template class... Args iterator emplacehint( constiterator, Args... ); pairiterator,bool insert( reference ); pairiterator,bool insert( valuetype ); pairiterator,bool insert( constiterator, reference ); pairiterator,bool insert( constiterator, valuetype );Standard Template Library 44 unorderedsetKey Member functions include: – Modifiers iterator erase( constiterator position ); iterator erase( reference ); iterator insert( constiterator, constiterator ); void clear() noexcept; void swap( unorderedset );Standard Template Library 45 unorderedsetKey Member functions include: – Allocator allocatortype getallocator() const noexcept; – Nonmember 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 comparisonStandard Template Library 46 Summary Data Structure STL Containers Array arrayT, N bitsetN vectorT, A vectorbool, A Linked lists forwardlistT, A listT, A Stacks, etc. stackT, D queueT, D dequeT, A Weakly ordered setK, C, A multisetK, C, A mapK, T, C, A multimapK, T, C, A Priority queue proporityqueueT, V Hash tables unorderedsetT, H, P, A unorderedmulitsetT, H, P, A unorderedmapK, T, H, P, A unorderedmulitmapK, T, H, P, AStandard Template Library 47 Summary We have looked at all the containers implemented in the STL – These cover all data structures looked at in this class – The most recent additions were singly linked lists and hash tablesStandard Template Library 48 References nd Donald E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, 2 Ed., Addison Wesley, 1998, §5.4, pp.248379. Wikipedia, https://en.wikipedia.org/wiki/Linkedlist http://stackoverflow.com/erroraspxerrorpath=/questions/8848363/rvaluereferencewithassignementoperator These slides are provided for the ECE 250 Algorithms and Data Structures course. The material in it reflects Douglas W. Harder’s best judgment in light of the information available to him at the time of preparation. Any reliance on these course slides by any party for any other purpose are the responsibility of such parties. Douglas W. Harder accepts no responsibility for damages, if any, suffered by any party as a result of decisions made or actions based on these course slides for any other purpose than that for which it was intended.
sharer
Presentations
Free
Document Information
Category:
Presentations
User Name:
Dr.SethPatton
User Type:
Teacher
Country:
United Kingdom
Uploaded Date:
22-07-2017