Lecture 7: The STL
Prof. Michael [email protected]
1
TheStandardTemplateLibrary
A collection of commonly used data structuresMade up of 3 thingsContainersAlgorithmsIteratorsDefinitely used in project 2
Containers
Acontaineris a holder object that stores a collection of other objects (its elements). They are implemented as class templates, which allows a great flexibility in the types supported as elements.Thecontainermanages the storage space for its elements and provides member functions to access them, either directly or through iterators (reference objects with similar properties to pointers).
From: http://www.cplusplus.com/reference/stl/
Sequence Containers
All sequential containers is that the elements can be accessed sequentiallyThey reside in namespacestdSome only in C++ 11 (but not C++ 98)
From: http://www.cplusplus.com/reference/stl/
Container Adaptors
Container adaptors are not full container classes, but classes that provide a specific interface relying on an object of one of the container classes (such as deque or list) to handle the elements.
From: http://www.cplusplus.com/reference/stl/
Priority queues are a type of container adaptors, specifically designed such that its first element is always the greatest of the elements it contains
Associative Containers
An abstract data type composed of a collection of (key, value) pairsFor sets and maps, each possible key appears at most once in the collection
From: http://www.cplusplus.com/reference/stl/
Vectors
Dynamically sizedElements stored in orderRandom access allowedUse [] or .at(i)at(i) will throw an exception if index out of bounds
Vector example
#include <vector>#include <iostream>using namespacestd;intmain() {vector<int> numbers(3);numbers.push_back(5);numbers.push_back(10);numbers.push_back(15);cout<<numbers.front() <<endl;// 15cout<<numbers.back() <<endl;// 5cout<< numbers[1] <<endl;// 10cout<<numbers.at(1) <<endl;// 10}
Stacks
Sequential data structure (LIFO)size()empty()push(e)pop()top()
Stack example
#include <stack>#include <iostream>using namespacestd;intmain() {stack<int> numbers;numbers.push(10);numbers.push(7);numbers.push(4);cout<<numbers.size() <<endl;// 3cout<<numbers.empty() <<endl;// falsecout<<numbers.top() <<endl;// 4numbers.pop();cout<<numbers.top() <<endl;// 7}
Queue
Sequential data structure (FIFO)size()empty()push(e)pop()front()back()
Queue example
#include <queue>#include <iostream>using namespacestd;intmain() {queue<int> numbers;numbers.push(10);numbers.push(7);numbers.push(4);cout<<numbers.size() <<endl;// 3cout<<numbers.empty() <<endl;// falsecout<<numbers.front() <<endl;// 10numbers.pop();cout<<numbers.front() <<endl;// 7}
Lists
Doubly Linked Listsize()empty()front()back()push_front()push_back()pop_front()pop_back()
List example
#include <iostream>#include <list>using namespacestd;intmain() {list<int> numbers;numbers.push_front(6);// 6numbers.push_front(3);// 3 6numbers.push_back(1);// 3 6 1cout<<numbers.size() <<endl;// 3cout<<numbers.empty() <<endl;// falsecout<<numbers.front() <<endl;// 3cout<<numbers.back() <<endl;// 1numbers.pop_back();cout<<numbers.back() <<endl;// 6}
Iterators
Iterators
ProblemNot all STL classes provide random accessHow do we do “for each element in X”?SolutionIterators“Special” pointers“Iterate” through each item in the collectionAlso: encapsulationUser shouldn’t need to knowhowit works
About Iterators
Allows the user to access elements in a data structure using a familiar interface, regardless of the internal details of the data structureAn iterator should be able to:Move to the beginning (first element)Advance to the next elementReturn the value referred toCheck to see if it is at the end
Kinds of Iterators
Forward iterators:Using ++ works on iteratorBidirectional iterators:Both ++ and -- work on iteratorRandom-access iterators:Using ++, --, and random access all workwith iteratorThese are "kinds" of iterators, not types!
Iterators
Essential operationsbegin()Returns an iterator to first item in collectionend()Returns an iterator ONE BEYOND the last item in collectionWhy does it do this?If the collection is empty, begin() == end()
Constant and Mutable Iterators
Behavior of the dereferencing operator dictates if an iterator is constant or mutableConstant iterator:Cannot edit contents of container using iteratorMutable iterator:Can change corresponding element in container
Mutable Iterators
Mutable iterator:*p can be assigned valueChanges corresponding element in containeri.e.: *p returns anlvalue*p can be on the left hand side of the assignment operator(and the right hand side)
Vector Example
Here’s a very basic example of using an iterator to move through a vector:vector<int> v; // fill up v with data...for (vector<int>::iterator it =v.begin();it !=v.end(); ++it) {cout<< *it <<endl;}This basic example should work regardless of the container type!
Constant Iterators
Constant iterator:* produces read-only version of elementCan use *p to assign to variable or output,but cannot change element in containere.g., *p = <anything>; is illegal*p can only be on the right hand side of the assignment operator
Vector Example
Here’s a a constant iterator moving through a vectorvector<int> v; // fill up v with data...for (vector<int>::const_iteratorit =v.begin());it !=v.end(); ++it) {cout<< *it <<endl;}
Iterators - Overloaded Operators
*Dereferences the iterator++Moves forward to next element--Moves backward to previous element==True if two iteratorspointtosameelement!=True if two iteratorspointtodifferentelements=Assignment, makes two iteratorspoint to same element
Algorithms
Algorithms
The STL provides a number of algorithms that can be used on any container#include <algorithmName>
One example
sort(p, q)p,qare iterators of the container typeSort the elements in ascending order from p to qSeveral more listed in Chapter 6 of your book
0
Embed
Upload