Chapter 16 template and generic programming

 

OOP: it can handle situations where the type is unknown before the program runs

Generic programming: types are known at compile time

Two important principles of generic code:

• The function parameter in the template is the application of const (more types can be accepted with const, copy / non copy / const / non const)
• The condition judgment of function weight only uses < comparison operator (reduce the requirements for type, < can be calculated! =, >, = =)

16.1 definition template

16.1.1 function template

Represents any type   Type parameter

template <typename T, typename W, typename A >  // Specify a type of T
int compare(const T& v1, const W& v2) { // Type specified in template
	if (v1 < v2) return -1;
	if (v2 < v1) return 1;
	return 0;
}

Template parameter lists work much like function parameter lists

class or typename must be used before type parameters. They are no different in the template parameter list

The type has been specified to represent any value. Non - type parameter must be a constant expression

template<unsigned N, unsigned M>
int compare(const char(&p1)[N], const char(&p2)[m]) {
	return strcmp(p1, p2);
}

Function templates for inline and constexpr:

inline or constexpr is placed after the template parameter and before the return type

template <typename T> inline T min(const T&, const T&);

Function templates and class template member functions are usually defined in header files

16.1.2 type formwork

The compiler cannot infer template parameter types for class templates. It feels like replacing all the places where string s need to be used with T

template<typename T> 
class Blob {
public:
	typedef T value_type;
	typedef typename std::vector<T>::size_type size_type;

	Blob():data(std::make_shared<std::vector<T>>()) {};
	Blob(std::initializer_list<T> il) :data(std::make_shared<std::vector<T>>(il)) {};
	size_type size() const { return data->size(); }
	bool empty() const { return data->empty(); }
	void push_back(const T& t) { data->push_back(t); }
	void push_back(T&& t) { data->push_back(std::move(t)); }
	void pop_back();
	T& back();
	T& operator[](size_type i);
private:
	std::shared_ptr<std::vector<T>> data;
	Blob check(size_type i, const T& msg) const;
};

There is no relationship between the classes formed by the template

When the function declared in the inner class is completed outside the class, the type t still needs to be declared with template < typename T > and < T > must be added after the class name where the class name needs to be used. For example, the definition of check function is:

template<typename T>
Blob<T> Blob<T>::check(size_type i, const T& msg) const { // < T > is required when using the class template name outside the class template
	// xx
}

When using class templates:

int main(int argc, char** argv) {
	Blob<int> ia = { 0,1,2,3,4 };
}

Template nesting and < T > can be omitted when within the scope of class template. Blobptr < T > is required when using class template name outside class template

template <typename T> class BlobPtr {
public:
	BlobPtr() :curr(0) {}
	BlobPtr(Blob<T> &a, size_t sz=0):wptr(a.data), curr(sz) {} // Blob < T > is required when using other types of templates
	T& operator*() const {
		auto p = check(curr, "dereference past end");
		return (*p)[curr];
	}
	BlobPtr& operator++(); // Blobptr < T > & operator + + ()
	BlobPtr& operator--(); // Equivalent to blobptr < T > & operator -- ()
private:
	std::shared_ptr<std::vector<T>>check(std::size_t, const std::string&) const;
	std::weak_ptr<std::vector<T>> wptr;
	std::size_t curr;
};

Class templates and friends:

If the class template contains non template friends, the friends can access all template instances

If a class template contains template friends, all friend instances can access all template instances or authorize only specific friends

One to one friendly relationship:

template <typename> class BlobPtr; // Friend class usage defined in Blob

template<typename> class Blob; // Function declaration for operator = =
template<typename T> // Function declaration for operator = =
bool operator==(const Blob<T>&, const Blob<T>&); // Function declaration

template<typename T> 
class Blob {
public:
	// typedef T value_type;
	typedef typename std::vector<T>::size_type size_type;

	friend class BlobPtr<T>; //Friend class
	friend bool operator==<T>(const Blob<T>&, const Blob<T>&); // Friend function declaration
    // xx
}

In the above code, the type of blobptr < T > in the declaration of friend class and the type of Blob in the declaration of friend function are t, so it is limited that the type used in BlobPtr, operator = must be consistent with the type in Blob. That is, the friendly relationship is limited to all blobs, BlobPtr, operator = = using the same type

Common and specific template friendships:

There are two types. One is non template class to template class:

template<typename T> class Pal; //Pre declaration of class template
class C {
	friend class Pal<C>; // Only the class Pal instantiated with C is a friend of C
	template <typename T> friend class Pal2; // All instances of Pal2 are friends of C. in this case, no pre declaration is required
};

  On the other hand, template classes are used for other:

