[C++知识库]《C++程序设计原理与实践》习题答案 第十四章 第14章习题答案

本章实现的模板Vector

目前学到第十四章，对继承不熟，因此没有用到14.5.6中的vector_base类，因而没有实现vector类的RAII。

//Vector_template.h

#include<iostream>
#include"14_8-Allocator.h"

//使用模板需要注意，目前VS2019都要求在使用模板的地方必须能得到模板的完整定义
//因此，我们将模板的定义都放在了头文件中

template<typename T, typename A = allocator<T>>
class vector {
	static const int first_expand_space{ 8 };
	A alloc;			//用 alloc 管理元素内存
	int sz;				//元素数目
	int space;			//总空间 = 元素数目 + 给新元素的空闲空间（槽位）；总空间是指当前分配的空间
	T* elem;
public:
	class Invalid {};
	struct out_of_range { /*...*/ };	//用来报告越界错误

	vector();									//默认构造函数
	explicit vector(int x, T def = T{});		//构造函数，x为元素数量，def为初始化值，在定义中有默认值
	vector(std::initializer_list<T>lst);	//初始化器列表构造函数
	
	vector(const vector&);						//拷贝构造函数
	vector& operator=(const vector&);			//拷贝赋值函数
	
	vector(vector&&);							//移动构造函数
	vector& operator=(vector&&);				//移动赋值函数
	
	int size() const;
	void reserve(int newalloc);					//改变 space 的大小
	int capacity()const;						//返回 space 的大小
	void resize(int newalloc, T def = T{});		//该表元素数量
	void push_back(const T& val);

	T& operator[](int n);
	const T& operator[](int n) const;
	T& at(int n);
	const T& at(int n) const;
	
	~vector();
};


//下面是定义

template<typename T, typename A>
vector<T, A>::vector()
	:sz{ 0 }, space{ 0 }, elem{ nullptr }
{ }

template<typename T, typename A>
vector<T, A>::vector(int x, T def)
//构造函数，x为元素数量
	: sz{ x }, space{ x }
{
	if (x < 0)
		throw Invalid{};
	elem = alloc.allocate(x);
	for (int i = 0; i < sz; i++)
		alloc.construct(elem + i, def);	//初始化
}

template<typename T, typename A>
vector<T, A>::vector(std::initializer_list<T> lst)
//初始化器列表构造函数
	:sz{ int(lst.size()) }, space{ int(lst.size()) }, elem{ alloc.allocate(lst.size()) }
{
	//std::cout << "初始化列表构造函数\n";
	const T* ti = lst.begin();
	for (int i = 0; i < sz; ++i)
		alloc.construct(elem + i, *ti++);	//初始化
}

template<typename T, typename A>
vector<T, A>::vector(const vector& arg)
//拷贝构造函数
	: sz{ arg.sz }, space{ arg.space }, elem{ alloc.allocate(arg.space) }
{
	//std::cout << "拷贝构造函数\n";
	for (int i = 0; i < sz; ++i)
		alloc.construct(elem + i, arg.elem[i]);
}

template<typename T, typename A>
vector<T, A>& vector<T, A>::operator=(const vector& arg)
//拷贝赋值函数
{
	//std::cout << "拷贝赋值函数\n";
	if (this == &arg)				//自赋值，什么也不用做
		;
	else if (arg.sz <= space)		//空间足够，无需分配空间
	{
		for (int i = 0; i < sz; ++i)
			alloc.destroy(elem + i);				//先销毁原来的元素
		for (int i = 0; i < arg.sz; ++i)
			alloc.construct(&elem[i], arg.elem[i]);	//拷贝元素
		sz = arg.sz;
	}
	else
	{
		T* p = alloc.allocate(arg.sz);
		for (int i = 0; i < arg.sz; ++i)
			alloc.construct(p + i, arg.elem[i]);	//拷贝元素
		alloc.deallocate(elem, space);
		sz = space = arg.sz;		//设置新大小
		elem = p;					//指向新元素的指针
	}
	return *this;					//按照惯例，赋值运算符将返回被赋值对象的引用
}

