Standard Template Library
Transcript: STL Introduction Standard Template Library Designed By Alex Stepanov WHAT? What is the STL? The Standard Template Library (STL) is a software library for the C++ programming language. A library of powerful, reusable, adaptable, generic classes and functions Implemented using C++ templates Implements common data structures and algorithms WHY? Why use the STL? Assortment of commonly used containers Tried and tested Consistent,fast , and type-safe Extensible ELEMENT Elements of the STL Containers Algorithms Iterators Functors Containers Collections of objects or primitive types Containers Sequence Containers Sequence Containers Vector List Deque Forward_list Container Adaptors Container Adaptors ㄑQueue Priority_Queue Stack Associative Containers Associative Containers ㄍSet Multiset Map Multimap Algorithms Functions for processing sequences of elements from containers Algorithms STL algorithms work on sequences of container elements provided to them by an iterator. STL has many common and useful algorithms Too many to describe in this section http://en.cppreference.com/w/cpp/algorithm Many algorithms require extra information in order to do their work Functors(function objects) Function pointers Lambda expressions(C++ 11) Algorithms and iterators. #include <algorithm> Different containers support different types of iterators Determines the types of algorithms supported All STL algorithms expect iterators as arguments Determines the sequence obtained from the container Iterator invalidation Iterators point to container elements It’s possible iterators become invalid during processing Suppose we are iterating over a vector of 10 elements And we clear() the vector while iterating? What happens? Undefined behavior – our iterators are pointing to invalid locations Example algorithm – find with primitive types The find algorithm tries to locate the first occurrence of an element in a container. Lots of variations. Returns an iterator pointing to the located element or end() std::vector<int> vec{1, 2, 3}; auto loc = std::find(vec.begin(), vec.end(), 3); if(loc != vec.end()) // found it! std::cout << *loc << std::endl; // 3 Example algorithm – for_each for_each algorithm applies a function to each element in the iterator sequence. Function must be provided to the algorithm as: Functor (function object) Functioin pointer Lambda expression(C++11) Let’s square each element for_each – using a functor struct Square_Functor{ void operator()(int x) // overload () operator std::cout << x * x << “ “; } }; square_Functor square; std::vector<int> vec {1, 2, 3, 4}; std::for_each(vec.begin(), vec.end(), square); // 1 4 9 16 for_each – using a function pointer void square(int x){ // function std::cout << x * x << “ “; } std::vector<int> vec{1, 2, 3, 4}; std::for_each(vec.begin(), vec.end(), square); // 1 4 9 16 Iterators Generate sequences of element from containers Iterators Allows abstracting an arbitrary container as a sequence of elements. They are objects that work like pointers by design. Most container classes can be traversed with iterators. Declaring iterators Iterators must be declared based on the container type they will iterate over container_type::iterator_type iterator_name; std::vector<int>::iterator it1; std::list<std::string>::iterator it2; std::map<std::string, std::string>::iterator it3; std::set<char>::iterator it4; Iterator begin and end methods. Declaring iterators. Initializing iterators. std::vector<int> vec{1, 2, 3}; std::vector<int>::iterator it = vec.begin(); or auto it = vec.begin(); Using iterators – std::vector std::vector<int> vec{1, 2, 3}; for(auto it = vec.begin(); it != vec.end(); it++){ std::cout << *it << “ “; } // 1 2 3 This is how the range-based for loop works Using iterators – std::set std::set<char> suits{‘C’, ‘H’, ‘S’, ‘D’}; auto it = suits.begin(); while(it != suits.end()){ std::cout << *it << “ “ << std::end; ++it; } // C H S D Reverse iterators Works in reverse Last elements is the first and first is the last ++moves backward, -- moves forward std::vector<int> vec{1, 2, 3}; std::vector<int>::reverse_iterator it = vec.begin(); while(it != vec.end()){ std::cout << *it << “ “; ++it; }// 3 2 1 Other iterators begin() and end() iterator cbegin() and cend() const_iterator rbegin() and rend() reverse_iterator crbegin() and crend() const_reverse_iterator