template<typename T> class Pal; // Pre declaration of class template
template<typename T> class C2 {
	friend class Pal<T>; // The instance of C2 of type T and the instance of Pal are friendly. One to one
	template <typename X> friend class Pal2; // X may or may not be equal to T. all instances of C2 and Pal2 of any type are friend relationships, many to many
	friend class Pal3; // Pal3 does not require pre declaration. All types of C2 instances are friends with pal3, many to one

};

In the above code, one-to-one declaration is required in both cases, and the rest are not required

Template parameters can also be declared as friends:

template<typename T> class B {
	friend T;
};

Template type alias:   Because blob < T > is not an exact type, all cannot be renamed with typedef, and can only be renamed with a certain type; But you can name it that way

typedef Blob<T> StrBlob;  // error
typedef Blob<string> StrBlob;

template<typename T> using twin = pair<T, T>; // definition
twin<string>authors; // ==Pair < string, string > usage

template<typename T> using twin2 = pair<int, T>; // You can also fix a type

Static member of class template: all class template instances share the same static member

template<typename T> class Foo {
public:
	static std::size_t cout() { return ctr; }
private:
	static std::size_t ctr;
};
template<typename T> size_t Foo<T>::ctr = 0; // The definition is similar to that of a non static member

int main(int argc, char** argv) {
	Foo<int> fi;
	auto ct = Foo<int>::cout();
	ct = fi.cout();
	ct = Foo::cout(); // Error, unable to determine template instance, so cout function cannot be used
}

static members need to define initial values outside the template

When using a template name outside a template, you need to carry a type list

// 16.16
template <typename T>
class Vec {
public:
	Vec() :elements(nullptr), first_free(nullptr), cap(nullptr) {}
	Vec(const Vec&);
	Vec(const std::initializer_list<T>&);
	Vec& operator=(const Vec&);
	Vec& operator=(Vec&&) noexcept;
	Vec(Vec&&) noexcept;
	~Vec();

	void push_back(const T&);
	void push_back(const T&&);
	size_t size() const { return first_free - elements; }
	size_t capacity() const { return cap - elements; }

	void resize(size_t);
	void resize(size_t, const T&);

	// If new_ If the capacity() is greater than the current capacity(), new storage will be allocated, otherwise the method will not do anything.
	void reserve(size_t);  // Increase the capacity of the vector to be greater than or equal to the specified value
	T* begin() const { return elements; }
	T* end() const { return first_free; }

private:
	static std::allocator<T> alloc; // Used to allocate element memory
	// If there is no room for the new element, the memory is reallocated
	void chk_n_alloc() {
		if (size() == capacity()) reallocate();
	}
	// It is used to allocate enough memory to hold the elements of the given range, and copy these elements to the newly allocated memory. Two pointers in the pair returned
	// Point to the beginning and end of the new space respectively
	std::pair<T*, T*>alloc_n_copy(const T*, const T*);
	void free(); // Destroy elements and free memory
	void reallocate(size_t); // Get more memory and copy existing elements
	T* elements; // Pointer to the first element
	T* first_free; // Pointer to the first free element
	T* cap; // Pointer to trailing position
};
template<typename T>
std::allocator<T> Vec<T>::alloc = std::allocator<T>();

