PowerPoint PresentationSlide 2More About Container IteratorsProperties of Iterator IntervalsThe forward_list ContainerThe vector ContainerThe list ContainerThe deque ContainerSlide 9Slide 10CSE 332: C++ Sequential ContainersBasic C++ Sequential Container Features•Contain elements of a parameterized type–Ordered (non-overlapping) ranges of elements–A location can’t be within more than one container•Adding and copying elements is by value–A container owns the elements in it•Container’s destructor destroys what it contains•Provide interfaces to contained values–Functions to add/remove values, e.g., push_back–May provide other container-specific operations, e.g. some have operator[] for random access–Obeys “principle of least surprise” (no []for list)CSE 332: C++ Sequential ContainersContainers Provide Their Own Iterators•Containers declare various associated iterator types// try to use const_iterators whenever you canvector<int>::iterator i; // iterator over non-constvector<int>::const_iterator ci; // iterator over const•They also give iterator accessor/factory methods for beginning of and just past the end of container range// v is previously declared as vector<int> v;auto ci = v.cbegin(); // use a const_iteratorwhile (ci != v.cend()) { // compare to const_iterator cout << *ci << endl; // does not modify v ++ci;}CSE 332: C++ Sequential ContainersMore About Container Iterators•Iterators generalize different uses of pointers–Most importantly, define left-inclusive intervals over the ranges of elements in a container [begin, end)•Interface between algorithms and data structures–Algorithm manipulates iterators, not containers•An iterator’s value can represent 3 kinds of states:–dereferencable (points to a valid location in a range)–past the end (points just past last valid location in a range)–singular (points to nothing)–What’s an example of a pointer in each of these states?•Can construct, compare, copy, and assign iterators so that native and library types can inter-operateCSE 332: C++ Sequential ContainersProperties of Iterator Intervals•valid intervals can be traversed safely with an iterator•An empty range [p,p) is valid•If [first, last) is valid and non-empty, then [first+1, last) is also valid–Proof: iterative induction on the interval•If[first, last) is valid –and position mid is reachable from first –and last is reachable from mid–then [first, mid) and [mid, last) are also valid•If [first, mid) and [mid, last) are valid, then [first, last) is valid–Proof: divide and conquer induction on the intervalCSE 332: C++ Sequential ContainersThe forward_list Container•Implements a singly linked list of elements–Elements not have to be contiguous in memory–No random access, can only iterate forward–Can only grow at front of forward_list•Insertion at front is constant time, but many other operations are linear in number of elements•Insertion into the middle of the list is constant time, but finding a position within the list is linear timeCSE 332: C++ Sequential ContainersThe vector Container•Implements a dynamically sized array of elements–Elements are (almost certainly) contiguous in memory–Random access and can iterate forward or backward–Can only grow at back of vector (reallocates as needed)•Many operations are constant time, such as whether or not the container is empty, how many elements it currently holds, etc.•Pushing at the back is “amortized” constant time (occasional reallocations averaged over all pushes)CSE 332: C++ Sequential ContainersThe list Container•Implements a doubly linked list of elements–Elements do not have to be contiguous in memory–No random access, but can iterate forward or backward–Can grow at front or back of listCSE 332: C++ Sequential ContainersThe deque Container•Implements a double-ended queue of elements–Elements do not have to be contiguous in memory–But must be accessible in constant time (random access)–Still can iterate forward or backward–Still can grow at front or back of dequeCSE 332: C++ Sequential ContainersRules of Thumb for Sequential Containers•Use a vector most of the time (if you can)–Often balances simplicity, efficiency, flexibility well–But, use a list (or maybe a forward_list) instead if you need to insert in the middle of a container–Or use a deque to insert at both ends•Watch out for when iterators may be invalidated•Use specialized containers only when needed–E.g., an array if you need a fixed sized container–E.g., a string if you’re only working with characters–E.g., a stack or queue container adapter if you want to restrict the container interface that can be usedCSE 332: C++ Sequential ContainersAn Advanced Topic: Emplacement•Insertion may involve extra overhead for copyingvector<string> courses;courses.push_back (“cse332”); // 2 constructor calls•If the compiler and STL library you are using supports emplacement, it may be more efficient (if that matters)vector<string> courses;courses.emplace_back (“cse332”); // 1 constructor call // due to