template<typename T, typename A>
vector<T, A>::vector(vector&& arg)
//移动构造函数
	:sz{ arg.sz }, space{ arg.space }, elem{ arg.elem }
{
	//std::cout << "移动构造函数\n";
	arg.sz = arg.space = 0;		//令 arg 变为空
	arg.elem = nullptr;
}


template<typename T, typename A>
vector<T, A>& vector<T, A>::operator=(vector&& arg)
//移动赋值函数，将 arg 移动到本vector
{
	//std::cout << "移动赋值函数\n";
	alloc.deallocate(elem, space);
	sz = arg.sz;
	space = arg.space;
	elem = arg.elem;
	arg.sz = arg.space = 0;
	arg.elem = nullptr;
	return *this;
}

template<typename T, typename A>
int vector<T, A>::size() const
{
	return sz;
}

template<typename T, typename A>
void vector<T, A>::reserve(int newalloc)
{
	if (newalloc <= space)					//永远不会减少分配的空间
		return;
	T* p = alloc.allocate(newalloc);	//分配新空间
	for (int i = 0; i < sz; ++i)
		alloc.construct(&p[i], elem[i]);		//拷贝现有元素
	for (int i = 0; i < sz; ++i)
		alloc.destroy(&elem[i]);			//销毁现有元素
	alloc.deallocate(elem, space);			//释放旧空间
	elem = p;
	space = newalloc;
}

template<typename T, typename A>
int vector<T, A>::capacity() const
{
	return space;
}

template<typename T, typename A>
void vector<T, A>::resize(int newsize, T def)
//令 vector 有 newsize 个元素
//newsize 必须 >= 0
//用默认值 def 初始化每个新元素
{
	if (newsize < 0)
		throw Invalid{};
	reserve(newsize);
	for (int i = newsize; i < sz; ++i)
		alloc.destroy(elem + i);			//销毁从newsize开始的元素
	for (int i = sz; i < newsize; ++i)
		alloc.construct(&elem[i], def);		//用默认值初始化
	sz = newsize;
}

template<typename T, typename A>
void vector<T, A>::push_back(const T& val)
//将 vector 的大小增加1：用 val 初始化新元素
{
	if (space == 0)
		reserve(first_expand_space);
	else if (sz >= space)
		reserve(space * 2);
	alloc.construct(&elem[sz], val);
	++sz;
}

template<typename T, typename A>
T& vector<T, A>::operator[](int n)
{
	return elem[n];
}

template<typename T, typename A>
const T& vector<T, A>::operator[](int n) const
{
	return elem[n];
}

template<typename T, typename A>
T& vector<T, A>::at(int n)
{
	if (n < 0 || sz <= n)
		throw out_of_range();
	return elem[n];
}

template<typename T, typename A>
const T& vector<T, A>::at(int n) const
{
	if (n < 0 || sz <= n)
		throw out_of_range();
	return elem[n];
}

template<typename T, typename A>
vector<T, A>::~vector()
{
	for (int i = 0; i < sz; ++i)
		alloc.destroy(elem + i);		//释放之前要销毁对象元素
	alloc.deallocate(elem, space);	
}

14.1

#include"../../std_lib_facilities.h"

template<typename T> void f(vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		cerr << "two vectors have different size\n";
		return;
	}
	for (int i = 0; i < v1.size; ++i)
		v1[i] += v2[i];
}

14.2

#include"../../std_lib_facilities.h"

template<typename T, typename U>	//T和U的限制为可以做乘法和加法的类型
T in_product(const vector<T>& vt, const vector<U>& vu)
{
	T res{ 0 };
	if (vt.size() != vu.size())
	{
		cerr << "two vectors have different size\n";
		return res;
	}
	for (int i = 0; i < vt.size(); ++i)
		res += vt[i] * vu[i];
	return res;
}

14.3

#include"../../std_lib_facilities.h"

template<typename T> class Pair {
	string var_name;
	T val;
public:
	Pair(string n, T v) :var_name{ n }, val{ v }{	}
	string get_name() { return var_name; }
	string get_name()const { return var_name; }
	T get_val() { return val; }
	const T& get_val()const { return val; }
	void change_val(T v) { val = v; }
};