template<typename T>
void Vec<T>::push_back(const T& s) {
	chk_n_alloc();
	alloc.construct(first_free++, s);
}
template<typename T>
void Vec<T>::push_back(const T&& s) {
	chk_n_alloc();
	alloc.construct(first_free++, std::move(s));
}
template<typename T>
std::pair<T*, T*>Vec<T>::alloc_n_copy(const T* b, const T* e) {
	auto data = alloc.allocate(e - b);
	return { data, uninitialized_copy(b,e, data) };
}
template<typename T>
void Vec<T>::free() {
	// If elements is empty, it means that the vec is empty, so there is no need to free memory
	if (elements) {
		for_each(elements, first_free, [this](T& s) { alloc.destroy(&s); });
		alloc.deallocate(elements, cap - elements);
	}
}
template<typename T>
Vec<T>::Vec(const Vec<T>& s) {
	auto newData = alloc_n_copy(s.begin(), s.end());
	elements = newData.first;
	first_free = cap = newData.second;
}
template<typename T>
Vec<T>::~Vec() {
	free();
}
template<typename T>
Vec<T>& Vec<T>::operator=(const Vec<T>& rhs) {
	auto data = alloc_n_copy(rhs.begin(), rhs.end());
	free();
	elements = data.first;
	first_free = cap = data.second;
	return *this;
}
template<typename T>
Vec<T>& Vec<T>::operator=(Vec<T>&& rrs) noexcept {
	if (this != &rrs) {
		free();
		elements = rrs.elements;
		first_free = rrs.first_free;
		cap = rrs.cap;
		rrs.elements = rrs.first_free = rrs.cap = nullptr;
	}
	return *this;
};
template<typename T>
void Vec<T>::reallocate(size_t new_size) {
	size_t newcapacity = 0;
	if (new_size == 0) newcapacity = size() ? 2 * size() : 1;
	else newcapacity = new_size;
	auto newdata = alloc.allocate(newcapacity);
	auto dest = newdata;
	auto elem = elements;
	for (size_t i = 0; i != size(); ++i)
		alloc.construct(dest++, std::move(*elem++));
	free();
	elements = newdata;
	first_free = dest;
	cap = elements + newcapacity;
}
template<typename T>
void Vec<T>::reserve(size_t new_cap) {
	if (new_cap > capacity()) {
		reallocate(new_cap);
	}
}
template<typename T>
void Vec<T>::resize(size_t count) { resize(count, T()); }
template<typename T>
void Vec<T>::resize(size_t count, const T& s) {
	if (count > size()) {
		if (count > capacity()) reallocate(2 * count);
		for (size_t t = size(); t != count; ++t) {
			alloc.construct(first_free++, s);
		}
	}
	else if (count < size()) {
		while (first_free != elements + count) alloc.destroy(--first_free);
	}
}
template<typename T>
Vec<T>::Vec(const std::initializer_list<T>& lst) {
	auto newdata = alloc_n_copy(lst.begin(), lst.end());
	elements = newdata.first;
	first_free = cap = newdata.second;
}
template<typename T>
Vec<T>::Vec(Vec<T>&& s) noexcept :elements(s.elements), first_free(s.first_free), cap(s.cap) {
	s.elements = s.first_free = s.cap = nullptr;
}

16.1.3 template parameters

• Template parameter names can be used from after their declaration to before the end of template declaration or definition
• Template parameters hide the same name declared in the outer scope
• Parameter names cannot be redefined

Template parameters must be included in the template declaration. The names after typename is used in the declaration and definition can be different

Use type members of the class:

By default, the name accessed through the scope operator is not a type, but a static member, such as alloc in the vec template

template<typename T> std::allocator<T> Vec<T>::alloc = std::allocator<T>();

If you want to use a type member of a template type parameter, you must use typename explicitly

template<typename T>
typename T::value_type top(const T& c) {
	if (!c.empty()) return c.back();
	else return typename T::value_type();
}

When you want to tell the compiler that a name represents a type, you must use typename instead of class

//This needs practice and reflection

Default template arguments:

template<typename T, typename F=less<T>()>  // Less < T > less < int > comparison function
bool compare(const T& v1, const T& v2, F f) {
	if (f(v1, v2)) return -1;
	if (f(v2, v1)) return 1;
	return 0;
}

Template default real participation class template:

Whenever a class template is used (it can not be used when the class acts inside), angle brackets must be added after the template name

template<typename T = int> class Numbers { // The default is int typename, or class
public:
	Numbers(T v = 0) :val(v) {};
private:
	T val;
};

int main(int argc, char** argv) {
	Numbers<long double> lots;
	Numbers<> aaa; // Default int
}

16.1.4 member template

A member function that is a template in a class is called a member template and cannot be a virtual function. A member template has its own parameter type

template<typename T>
class NewCall {
	template<typename TT> void funInC(TT& a) {
		//xx
	}
	template<typename TT> void funInC2(TT&);
};

template<typename T>  // Class type parameter and member template type parameter are required
template<typename WW>  // The type parameters here can be different from those defined in the class
void NewCall<T>::funInC2(WW& w) {
	//xx
};

Instantiation and member template: the compiler infers the type of template class according to the passed in class type, and infers the type of member template according to the passed in parameters of member function

16.1.5 control instantiation

The template is instantiated only when it is used   explicit instantiation

extern template declaration;  // Instantiation declaration
template declaration; // Instantiation definition
// as
extern template class Blob<string>; // statement
template int compare(const int&, const int&); // definition

When the compiler encounters an extern declaration, it will not instantiate the code in this file, and promises to have a non extern declaration / definition of the instantiation in other parts of the program. There can be multiple extern declarations, and there must be only one definition

extern must appear before any template is used, otherwise it will be instantiated automatically

Instantiating a definition instantiates all members

There are several situations where the template may be instantiated

