Template
- Polymorphism is the ability of the same code to operate on different types. This ability to operate on multiple types reduces code duplication by allowing the same piece of code to be reused across the different types it can operate on.
- Polymorphism comes in a variety of forms. What we are interested in at the moment is parametric polymorphism, meaning that we can write our code so that it is parameterized over what type it operates on.
-That is, we want to declare a type parameter T and replace int with T in the above code.
-Then, when we want to call the function, we can specify the type for T and get the function we desire. C++ provides parametric polymorphism through templates.
Templated Functions
- We can write a templated function by using the keyword template followed by the template parameters in angle brackets (<>).
- Unlike function parameters, template parameters may be types, which are specified with typename where the type of the parameter would typically go.
- class and typename is preferable because it can avoid confusion. Non-class types may be used, even if the parameter is declared with class.
find the largest element function:
template<typename T>
T * arrMax (T * array, size_t n) {
if (n == 0) {
return NULL;
}
T * ans = &array[0];
for (size_t i = 1; i < n; i++) {
if (array[i] > *ans) {
ans = &array[i];
}
}
return ans;
}
- We can put T anywhere we want to use any other types.
- It can take multiple parameters, and their parameters may be normal types such as int.
e.g.
template<typename T, typename S, int N>
Instantiating Templated Functions
- We can think of a template as taking parameters and creating a function.
- The template function itself is not actually a function. Instead, we must instantiate the template - giving its parameters to create an actual function.
-Even though there's similarities between calling a function and instantiating a template, the two have different terminology as well as other important distinctions.
- To instantiate a template, we write the name of the templated function, followed by the arguments we wish to pass inside of angle bracket.
e.g.
int * m1 = arrMax(myIntArray, nIntElements);
string * m2 = arrMax<string>(myStringArray, nStringElements);
int x = someFunction<int *, double, 42> (m1, 3.14);
- Whenever we instantiate a template, the C++ compiler creates a template specialization - a "normal" function derived from a template for particular values of its parameters.
- It the compiler needs to create the specialization, it does so by taking the template definition and replacing the template parameters with the actual arguments passed in the instantiation.
Templated Classes
- C++ not only allows a programmer to write template functions, but allows templated classes as well.
- template classes has template parameters, which can be either types or values.
- The scope of the template parameter is the entire class declaration.
e.g.
template<typename T>
class Array {
private:
T * data;
size_t size;
public:
Array() : data(NULL), size(0) {}
Array(size_t n) : data(new T[n]()), size(n) {}
Array(const Array & rhs) : data(NULL), size(rhs.size) {
(*this) = rhs;
}
~Array() {
delete[]data;
}
Array & operator = (const Array & rhs) {
if (this != &rhs) {
T * temp = new T[rhs.size];
for (int i = 0; i < rhs.size; i++) {
temp[i] = rhs.data[i];
}
delete[] data;
data = temp;
size = rhs.size;
}
return *this;
}
T & operator[] (unsigned ind) const {
return data[ind];
}
size_t getSize() const {
return size;
}
};
- As with functions, whenever we instantiate the templated class, the compiler creates a specialization of that template.
- e.g. We can instantiate the template for ints by writing Array<int> and for string by writing Array<std::string>. The specialization created by these two instantiations are different classes.
- The following code is illegal:
Array<int> intArray(4);
Array<std::string> stringArray(intArray); //illegal
Templates as Template Parameters
- Templates can also be another template's parameters.
e.g.
template<typename T, template<typename> class Container>
class smoething {
private:
Container<T> data;
};
- After writing Array template we wrote above, we could instantiate this templated class like this:
something<int, Array>x;
- This instantiation will create a specialization whose data field is an Array<int>.
- If we always want to use an Array to store our data, we can just write that in our class. This is just an example of abstraction - we decouple the specific implementation for how the Container stores its data from the interface required to do so.
Template Rules
- There are several rules related to the workings of template.
Template Definitions Must Be "Visible" at instantiations
- The actual definition of the templated function or class must be "visible" to the compiler at the point where the template is instantiated. We cannot just put the declaration in a .h file and instantiate it the .cpp file.
- The reason for that is: a templated function (or class) is not actually a function, but a recipe to create the specialization. When the compiler finds the instantiation of the template, it needs the definition in order to create the actual specialization that is actual concrete code that can be placed in an object file.
- So we should write both entire templated classes and functions in their header files.
Template Arguments Must Be Compile-Time Constants
- The arguments that are passed to a template must be compile-time constants - they may be an expression, but the compiler must be able to directly evaluate that expression to a constant.
e.g.
for (int i = 0; i < 4; i++) {
x += f<i>(x); //illegal: because i is not a compile-time constant
}
but we can write the following legal words
x += f<0>(x);
x += f<1>(x);
x += f<2>(x);
x += f<3>(x);
The reason for this rule is that the compiler must create a specialization for the argument values given. When it sees f<0>, it create a version 0 of f and then compile the code.
- If the compiler cannot figure out the exact value of the parameter easily, then it has no idea what specializations of the template it should create and thus cannot compile the code.
Template are only type checked when specialized
!!! important
- In C++, a template is only type checked when it is specialized. i.e.we can write a template that can only legally be instantiated with some types, but not others.
- e.g. in previous example,
if (array[i] > *ans) {}
requires that T to have > operator defined to compare two Ts and returns a bool.
- The first time the function encounters an instantiation of the templated function with a particular set of arguments, it specializes the function.
- For a class, only the specialization occurs in parts. Whenever an instance of the class is created, the compiler specializes the part of the class definition that is required to make the object's in-memory representation - the fields, as well as virtual methods.
The normal method do not actually affect the in-memory representation of an instance of the object, as they are not placed in the object but rather the code segment.
- The non-virtual methods of a templated class are only specialized when the corresponding method is used.
e.g. We have the following:
template<typename T>
class Something {
T data;
public:
bool operator == (const Something & rhs) const{
return data == rhs.data;
}
bool operator < (const Something & rhs) const {
return data < rhs.data;
}
}
- If we instantiate the Something template on a type (T) that admits equality, it is legal.
If we only have the following:
template<typename T>
class Something {
T data;
public:
bool operator == (const Something & rhs) const{
return data == rhs.data;
}
}
and we want to compare two Something<T>s, then the compiler will specialize the < operator for Something, try to type check it, and produce an error as the < operator is not defined on T.
Multiple Close Brackets Must Be Separated by Whitespace
- If we want to instantiate the std::vector template with a std::pair with an int and a std::string, we might do the following:
std::vector<std::pair<int, std::string> > myVector
- The space between the two >s is required. The following is illegal:
std::vector<std::pair<int, std::string>> myVector
Dependent Type Names Require Keyword typename
- Different expressions can have different meanings.
- In C++ compilation, the compiler can typically simply check to see if x names a type or not. However, if T is a template parameter that names a type, then the compiler has a difficult time determining if T::x names a type or a variable.
- Something<T>::x is difficult to figure out.
- We call x a dependent name, as its interpretation depends on what T is.
- Whenever we use a dependent name for a type, we need to explicitly tell the compiler that it names a type by placing the typename keyword before the name of the type. e.g.
template<typename T>
class Something {
private:
typename T::t oneField;
typename anotherTemplate<T>::x twoField;
public:
typename T::t someFunction() {
typename T::t someVar;
}
}
- For dependent type: declaring the two fields, the return type of the function, the parameter type of the function, and the local variable in the function. Each of these requires us to explicitly add the typename keyword, as shown in the example.
- If a dependent name has a templated class or function inside of it, and the compiler must explicitly be told that name refers to a template via the template keyword to disambiguate the < that encloses the template's arguments from the less-than operator.
You Can Provide an Explicit Specialization
- We can explicitly write a specialization for a template - providing specific behavior for particular values of the template arguments.
- Explicit specialization is performed to provide a more efficient implementation of the exact same behavior as the "primary template". There's no rule to enforce this behavior.
- Explicit specializations may either be:
1) partial: we only specialize with the respect to some of the parameters, leaving the resulting specialization parameterized over the other
2) complete: specialize all of the parameters
- If we use partial specializations, we should be aware of the rules that C++ uses to match template instantiations to the partial specializations we have written.
Template Parameters for Functions (But Not Classes) May Be Inferred
- When we use a templated function, we can omit the angle brackets and template arguments in cases where the compiler can infer them. i.e. if the compiler can guess what to use based on other information, such as the types of the parameters to the function.
- However, we recommend against this practice. It's much better to be explicit and make sure we and the compiler both agree on what types are being used.
- Being explicit also helps with readability - someone else examining your code knows exactly what's happening. Meanwhile, the compiler may infer a perfectly legal type that we did not intend.
- For templated classes, the arguments must always be explicitly specified. The compiler will never try to infer them.
The Standard Template Library (STL)
- C++ has a Standard Template Library, which provides a variety of useful templated classes and functions.
The std::vector Templated Class
std::vector<typename T>
- Technically, the vector template has a second parameter, but its default value suffices for everything we place to use vectors as well as for most common purposes.
- A vector is similar to an array in that it stores elements of some other type - namely, the type that is its template parameter T.
- Like an array. the vector 's elements may be accessed with the [] operator. We should:
#include <vector>
if we want to sue this class
- The size of a vector can be changed via methods such as push_back, insert, pop_back and erase.
- push_back means we add an element to the end of the vector.
- insert means we insert an element at an arbitrary.
- pop_back means we reduce the size of the vector by removing the last elements from it.
- erase removes an arbitrary element.
- vector provide a copy constructor, assignment constructor, destructor and size method
- vector provide overloaded operators to compare two vectors, == checks if the two vectors are the same size and, if so, compares each element in its left-hand operand to the corresponding element in the right-hand operand for equality. Of course, this comparison requires the == operator to be defined on Ts, which it uses to compare the individual elements to each other.
- == operator for vectors is a great example of the template rule. Type checking for templates only happens on the specializations that are actually used.
- The STL can define the vector template despite the fact that not all types have == defined on them. We can then instantiate the vector with any type. For any of these types (T) that do define ==, we can compare vector<T>s for equality. But we cannot compare vectors for equality if the type of objectts they hold does not have == defined on it.
- vector have < operator, which orders two vectors lexicographically.
The std::pair Templated Class
- For this templated class, it combines two objects with type T1, and T2 into a single object. We can then access these two objects by the method first and second.
- It's quite useful because the return value can only be one while sometimes we may want to return two values, or the values in the vector.
Iterators
- While we have a loop, we might have inefficiency accessing the element inside. We may want to expose the internal representation, but it is against the principles of abstraction.
- The approach C++ takes to resolve the tension is to offer an abstraction called an iterator.
- An iterator is a class that encapsulates the state of the internal traversal while providing an implementation-independent interface to external code.
- In other words, the iterator tracks where the traversal is in whatever fashion is efficient for the data structure it belongs to but gives a simple interface to other code. (And iterator is a class inside of the data structure - thus it is file to know the internal representation details)
e.g.
std::vector<int>::iterator it = meVector.begin();
while (it != myVector.end()) {
std::cout << *it << "\n";
++it;
}
- The begin() function returns an iterator positioned at the start of the data structure.
- ++it and it++ are functionally equivalent, but ++it is more efficient due to the difference in the semantics of the operators.
- The postfix increment operator (i++) evaluates to the value before the increment was performed, while the prefix increment operator (++it) evaluates to the value after the increment is performed.
- Although the distinct seems minor, the postfix increment require the operator to make a copy of the original object, perform the increment and then return the copy of the object.
- In general, we should use the prefix increment operator whenever the increment is on an object type to avoid these unnecessary copies and destructions.
- We can write a template for it:
template<typename T>
void printElement (T & container) {
typename T::iterator it = container.begin();
while (it != container.end()) {
std::cout << *it << "\n";
++it;
}
}
- Here we cannot use const T & container because begin() returns an iterator that allows the elements it references to be modified, so we cannot call it on a const object.
- But we can use the const_iterator to make it const:
template<typename T>
void printElement (const T & container) {
typename T::const_iterator it = container.begin();
while (it != container.end()) {
std::cout << *it << "\n";
++it;
}
}
- Here, it's just begin() is overloaded by the following two signatures:
iterator begin();
const_iterator begin() const;
- These two are different in types of their this argument and thus are legal overloading. The second has this as a pointer to a const object.
- C++ provides a variety of kinds of iterators, which vary in how they can traverse their data structure:
-forward iterator can only move forward ++
-backward iterators can only move backward --
- bidirectional and random access iterators can go both forward and backward
- random access iterators can move forwards or backwards by more than one element at a time += -+
- Whenever a modification occurs, an iterator may be invalidated by that modification. But whether an iterator will be affected depends on different container. e.g.
-vector, all iterators and references before the point of insertion are unaffected, unless the new container size is greater than previous capacity.
-list: all iterators and references unaffected.
- Use of an invalidated iterator is incorrect. It's an error. And it will crash.
Algorithms from the STL
- When using algorithms provided by STL, we should
#include <algorithm>
- The simplest of these are the min and max algorithms.
- There are two versions of these templates. The first simply compares the two parameters with the < operator while the second allows for a custom comparison function to determine the ordering.
- The second version is implemented by having a second template parameter that specifies a class with an overloaded () operator. This is called function call operator.
e.g.
class OrderIgnoreCase {
public:
bool operator() (const std::string & s1, const std::string & s2) const {
for (size_t i = 0; i < s1.size() && i < s2.size(); i++) {
char c1 = tolower(s1[i]);
char c2 = tolower(s2[i]);
if (c1 != c2) {
return c1 < c2;
}
}
return s1.size() < s2.size();
}
}
- After writing this overloaded() operator , we could then use this class to with the min algorithm to find the minimum of two strings and ignore case:
std::min<std::string, OrderIgnoreCase>(str1, str2, OrderIgnoreCase());
summary& understanding after reading <<All of Programming>> Chapter 17
Comments
Post a Comment