Introduction to STL containers
CSinParallel Project
Note: This
reading refers to topics that we will not pursue in homework, but which may
arise in general C++ coding. Such topics will be marked(Extra).
●
The C++ Standard Template Library(STL) is a
software library of algorithms, data structures, and other features that can be
used with any pre-defined C++ type and with user-defined types (that provide
members such as a copy constructor and an assignment operator).
●
The STL uses a C++ feature called the template
to substitute types throughout a class or function definition, which enables a
programmer to avoid rewriting definitions that differ in the type being used.
●
For example, our IntArray class for homework provides
a class structure around an array of int, with error checking, default
initialization for array elements, whole-array assignment, etc. To define a
class LongArray or FloatArray, we would only need to replace the type name int
by a different type name long or float, etc. Templates make it possible to
define a class Array<T> in which a type name T is used thrroughout the
definition of that class, so that the notation Array<int> would specify a
class that behaves just like IntArray, Array<float> would specify
FloatArray, etc. Here, the angle brackets <...> are the syntax for
invoking a template, and they enclose a type name to use throughout a
definition.
●
A programmer can define her/his own templated classes.
For example, here is a complete program with a definition of a templated
structPair<T> that represents an group of two elements of the same type,
together with an example use of that template.
●
#include <iostream>
using namespace std;
template <class
T>
struct Pair {
T x;
T y;
Pair(T
val1, T val2) { x = val1; y = val2;
}
};
int main() {
Pair<float> p(3.14, -1.0);
cout
<< p.x << ", " << p.y << endl;
}
●
The STL containers are templated classes
defined in the STL that are designed to hold objects in some relationship.
Examples::
○
The array classes we have implemented in homework are
examples of containers, although STL's array-like container vector<T> has
some added useful features such as an ability to resize incrementally that our
array classes did not include.
○
Another STL container is called a queue<T>, and
contains a linear list of elements that are added at one end and removed at
another, comparable to a check-out line of customers at a grocery store. Unlike
a vector, the elements of a queue do not necessarily appear consecutively in
memory.
○
(Extra) Another example is the
map<K,T> container, which includes an operator[] that accepts
"indices" of a type K (not necessarily an integer type) and
associates values of type T with those "index" values.
●
This is not a complete list of STL containers, but
illustrates some commonly used ones. See www.cplusplus.com/reference/stl/ for
documentation of all STL containers
●
STL's vector<T> is a templated class that
behaves like an "elastic array," in that its size can be changed
incrementally. For example, consider the following example program:
●
#include <iostream>
using namespace std;
#include
<vector>
int main() {
vector<int> vec(4);
vec[1] =
11;
vec.at(2)
= 22;
vec.push_back(33);
for (int i
= 0; i < vec.size(); i++)
cout << vec.at(i) << endl;
}
○
The preprocessor directive
○
#include <vector>
○
tells the compiler what it needs to know to compile
with vectors
○
The first statement is a variable definition that
defines vec to be a vector of four integers. Each integer location is
initialized at 0 by default.
○
The third statement uses the at() method of vector,
and behaves exactly like operator[] except for a different style of error
handling (at throws "exceptions" instead of crashing the program).
○
The call to vector's push_back() method appends a new element
33 to the end of vec
●
The resulting vector vec contains five int elements:
0, 11, 22, 0, and 33. Those values will be printed by the final loop.
●
A similar exercise could have been programmed with
float, Dog, or another type.
●
(Extra) In the "exception" style
of error handling used by methods such as at(), a runtime error (i.e., while
the program is running, such as index out of bounds for a vector object)
creates an object called an exception that includes information about
that error. We say that the error condition throws the exception object.
C++ provides an optional try/catch feature for capturing thrown exceptions and
taking action on them; otherwise, throwing an exception causes a program to
crash.
●
The vector method push_back() enables a programmer to
extend the length of a vector object by one element, as shown above. That new
element is added at the "back" or highest-indexed end of that vector.
●
Another vector method pop_back() enables a programmer
to delete the last element of a vector, thus decreasing its length by 1. The
methodpop_back() requires no argument and returns no value.
●
The vector index operator [ ] and the method at() both
provide immediate access to any element in a vector.
●
The method size() returns the number of elements
currently in a vector object.
●
The method back() returns the last element of a
non-empty vector. Thus, vec.back() returns the same value as vec[vec.size()-1]
orvec.at(vec.size()-1) .
●
The vector container provides methods for inserting or
removing values at locations other than the back of a vector object, called
insert()and erase(). However, these methods are not as efficient as push_back()
and pop_back(). This is because vector elements are stored consecutively in
memory, so inserting or removing an element at a position other than the back
requires copying all element values from that position through the back value.
●
(Extra) Note that the methods insert()
and erase() require iterator objects to specify position within a vector
object. An iterator is an object that contains a pointer and has methods
for certain pointer operations, such as a method next() for advancing to the
next element in an array or vector.
●
See www.cplusplus.com/reference/stl/vector for a
reference on vectors.
●
STL's queue<T> is a templated class that is a FIFO
(first-in first-out) container. This means that it is capable of holding an
indeterminate number of elements of a particular type, organized in an ordered
list, with each element added at one end of the list (the back) and
removed at the other end (the front).
●
Whereas STL's vector templated class has many methods,
a queue has only six specified methods (seewww.cplusplus.com/reference/stl/queue:
○
push(), which adds an element at the end of a queue,
○
pop(), which removes an element from the beginning of
a queue,
○
front(), which returns the element at the front of a
non-empty queue (next to be popped),
○
back(), which returns the element at the back of a
non-empty queue (most recent to be pushed),
○
empty(), which returns Boolean True if there are no
elements in a queue and False otherwise, and
○
size(), which returns the number of elements currently
in a queue.
●
Here is a code example of using a queue.
●
#include <iostream>
using namespace std;
#include <queue>
int main() {
queue<float> q;
q.push(1.23);
q.push(4.56);
q.push(7.89);
while
(!q.empty()) {
cout << q.front() << endl;
q.pop();
}
}
●
The output from this code should be the numbers 1.23 then
4.56 then 7.89, one per line.
●
An STL vector could be used in a situation where a queue
would be appropriate (e.g., simulating a process comparable to a grocery-store checkout
line), using the vector methods push_back(), front(), and erase() (to remove
the front element). But a queue can be implemented more efficiently than a
vector for this purpose, avoiding the copying of elements that are needed for
vector's erase() method.
●
(Extra) The underlying data structure for a
queue can be specified when that queue is created, using a second template
parameter.
●
On the other hand, a queue provides no index or at()
operator for accessing an element other than the front or back elements. The
ability to access arbitrary element locations (e.g., via indices) is called random
access, and if random access is needed, a vector may be more desirable than
a queue.
●
As with vector, the templated container class queue
can accept a user-defined type for its elements. Thus
●
queue<Dog> , queue<const Dog*> ,
●
and other types may be used.
rab@stolaf.edu, April
27, 2011