• Declaring a pointer and reference to a class template will not cause instantiation of the class template, because it is not necessary to know the definition of the class.
• When defining an object of class type, you need to define the class, so the class template will be instantiated.
• When using sizeof(), because you need to calculate the size of an object, the compiler must instantiate it according to its type
• The new class template is instantiated
• Referencing a member of a class template causes the class template to be instantiated by the compiler.
• It should be noted that the member function of the class template itself is also a template. Standard C + + requires that such member functions be instantiated only when called or addressed

16.1.6 efficiency and flexibility

//16.28 exercises   reference resources   https://github.com/pezy/CppPrimer/tree/master/ch16

16.2 template argument inference

16.2.1 type conversion and template type parameters

Const conversion:   Non const references / pointers can be passed to a const

template<typename T> T fobj(T, T);
template<typename T> T fref(const T&, const T&);

string s1("aaaaaa");
const string s2("bbbb");
fobj(s1, s2);  // const of s2 is ignored
fref(s1, s2);  // s1 non const to const

Array or function pointer: if the formal parameter is not a reference type,   Normal pointer conversion can be applied to the array / function type argument, that is, the array argument can be converted into a pointer to the first element, and the function argument can be converted into a pointer to the function type

template<typename T> T fobj(T, T);
template<typename T> T fref(const T&, const T&);

int a[10], b[11];
fobj(a, b); // a[10] -> int*, b[11]-> int*  fobj(int*, int*)
fref(a, b); // When referencing the formal parameter of the wrong type, the argument does not convert a[10], b[11], which is not a type

When passing arguments to function parameters with template type, there are only const conversion, array and function to pointer conversion

If the function parameter type is not a template parameter, normal type conversion is performed on the argument

// 16.34
template<typename T> int compare2(const T&, const T&);

compare2("hi", "world"); // Illegal, "hi" is converted to const char [3], and "world" is converted to const char[6]. The two types are different
compare2("bye", "daa"); // Legal, all converted to const char (&) [4]

16.2.2 function template display arguments

The template arguments can be explicitly declared by following < type > after the function name, such as:

template<typename T>
bool compare(const T& v1, const T& v2) {
	if (v1<v2) return -1;
	if (v2<v1) return 1;
	return 0;
}
// use
auto a = compare<std::string>("helo", "world");

16.2.3 tail return type and type conversion

When the return value type is required, but the return value type cannot be determined when the parameter type is not determined, the tail should be used to indicate the return value type:

template<typename It>
auto fcn(It beg, It end) -> decltype(*beg) {
	return *beg;
}

Tail return allows us to declare the return type after the parameter list

The above code can only return a reference to an element,   If you want to return a copy of an element, you need to use the following code

template<typename It>
auto fcn2(It beg, It end) -> typename remove_reference<decltype(*beg)>::type {
	return *beg;
}

remove_reference is a standard library function. Its function is to remove the reference part of the reference type, and the type returns the remaining types after removing the reference part

For example: remove_ reference<int&>::type   The value of is int

Similar to remove_ Reference < T >: functions of type include:

  16.2.4 function pointer and argument inference

Function templates can be instantiated through function pointers. Overloaded functions need to know which version of the template they are

template<typename T> int compare(const T&, const T&);
// function overloading
void func(int(*)(const string&, const string&));
void func(int(*)(const int&, const int&));

// use
int (*pf1)(const int&, const int&) = compare; // T = int
func(compare<int>); // Call the overloaded func, but you need to specify which compare is? Is it a string version or an int version

When the parameter is a   Address of the function template instance   The program must be able to uniquely determine the type or value of each template parameter

16.2.5 template argument inference and reference

Infer type from lvalue reference function parameter:  

Template < typename T > void F1 (T &) the type to be passed in must be an lvalue. If the passed in const int, t is const int

Template < typename T > void F2 (const T &) can pass in any parameter, including an R-value. At this time, the top const will be ignored. For example, f2(ci) if ci is const int, t is still int

Template < typename T > void F3 (T & &) the right value is the same as the left value

Reference collapse and R-value reference parameters:

Two kinds of out of column:

1. When we pass an lvalue (such as i) to the right value reference parameter (such as f3) of the function, and the right value reference points to the template type parameter (such as T & &), the compiler infers that the template type parameter is the lvalue reference type of the argument (i). Therefore, the type of T in f3(i) is int&
2. References will collapse. For example, X & &, X & &, X & & & will collapse into type X &,   X & & & & fold to X&&

Reference collapses can only be applied to references created by profiles, such as type aliases or template parameters

16.2.6 std::move

static_cast can explicitly convert an lvalue to an rvalue reference  