vector<Pair<double>> var_tbl;

bool is_declared(string var)
{
	for (const Pair<double>& v : var_tbl)
		if (v.get_name() == var)
			return true;
	return false;
}

double define_name(string var, double val)
{
	if (is_declared(var))
		error(var, " declared twice");
	var_tbl.push_back(Pair<double>{var, val});
	return val;
}

14.4

#include"../../std_lib_facilities.h"

struct God {
	string name;
	string mythology;
	string mount;
	string weapon;
};

template<typename T>
class Link {
public:
	T god;

	Link(const God& g, Link* p = nullptr, Link* s = nullptr)
		:god{ g }, pred{ p }, succ{ s } { }

	Link* insert(Link* n);	//在此对象之前插入n
	Link* add(Link* n);		//在此对象之后插入n
	Link* add_order(Link* n);	//按字典序将n放置在正确位置中
	Link* erase();			//将此对象从链表中删除
	Link* find(const string& s);	//在链表中查找s
	const Link* find(const string& s) const;	//在const链表中查找s
	Link* advance(int n);		//在链表中移动n个位置
	Link* next() const { return succ; }
	Link* prev() const { return pred; }
private:
	Link* pred;
	Link* succ;
};

template<typename T>
void print_all(Link<T>* p);


int main()
try
{
	Link<God>* norse_gods = new Link<God>{ God{"Thor", "Norse","",""} };
	norse_gods = norse_gods->add_order(new Link<God>{ God{"Odin", "Norse","Eight-legged flying horse called Sleipner",""} });
	norse_gods = norse_gods->add_order(new Link<God>{ God{"Freia", "Norse", "",""} });
	print_all(norse_gods);
	cout << '\n';

	Link<God>* greek_gods = new Link<God>{ God{"Hera","Greek","",""} };
	greek_gods = greek_gods->insert(new Link<God>{ God{"Athena","Greek","",""} });
	greek_gods = greek_gods->add_order(new Link<God>{ God{"Ares" ,"Greek", "", ""} });
	greek_gods->add_order(new Link<God>{ God{"Zeus","Greek","",""} });
	greek_gods->add_order(new Link<God>{ God{"Poseidon","Greek","","Trident"} });
	print_all(greek_gods);
	cout << '\n';

	print_all(greek_gods->advance(2));
	cout << '\n';

	return 0;
}
catch (runtime_error& e)
{
	cerr << "Runtime error: " << e.what() << endl;
	return 1;
}
catch (...)
{
	cerr << "Exception occured!\n";
	return 2;
}

template<typename T>
Link<T>* Link<T>::insert(Link<T>* n)
//在此对象之前插入n
{
	if (n == nullptr)
		return this;
	if (this == nullptr)
		return n;
	n->succ = this;
	n->pred = pred;
	if (pred)
		pred->succ = n;
	pred = n;
	return n;
}

template<typename T>
Link<T>* Link<T>::add(Link<T>* n)
//在此对象之后插入n
{
	if (n == nullptr)
		return this;
	if (this == nullptr)
		return n;
	n->pred = this;
	n->succ = succ;
	if (succ)
		succ->pred = n;
	succ = n;
	return this;
}

template<typename T>
Link<T>* Link<T>::add_order(Link<T>* n)
//按字典序将n放置在正确位置中；返回在前的元素
{
	if (n == nullptr)
		return this;
	if (this == nullptr)
		return n;
	Link<T>* header = this;

	if (n->god.name < header->god.name)
	{
		n->pred = pred;
		n->succ = this;
		pred = n;
		header = n;
	}
	else if (n->god.name > header->god.name)
	{
		Link<T>* p;
		for (p = this; p->succ && n->god.name > p->succ->god.name; p = p->next())
			continue;
		n->succ = p->succ;
		n->pred = p;
		if (p->succ)
			p->succ->pred = n;
		p->succ = n;
	}
	return header;
}

