Programming in C++
Templates and Containers, the Standard Template Library, the vector class
06/11/2019 CE221 Part 6
Copyright By PowCoder代写 加微信 powcoder
Template Functions 1
Consider the following function.
void swap(int &a, int &b)
{ int temp = a;
b = temp; }
This can be used to swap the values in two variables of type int; if we wished to swap the values of two variables of type float or of type string we would have to write extra versions of the function with different argument types.
It is possible to avoid the need to write overloaded versions of functions by using a template function.
06/11/2019 CE221 Part 6
Template Functions 2
Here is a template version of the function from the previous slide:
template
b = temp; }
The template declaration says that T is a type parameter that can be instantiated with any type (it doesn’t have to be a class).
If we make a call swap(x, y) where x and y are variables of type float, the compiler will generate a version of the function with T instantiated to float.
06/11/2019 CE221 Part 6
Template Functions 3
The compiler will generate a separate instance of the template function for each type for which a call is made, so if we made calls swap(x, y) and swap(a, b) where x and y are of float and a and b are of int two separate versions of the function will be created. The machine code would hence be the same as if the programmer had written overloaded versions of the function.
Note that when matching argument types with template types the compiler will not attempt to perform any type conversions apart from implicit referencing and dereferencing, so the function on the previous slide cannot be called with two arguments of different types even if a conversion between the two types exists.
06/11/2019 CE221 Part 6
Template Functions 4
We could write a template function to print the contents of an array in a desired format:
template
void printArray(const T array[], int count) { for (int i = 0; i
void printPair(const S &s, const T &t)
{ cout << '<' << s << ', ' << t << '>‘;
Here S and T may be instantiated with the same type or with different types.
06/11/2019 CE221 Part 6
Template Classes 1
A template class is a class in which one or more of the members has a parameterised type, e.g.
The following class can store pairs of objects.
template
class Pair
{ private:
T t; public:
Pair(S a, T b): s(a), t(b) { };
S getFirst() const { return s; }; T getSecond() const { return t; }
06/11/2019 CE221 Part 6
Template Classes 2
A variable to hold an object of this class would be declared using the syntax
Pair
Note that if we write a template class in a file of its own we must place the complete function definitions in the header file. If the complete definitions of getFirst and getSecond were in a file called Pair.cpp the compiler when compiling this file would not know what instantiations of S and T are required by code in other files that uses the class and hence could not generate appropriate versions of the functions.
06/11/2019 CE221 Part 6
The Standard Template Library 1
The standard template library (STL) provides a number of template classes for various kinds of collections of objects, and algorithms that can be applied to these classes.
Each of these template classes is known as a container.
There are three sequence containers to store sequential data: vector, deque and list. The string class, which we have already encountered, is also a regarded as a sequence container (although it is not a template class).
In addition there are three container adaptors: stack, queue and priority_queue; these do not provide the full functionality of containers because the operations that may be performed on them are restricted (e.g. we are not allowed to access the middle of a stack).
06/11/2019 CE221 Part 6
The Standard Template Library 2
There are four associative containers to store non-sequential data with rapid searching: set, multiset, map and multimap.
The STL also contains two other non-template classes, bitset and valarray, that have some of the functionality of containers, but we will not use these in this module.
All of the container classes and container adaptors in the STL have a no-argument constructor to initialise a collection to be empty, a copy constructor to initialise a collection to contain copies of the objects in an existing collection, an assignment operator and a destructor. Most containers also have other constructors.
06/11/2019 CE221 Part 6
The Standard Template Library 3
All container classes and container adaptors have member functions called size and empty. These have no arguments; the former returns the number of elements in the collection and the latter returns a boolean result.
There is also a function max_size which returns the maximum possible size for the container. (This will be implementation- dependent.)
Each class has a swap function, which takes as an argument a reference to another container of the same type: after a call to c1.swap(c2), c1 will contain the previous contents of c2 and c2 will contain the previous contents of c1.
06/11/2019 CE221 Part 6
The Standard Template Library 4
Each class other than priority_queue also has the usual six comparison operators, although the behaviour of operators such as < depends on the container.
The sequence container and associative container classes have some additional member functions. (The adaptors do not have these.)
The clear function (which takes no argument and returns no result) resets the container to be empty.
There are also functions begin, end, rbegin and rend which can be used to obtain iterators to traverse through the elements of a collection and erase to remove one or more elements (using an iterator).
06/11/2019 CE221 Part 6
The vector Class 1
The vector template class provides an implementation of arrays with range-checking and should be used when we want to access elements by position. Programs that use this class should contain the line #include
The no-argument constructor will initialise a vector to have no contents and a default capacity. There is also a constructor with an argument of type int which initialises the vector to contain a fixed number of elements, each initialised to the same value – this value may be specified in a second argument which defaults to 0 (or the equivalent for any other type):
vector
vector
vector
// will contain 20 zeroes
// will contain 10 ‘x’s
06/11/2019
CE221 Part 6
The vector Class 2
Note that for a vector of class objects the use of the single- argument vector constructor will cause initialisation of the objects in the vector to be performed by the class’s no-argument constructor, so its use will be rejected by the compiler if no such constructor exists. In addition some other vector methods make use of the no-argument constructor so when writing a class that is expected to be used in collections a no-argument constructor should normally be provided.
06/11/2019 CE221 Part 6
The vector Class 3
It is possible to initialise the contents of a vector to be a copy of the contents of an array. This is done using a constructor with two arguments – the first is the address of the beginning of the array and the second is the address of the memory location immediately after the end of the array.
Using address arithmetic the appropriate value for the second argument is calculated by adding the length of the array to its start address; we can use a smaller second argument or a larger first argument to copy part of the array into the vector.
int a[] = { 1, 2, 3, 4, 5, 6, 7 };
vector
vector
vector
06/11/2019 CE221 Part 6
The vector Class 4
As with the string class, elements of a vector can be accessed using a member function at or via subscripting; only the at function provides range-checking so for safe access to the elements of a vector an expression such as v.at(n) should be used.
There are member functions front and back which return references to the first and last element; these can be used as the left-hand operand of an assignment statement:
v2.front() = 7;
cout << v2.back();
If the vector is empty a call to either of these two functions will throw an exception.
06/11/2019 CE221 Part 6
The vector Class 5
There are member functions push_back which will append an element to the end of the vector and pop_back which will remove the last element (or throw an exception if the vector is empty).
If a call to push_back results in the size of the vector becoming greater than the current capacity the capacity will be doubled – this involves dynamic allocation of a new larger block of memory and copying the existing elements into this block. Hence if we know that many calls to push_back will be made it can sometimes be more efficient to increase the capacity once using reserve before making any of the calls:
v.reserve(100); // increase capacity to 100
06/11/2019 CE221 Part 6
The vector Class 6
The reserve function can also be useful if the size of a large vector is about to reach its capacity and we know that we are going to add only a small number of new elements. We can prevent the automatic doubling of the capacity (which would result in a large amount of unused space being allocated) by reserving enough space for the extra elements, e.g.
v.reserve(v.size()+10);
06/11/2019 CE221 Part 6
The vector Class 7
It is possible to change the size of a vector using resize. If the new size is smaller than the original size the vector will be truncated; if it is greater multiple copies of an extra value will be appended to the end of the vector. The second argument, if provided, specifies this value; the default is 0 or its equivalent, (so we must provide the second argument for a vector of objects of a class without a no-argument constructor):
v2.resize(5);
// elements after v2[4] will be deleted
v1.resize(10);
// empty strings appended to vector // if its size is less than 10
v1.resize(15, "hello")
// 5 copies of "hello" appended to vector
06/11/2019 CE221 Part 6
The vector Class 8
It is possible to insert values into locations other than the end and remove values from arbitrary locations – performing either of these tasks requires the use of an iterator. These operations involve shifting of the existing elements to the right of the insertion or deletion point and are hence rather inefficient; hence if they are to be performed frequently it would be more appropriate to use a different container class such as list or deque.
06/11/2019 CE221 Part 6
Range-based For Loops 1
Range-based for loops similar to the enhanced for loops of Java were introduced in C++11. The syntax is
for (T i: range) statement
The range may be an array or a container (including a string), or any other class that has been written that supports iterators. The statement may of course be a sequence inside { and } .
We could output the contents of a vector one item per line using
for (int i: v2) cout << i << endl;
It is important to note that unless we specify explicitly that we wish to use a reference the variable will hold a copy of the item in the array or container. If we wish to use such a loop to modify the contents of the array or container we must use a reference variable.
06/11/2019 CE221 Part 6
Range-based For Loops 2
To convert all the characters in the vector v1 to upper-case we would use
for (char &c: v1) c = toupper(c);
To output details of all students in a vector of students (assuming a << operator has been written for the Student class) we could use a loop such as
for (Student s: studs) cout << s << endl;
However this will result in copies of the student objects being made, so it would be more efficient to use
for (Student &s: studs) cout << s << endl;
for (const Student &s: studs) cout << s << endl;
06/11/2019 CE221 Part 6
Range-based For Loops 3
It is common practice to use auto in range-based for loops since the variable type will almost invariably be the type of the data items in the range:
for (auto &s: studs) cout << s << endl;
There will be rare occasions when it is useful to use a variable whose type differs from the type of the data items when a conversion is available. One example could be using a string variable with a vector of C-strings to allow string member functions to be used:
vector
if (s.find(‘s’)!=string::npos)
cout << s << endl;
06/11/2019 CE221 Part 6
Range-based For Loops 4
Note that range-based for loops are generally not useful if we need to know the position in the range of the item being processed, since we would need to maintain a counter inside the loop; a normal counter-controlled for loop would usually be more appropriate. Consider an attempt to output the contents of a vector with position prefixes:
int i = 0;
for (int a: v3)
{ cout << i << ':' << a << endl;
The traditional for loop would be more concise:
for (int i = 0; i