template<typename T>
typename remove_reference<T>::type&& move(T&& t) {
	return static_cast<typename remove_reference<T>::type&&>(t);
}
// When move passes in an lvalue, it becomes string & & move (string & T)
// static_ Cast < string & & > (T) the type of T is string &. Cast converts an lvalue reference to an lvalue reference

16.2.7 forwarding

You can use the feature that template parameters are r-valued references to retain all the attributes of function parameters, that is, if a function parameter is an r-valued reference (T & &) pointing to template type parameters, the const attribute and L / R-value attribute of its corresponding argument will be maintained. When used for an r-valued reference function parameter (T & &) pointing to template parameter types, forward keeps all the details of the argument type

template<typename F, typename T1, typename T2>
void flip(F f, T1&& t1, T2&& t2) {
	f(std::forward<T2>(t2), std::forward<T1>(t1));
}
// This definition can perfectly preserve the attributes of T1 and T2 and realize inversion

16.3 overloading and templates

Function templates can be overloaded by another template or ordinary non - template functions

Overloaded matching rules:

1. For a call, the candidate function includes all template parameters, and the function template instance that is successfully inferred
2. Candidate function templates are always feasible because template argument inference excludes any infeasible templates
3. Feasible functions (template and non template) are sorted by type conversion
4. If one function provides a better match than any other function, select this function. If multiple functions provide the same good match, then:

• If only one of the equally good functions is a non template function, select this function
• If there is no non template function in the same good function, but there are multiple function templates, and one template is more special than other templates, select this template
• Otherwise, this call is ambiguous

16.4 variable parameter template

Template function or template class that can receive a variable number of parameters. Variable parameters -- parameter package. Symbol   ellipsis,

typename... T

Two parameter packages:

• Template parameter package -- zero or more template parameters
• Function parameter package -- zero or more function parameters

template<typename T, typename ... Args>
void foo(const T& t, const Args& ... rest) {}

sizeof... Operator

When we need to know how many elements are in the package, we can use the sizeof... Operator

template<typename T, typename ... Args>
void foo(const T& t, const Args& ... rest) {
	cout << sizeof...(Args) << endl;
}

16.4.1 preparation of variable parameter function template

Variable parameter functions are usually recursive. Each time the first argument in the package is processed, it calls itself with the remaining arguments

template<typename T>
ostream& print(ostream& os, const T& t) { return os << t; }
template<typename T, typename ... Args>
ostream &print(ostream &os, const T &t, const Args& ... rest) {
	os << t << ", ";
	return print(os, rest...);
// Here, the first argument in rest is bound to rest every time it is parsed, and the rest continues to be bound to rest in the formal parameter as rest
}

16.4.2 package extension

That is, unpacking the template parameter package / template function parameter package,   For example, the print variable parameter template function above

When print(cout, i, s, 42), the template function will be instantiated as:  

print(ostream&, const int&, const string&, const int&);

When you need to call a function to perform function operations on the elements in the package one by one, you need to:

template <typename ... Args>
ostream& errorMsg(ostream& os, const Args& ... rest) {
	return print(os, debug_rep(rest)...)
	// debug_rep is also a template function that accepts a parameter and prints out the contents of the parameter
}

16.4.3 forwarding parameter packet

When forwarding, define the formal parameter as the right value version

template<typename ... Args>
inline void StrVec::emplace_back(Args&& ... args) {
	chk_n_alloc();
	alloc.construct(first_free++, std::forward<Args>(args)...);
}

16.5 template characterization

When making a special case of a function template, you must provide arguments for each template parameter in the original template. You should also follow < >. That is, the type used in the special case definition here must match the type of the previously defined template

// Special case a compare template
template<>
int compare(const char* const& p1, const char* const& p2) { return strcmp(p1, p2); }

    The typename that should be followed by the template is used to specify the types used in the template. However, because it is a special case and specifies the types used in the template, the template is only followed by < > without defining the types

Const char * const & a reference to the const pointer to const char

Function overloading and template specialization:

A specialized version is essentially an instance, not an overloaded version of a function name

The template and its special case version should be declared in the same header file. The declarations of all templates with the same name should be placed first, followed by the special case version of these templates. Otherwise, it is difficult for the compiler to find the error without special case declaration

Class template specialization:

Partial specialization of class template:

Partially specialized classes are still template classes

Specialization of members rather than classes: only specialization of member functions rather than the entire template

template<typename T> struct Foo2 {
	Foo2(const T &t = T()):mem(t) {}
	void Bar();
	T mem;
};
template<>
void Foo2<int>::Bar(){}  // Bar, member of exceptional foo < int >
// After specialization, when Foo is instantiated with a type other than int, it is the same as other cases
// When instantiating Foo with int type, it is the same as others except Bar