template<typename T>
Link<T>* Link<T>::erase()
//将此对象从链表中删除；返回该对象的后继
{
	if (this == nullptr)
		return nullptr;
	if (pred)
		pred->succ = succ;
	if (succ)
		succ->pred = pred;
	return succ;
}

template<typename T>
Link<T>* Link<T>::find(const string& name)
//在链表中查找s
{
	Link<T>* p = this;
	while (p)
		if (p->god.name == name)
			break;
		else
			p = p->succ;
	return p;
}
template<typename T>
const Link<T>* Link<T>::find(const string& name) const
//在const链表中查找s
{
	const Link<T>* p = this;
	while (p)
		if (p->god.name == name)
			break;
		else
			p = p->succ;
	return p;
}

template<typename T>
Link<T>* Link<T>::advance(int n)
//在链表中移动n个位置
{
	Link<T>* p = this;
	if (n < 0)
	{
		while (n++)
			p = p->pred;
	}
	else if (n > 0)
		while (n--)
			p = p->succ;
	return p;
}


//辅助函数
template<typename T>
void print_all(Link<T>* p)
{
	cout << "{ ";
	God g;
	while (p)
	{
		g = p->god;
		cout << "( " << g.name << ", "
			<< g.mythology << ", "
			<< g.mount << ", "
			<< g.weapon << " )";
		if (p = p->next())
			cout << '\n';
	}
	cout << " }";
}

14.5, 14.6 and 14.7 Number

//Exercise 14.5, 14.6 and 14.7

#include"../../std_lib_facilities.h"


template<typename T>	//T应是数值类型
class Number {
	T n;
public:
	Number(T ini = T{}) :n{ ini } { }
	T get() const { return n; }
	void set(T v) { n = v; }
	Number& operator=(const Number& a);	//赋值运算符必须重载为类的非静态成员函数
};

template<typename T>
Number<T>& Number<T>::operator=(const Number<T>& a)
{
	n = a.get();
	return *this;
}


//二元运算符重载，如果不改变左操作数，那么一般重载为非成员函数
template<typename T>
Number<T> operator+(const Number<T>& a, const Number<T>& b)
{
	Number<T> res{ a.get() + b.get() };
	return res;
}

template<typename T>
Number<T> operator+=(Number<T>& a, const Number<T>& b)
{
	a.set(a.get() + b.get());
	return Number<T>{a.get()};
}

template<typename T>
Number<T> operator-(const Number<T>& a, const Number<T>& b)
{
	Number<T> res { a.get() - b.get() };
	return res;
}

template<typename T>
Number<T> operator*(const Number<T>& a, const Number<T>& b)
{
	Number<T> res { a.get()* b.get() };
	return res;
}

template<typename T>
Number<T> operator/(const Number<T>& a, const Number<T>& b)
{
	if (b.get() == 0)
		error("divide by zero");
	Number<T> res { a.get() / b.get() };
	return res;
}

template<typename T>
Number<T> operator%(const Number<T>& a, const Number<T>& b)
{
	if (b.get() == 0)
		error("mod by zero");
	//模运算可定义为 x % y = x - int(x / y) * y
	T res = a.get() - int(a.get() / b.get()) * b.get();
	return Number<T> {res};
}

template<typename T>
istream& operator>>(istream& is, Number<T>& n)
{
	T v;
	is >> v;
	n.set(v);
	return is;
}

template<typename T>
ostream& operator<<(ostream& os, const Number<T>& n)
{
	os << n.get();
	return os;
}

//专门针对习题7的乘法模板
template<typename T, typename U>
Number<T> operator*(const Number<T>& a, const Number<U>& b)
{
	Number<T> res{ a.get() * b.get() };
	return res;
}

//template<typename T, typename U>
//T in_product(const vector<T>& vt, const vector<U>& vu);
//VS2019仍然要求在使用模板的地方必须能够得到模板的完整定义，所以上面的声明是不行的，必须得是下面的完整定义
template<typename T, typename U>	//T和U的限制为可以做乘法和加法的类型
T in_product(const vector<T>& vt, const vector<U>& vu)
{
	T res{ 0 };
	if (vt.size() != vu.size())
	{
		cerr << "two vectors have different size\n";
		return res;
	}
	for (size_t i = 0; i < vt.size(); ++i)
		res += vt[i] * vu[i];
	return res;
}

int main()
try
{
	Number<int>a{ 1 };
	Number<int>b;
	cout << "int a = " << a << '\n';
	a = Number<int>{ 72 };
	cout << "a = Number<int>{ 72 } : a = " << a << '\n';
	cout << "int b = " << b << '\n';
	cin >> b;
	cout << "cin >> b --> int b = " << b << '\n';
	cout << "a + b = " << a + b << '\n';
	cout << "a - b = " << a - b << '\n';
	cout << "a * b = " << a * b << '\n';
	cout << "a / b = " << a / b << '\n';
	cout << "a % b = " << a % b << '\n';


	Number<double>x{ 1.2 };
	Number<double>y;
	cout << "double x = " << x << '\n';
	cout << "double y = " << y << '\n';
	x = Number<double>{ 7.2 };
	cout << "x = Number<double>{ 7.2 } --> x = " << x << '\n';
	cin >> y;
	cout << "cin >> y --> double y = " << y << '\n';
	cout << "x + y = " << x + y << '\n';
	cout << "x - y = " << x - y << '\n';
	cout << "x * y = " << x * y << '\n';
	cout << "x / y = " << x / y << '\n';
	cout << "x % y = " << x % y << '\n';

	vector<Number<double>>vt{ x, y };
	vector<Number<int>>vu{ a, b };
	Number<double> res = in_product(vt, vu);
	cout << "vt .* vu = " << res << '\n';

	return 0;
}
catch (runtime_error& e) {
	cerr << "Runtime error: " << e.what() << endl;
	return 1;
}
catch (...) {
	cerr << "Exception occured!\n";
	return 2;
}

14.8 Allocator

14_8-Allocator.h

//14_8-Allocator.h

#include<iostream>
#include<stdio.h>
#include<stdlib.h>

using std::cerr;

template<typename T>class allocator {
public:
	allocator() {}

	T* allocate(int n);					//为n个类型为T的对象分配空间
	void deallocate(T* p, int n);		//释放从p开始的n个类型为T的对象

	void construct(T* p, const T& v);	//在地址p构造一个值为v的T类型对象
	void destroy(T* p);					//销毁p中的T

};

template<typename T>
T* allocator<T>::allocate(int n)
{
	T* p = (T*)malloc(n * sizeof(T));
	if (p == NULL)
	{
		fprintf(stderr, "allocating fail\n");
		return nullptr;
	}
	return p;
}

template<typename T>
void allocator<T>::deallocate(T* p, int n)
{
	if (n < 0)
	{
		cerr << "deallocate fail: n can not be negative\n";
		return;
	}
	if (n == 0)
		return;
	free(p);
}

template<typename T>
void allocator<T>::construct(T* p, const T& v)
{
	new (p) T{ v };
}

template<typename T>
void allocator<T>::destroy(T* p)
{
	p->~T();
}

14.9

template<typename T, typename A>
vector<T, A>& vector<T, A>::operator=(const vector& arg)
{
	if (this == &arg)				//自赋值，什么也不用做
		;
	else if (arg.sz <= space)		//空间足够，无需分配空间
	{
		for (int i = 0; i < sz; ++i)
			alloc.destroy(elem + i);				//先销毁原来的元素
		for (int i = 0; i < arg.sz; ++i)
			alloc.construct(&elem[i], arg.elem[i]);	//拷贝元素
		sz = arg.sz;
	}
	else
	{
		T* p = alloc.allocate(arg.sz);
		for (int i = 0; i < arg.sz; ++i)
			alloc.construct(p + i, arg.elem[i]);	//拷贝元素
		alloc.deallocate(elem, space);
		sz = space = arg.sz;		//设置新大小
		elem = p;					//指向新元素的指针
	}
	return *this;					//按照惯例，赋值运算符将返回被赋值对象的引用
}