C++程序设计原理与实践 习题答案 第二十六章 第26章习题答案

第二十六章：测试 习题答案

• 本章的BinarySearch
• • Binary_Search.h
• 26.2
• • 26.2 测试集
• 26.3
• 26.4
• 26.5
• 26.8 and 26.9
• • 26.8 测试集
• 26.11
• 26.12
• 26.13
• 26.14

本章的BinarySearch Binary_Search.h

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


template<typename Iter, typename T, typename BinOp = less<T>>
bool my_binary_search(Iter first, Iter last, const T& to_find, BinOp bin_cmp = BinOp{})
{
	//递归方法
	//if (first == last)	//last是指向end的
	//	return false;
	//Iter mid = first + distance(first, last) / 2;

	//if (*mid == to_find)
	//	return true;
	//else if (*mid < to_find)	//往右半部分搜索
	//	return my_binary_search(mid + 1, last, to_find, bin_cmp);
	//else
	//{
	//	往左半部分搜索
	//	return my_binary_search(first, mid, to_find, bin_cmp);
	//}

	//循环方法
	while (first < last)
	{
		Iter mid = first + distance(first, last) / 2;
		if ((bin_cmp(*mid, to_find) == false) && (bin_cmp(to_find, *mid) == false))
			return true;
		else if (bin_cmp(*mid, to_find))
		{
			//往右半部分搜索
			first = mid + 1;
		}
		else
		{
			//往左半部分搜索
			last = mid;
		}
	}
	return false;	//没搜到
}

26.2

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

template<class T>
struct Test {
	string label;		//唯一标签
	T val;			//要搜索的值
	vector<T> seq;	//数值序列
	bool res;			//期望的计算结果
};
//参考格式：{ 27 7 { 1 2 3 5 8 13 21 } 0 }，对应Test结构体顺序 （各字段之间需要有空格）

//读入格式化的各种类型序列 比如{ 1 2 3 5 8 13 21 } 的方法
template<class T>
istream& operator>>(istream& is, vector<T>& seq);

//终止输入循环，需要终止符号 term
void end_of_loop(istream& is, const char term, const string& err_msg);

template<class T>
istream& operator>>(istream& is, Test<T>& t)
{
	char ch1;
	is >> ch1;
	if (ch1 != '{')		//如果读入的不是'{'，说明不是读入测试集，可能是别的格式化字符串
	{
		is.unget();
		is.clear(ios::failbit);
		return is;
	}

	string lab;
	T v;
	vector<T> s;
	bool r;
	char ch2{ 0 };

	if (!(is >> lab >> v >> s >> r >> ch2))
		error("error in reading test case");
	if (ch2 != '}')
		error("bad end of test case");

	//成功读入后，要赋值给Test& t
	t.label = lab;
	t.val = v;
	t.seq = s;
	t.res = r;

	return is;
}

//读入格式化的各种类型序列(除了string) 比如{ 1 2 3 5 8 13 21 } 的方法
template<typename T>
istream& operator>>(istream& is, vector<T>& seq)
{
	char ch;
	if (is >> ch && ch != '{')
	{
		is.unget();
		is.clear(ios_base::failbit);
		return is;
	}

	T v;	//读入的将要放入向量的单个数值
	while (is >> v)
		seq.push_back(v);
	end_of_loop(is, '}', "bad termination of numeric sequence");

	
	return is;
}

//读入格式化的string序列，模板特例化
template<>
istream& operator>>(istream& is, vector<string>& seq)
{
	char ch;
	if (is >> ch && ch != '{')
	{
		is.unget();
		is.clear(ios_base::failbit);
		return is;
	}

	string v;	//读入的将要放入向量的单个数值
	while (is >> v)
	{
		if (v.back() == '}')
		{
			//is.putback('}');
			break;
		}
		seq.push_back(v);
	}
	
	return is;
}

void end_of_loop(istream& is, const char term, const string& err_msg)
{
	if (is.fail())
	{
		is.clear();
		char ch;
		if (is >> ch && ch == term)
			return;
		error(err_msg);
	}
}

//------------------------------------------------------------------------------

//格式化输出字符集
template<class T>
ostream& operator<<(ostream& os, const Test<T>& t)
{
	os << "{ "
		<< t.label << ' '
		<< t.val << ' '
		<< "{ ";
	for (const int x : t.seq)
		os << x << ' ';
	os << "} " << t.res << " }";

	return os;
}

//------------------------------------------------------------------------------

template<class T>
int test_all(istream& is)
{
	int error_count = 0;
	for (Test<T> t; is >> t; ) {
		bool r = my_binary_search(t.seq.begin(), t.seq.end(), t.val);

		if (r != t.res) {
			std::cout << "failure: test " << t.label
				<< " binary_search: "
				<< t.seq.size() << " elements, val == " << t.val
				<< " -> " << t.res << " != " << r << '\n';
			++error_count;
		}
	}
	return error_count;
}


//------------------------------------------------------------------------------

int main()
try {
	int err_cnt{ 0 };

	ifstream ifs{ "SimpleExercise_TestCase4.txt" };
	if (!ifs)
		error("can't open file SimpleExercise_TestCase4.txt");
	err_cnt = test_all<string>(ifs);
	cout << "error count = " << err_cnt << endl;
	ifs.close();

	return 0;
}
catch (exception& e)
{
	cerr << e.what() << endl;
	return 1;
}
catch (...)
{
	cerr << "Exception!\n";
	return 2;
}

26.2 测试集

{ 101.1 Bohr { Bohr Darwin Einstein Lavoisier Newton Turing } 1 }
{ 101.2 Einstein { Bohr Darwin Einstein Lavoisier Newton Turing } 1 }
{ 101.3 Lavoisier { Bohr Darwin Einstein Lavoisier Newton Turing } 1 }
{ 101.4 Turing { Bohr Darwin Einstein Lavoisier Newton Turing } 1 }
{ 101.5 Abel { Bohr Darwin Einstein Lavoisier Newton Turing } 0 }
{ 101.6 Dirichlet { Bohr Darwin Einstein Lavoisier Newton Turing } 0 }
{ 101.7 Watt { Bohr Darwin Einstein Lavoisier Newton Turing } 0 }

{ 102 Bohr { } 0 }

{ 103.1 Bohr { Bohr } 1 }
{ 103.2 Abel { Bohr } 0 }
{ 103.3 Einstein { Bohr } 0 }

{ 104.1 Bohr { Bohr Darwin Einstein Lavoisier } 1 }
{ 104.2 Lavoisier { Bohr Darwin Einstein Lavoisier } 1 }
{ 104.3 Darwin { Bohr Darwin Einstein Lavoisier } 1 }
{ 104.4 Einstein { Bohr Darwin Einstein Lavoisier } 1 }
{ 104.5 Abel { Bohr Darwin Einstein Lavoisier } 0 }
{ 104.6 Newton { Bohr Darwin Einstein Lavoisier } 0 }

{ 105.1 Bohr { Bohr Darwin Einstein Lavoisier Newton } 1 }
{ 105.2 Newton { Bohr Darwin Einstein Lavoisier Newton } 1 }
{ 105.3 Einstein { Bohr Darwin Einstein Lavoisier Newton } 1 }
{ 105.4 Abel { Bohr Darwin Einstein Lavoisier Newton } 0 }
{ 105.5 Turing { Bohr Darwin Einstein Lavoisier Newton } 0 }

{ 106.1 Bohr { Bohr Bohr Bohr Bohr Bohr } 1 }
{ 106.2 Abel { Bohr Bohr Bohr Bohr Bohr } 0 }
{ 106.3 Darwin { Bohr Bohr Bohr Bohr Bohr } 0 }

{ 107.1 Abel { Abel Bohr Bohr Bohr Bohr Bohr } 1 }
{ 107.2 Bohr { Abel Bohr Bohr Bohr Bohr Bohr } 1 }
{ 107.3 Aamodt { Abel Bohr Bohr Bohr Bohr Bohr } 0 }
{ 107.4 Darwin { Abel Bohr Bohr Bohr Bohr Bohr } 0 }

{ 108.1 Abel { Abel Abel Abel Abel Abel Bohr } 1 }
{ 108.1 Bohr { Abel Abel Abel Abel Abel Bohr } 1 }
{ 108.1 Aamodt { Abel Abel Abel Abel Abel Bohr } 0 }
{ 108.1 Darwin { Abel Abel Abel Abel Abel Bohr } 0 }

26.3

已在Binary_Search.h中实现

26.4

设计了一个数据格式，用 make_test_file() 生成测试集文件。

/*
定义一种测试数据格式，可以只需定义一次数据序列，但可在多个测试中使用
	
	{	lab1 [...]
		( lab2.x val res )
		( lab2.x val res )
		... 
	}

	{}内是数据序列和对应的各项测试，lab1表示数据序列的标签，[]内是数据序列
	()内是测试，其中lab2.x表示测试标签，val表示测试值，res表示测试结果
	注意括号以及各字段之间要有空格或换行符
*/


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


template<class T>
struct Test {
	string lab2x;		//标签：对应一个测试
	T val;			//要搜索的值
	bool res;			//期望的计算结果
};


template<class T>
struct Test_case {
	string lab1;		//标签：对应一个序列和针对它的测试
	vector<T> seq;		//数值序列
	vector<Test<T>> tests;	//各项测试，标签自动生成

	bool add_test(const T& val, const bool res);
};

template<class T>
bool Test_case<T>::add_test(const T& val, const bool res)
{
	//加入一项测试，自动添加标签
	auto it = find(seq.begin(), seq.end(), val);
	//判断要加入的测试是否正确
	if ((it != seq.end() && res == true) || (it == seq.end() && res == false))
	{
		//正确则加入
		Test<T> t;
		t.lab2x = lab1 + '.' + to_string(1 + tests.size());
		t.val = val;
		t.res = res;
		tests.push_back(t);		//加入该测试
		return true;
	}
	else
		return false;
}


//读入格式化的各种类型序列 比如{ 1 2 3 5 8 13 21 } 的方法
template<class T>
istream& operator>>(istream& is, vector<T>& seq);

//终止输入循环，需要终止符号 term
void end_of_loop(istream& is, const char term, const string& err_msg);

//读入测试
template<class T>
istream& operator>>(istream& is, Test<T>& t)
{
	char ch;
	is >> ch;
	if (ch != '(')		//如果读入的不是'('，说明不是读入测试，可能是别的格式化字符串
	{
		is.unget();
		is.clear(ios::failbit);
		return is;
	}

	string lab;
	T v;
	bool r;
	
	if (!(is >> lab >> v >> r >> ch))
		error("error in reading test");
	if (ch != ')')
		error("bad end of test");

	//成功读入后，要赋值给Test& t
	t.lab2x = lab;
	t.val = v;
	t.res = r;

	return is;
}

template<class T>
istream& operator>>(istream& is, Test_case<T>& tc)
{
	char ch;
	is >> ch;
	if (ch != '{')		//如果读入的不是'{'，说明不是读入测试集，可能是别的格式化字符串
	{
		is.unget();
		is.clear(ios::failbit);
		return is;
	}

	string lab;
	vector<T> s;
	
	if (!(is >> lab >> s))
		error("error in reading test case");
	//成功读入后，要赋值给Test_case& tc
	tc.lab1 = lab;
	tc.seq = s;

	//读入各项测试
	for (Test<T> t; is >> t;)
		tc.tests.push_back(t);
	end_of_loop(is, '}', "bad termination of test case");

	return is;
}

//读入格式化的各种类型序列(除了string) 比如{ 1 2 3 5 8 13 21 } 的方法
template<typename T>
istream& operator>>(istream& is, vector<T>& seq)
{
	char ch;
	if (is >> ch && ch != '[')
	{
		is.unget();
		is.clear(ios_base::failbit);
		return is;
	}

	T v;	//读入的将要放入向量的单个数值
	while (is >> v)
		seq.push_back(v);
	end_of_loop(is, ']', "bad termination of numeric sequence");


	return is;
}

//读入格式化的string序列，模板特例化
template<>
istream& operator>>(istream& is, vector<string>& seq)
{
	char ch;
	if (is >> ch && ch != '[')
	{
		is.unget();
		is.clear(ios_base::failbit);
		return is;
	}

	string v;	//读入的将要放入向量的单个数值
	while (is >> v)
	{
		if (v.back() == ']')
		{
			//is.putback('}');
			break;
		}
		seq.push_back(v);
	}

	return is;
}

void end_of_loop(istream& is, const char term, const string& err_msg)
{
	if (is.fail())
	{
		is.clear();
		char ch;
		if (is >> ch && ch == term)
			return;
		error(err_msg);
	}
}

//------------------------------------------------------------------------------

template<class T>
int test_all(istream& is)
{
	int error_count = 0;
	for (Test_case<T> tc; is >> tc; ) {
		cout << "Test " << tc.lab1 << '\n';
		for (const Test<T>& t : tc.tests)
		{
			bool r = my_binary_search(tc.seq.begin(), tc.seq.end(), t.val);

			if (r != t.res) {
				std::cout << "failure: test " << t.lab2x
					<< " binary_search: "
					<< tc.seq.size() << " elements, val == " << t.val
					<< " -> " << t.res << " != " << r << '\n';
				++error_count;
			}
		}
	}
	return error_count;
}


//生成随机数序列，并生成各项测试，最后输出到os
// n 随机数序列个数，m 测试项数，base 随机数序列的起始，spread 随机数之间的平均间距
void make_test_file(const string& lab, int n, int m, int base, int spread, ostream& os)
{
	os << "{ " << lab << " [ ";
	
	vector<int> v;
	int elem = base;
	
	for (int i = 0; i < n; ++i) {
		elem += randint(spread);
		v.push_back(elem);
		os << elem << ' ';
	}
	os << "]\n";
	
	for (int i = 0; i < m; ++i)
	{
		os << "\t( " << lab + '.' + to_string(1 + i);
		int val = randint(base, elem);
		os << ' ' << val;
		bool found = false;
		for (int i = 0; i < n; ++i) {
			if (v[i] == val) 
				found = true;
		}
		os << ' ' << found << " )\n";
	}
	os << "}\n\n";
}


//------------------------------------------------------------------------------

int main()
try {
	int err_cnt{ 0 };
	string fname{ "TestCase4.txt" };
	
	//ofstream ofs{ fname };
	//if (!ofs)
	//	error("can't open file ", fname);
	//make_test_file("1", 10, 5, 0, 5, ofs);
	//ofs.close();

	ifstream ifs{ fname };
	if (!ifs)
		error("can't open file ", fname);
	err_cnt = test_all<int>(ifs);
	cout << "error count = " << err_cnt << endl;
	ifs.close();

	return 0;
}
catch (exception& e)
{
	cerr << e.what() << endl;
	return 1;
}
catch (...)
{
	cerr << "Exception!\n";
	return 2;
}

26.5

题目的中文翻译似乎有误，第一句话应该是：在 binary_search 的测试中加入一个测试，（中文版是测试集中加入一个测试）。

//检查原书的测试用例数据序列

template<class T>
int test_all(istream& is)
{
	int error_count = 0;
	for (Test<T> t; is >> t; ) {
		
		//新加入一个测试，能够捕获 binary_search 修改数据序列这种错误
		auto before_binary_search_container = t.seq;

		bool r = my_binary_search(t.seq.begin(), t.seq.end(), t.val);

		if (r != t.res) {
			std::cout << "failure: test " << t.label
				<< " binary_search: "
				<< t.seq.size() << " elements, val == " << t.val
				<< " -> " << t.res << " != " << r << '\n';
			++error_count;
		}

		//新加入一个测试，能够捕获 binary_search 修改数据序列这种错误
		if (t.seq != before_binary_search_container)
			cout << "failure: test " << test.label
			<< " had its sequence modified\n";
	}
	return error_count;
}

26.8 and 26.9

其中26.9题就是在图形（以矩形为例）的draw_line()的最后加一句：

cout << "Rectangle(Point(" << point(0).x << ',' << point(0).y << "),"
	 << w << ',' << h << ")\n";

#include "../../std_lib_facilities.h"
#include "../../GUI/Simple_window.h"
#include

//其中26.9题就是在图形（以矩形为例）的draw_line()的最后加一句：
//cout << "Rectangle(Point(" << point(0).x << ',' << point(0).y << ")," << w << ',' << h << ")\n";

//-----------------------------------------------------------------------------

using namespace Graph_lib;

//-----------------------------------------------------------------------------

// read a point of format "Point(int x, int y)"
istream& operator>>(istream& is, Point& p)
{
    string s;
    char ch;
    while (is >> ch) {
        if (ch == '(')
            break;
        s += ch;
    }
    is.unget();
    
    if (s != "Point")
        error("expected 'Point'");
    char ch1;
    char ch2;
    char ch3;
    int x;
    int y;
    is >> ch1 >> x >> ch2 >> y >> ch3;
    if (ch1 != '(' || ch2 != ',' || ch3 != ')')
        error("expected '(', ',' or ')'");
    p = Point(x, y);
    return is;
}

//-----------------------------------------------------------------------------

// read contents of circle: "Point(int x, int y), int rad"
Circle* get_circle(istream& is)
{
    char ch1;
    Point p;
    char ch2;
    int rad;
    char ch3;
    is >> ch1 >> p >> ch2 >> rad >> ch3;
    if (ch1 != '(' || ch2 != ',' || ch3 != ')')
        error("get_circle(): expected '(', ',' or ')'");
    //is.ignore(numeric_limits::max(), '\n');  // ignore rest of line
    return new Circle(p, rad);
}

//-----------------------------------------------------------------------------

// read contents of line: "Point(int x1, int y1), Point(int x2, int y2)"
Line* get_line(istream& is)
{
    char ch1;
    char ch2;
    char ch3;
    Point p1;
    Point p2;
    is >> ch1 >> p1 >> ch2 >> p2 >> ch3;
    if (ch1 != '(' || ch2 != ',' || ch3 != ')')
        error("get_line(): expected '(', ',' or ')'");
    //is.ignore(numeric_limits::max(), '\n');
    return new Line(p1, p2);
}

//-----------------------------------------------------------------------------

// read contents of rectangle: "Point(int x, int y), int w, int h"
Graph_lib::Rectangle* get_rectangle(istream& is)
{
    char ch1;
    Point p;
    char ch2;
    int w;
    char ch3;
    int h;
    char ch4;
    is >> ch1 >> p >> ch2 >> w >> ch3 >> h >> ch4;
    if (ch1 != '(' || ch2 != ',' || ch3 != ',' || ch4 != ')')
        error("get_rectangle(): expected '(', ',' or ')'");
    //is.ignore(numeric_limits::max(), '\n');
    return new Graph_lib::Rectangle(p, w, h);
}

//-----------------------------------------------------------------------------

// returns a pointer to the next Shape extracted from is, null if no successful
Shape* get_shape(istream& is)
{
    string type;
    char ch;
    while (is >> ch) {
        if (ch == '(') {
            is.unget();
            break;
        }
        type += ch;
    }
    if (type == "Circle")
        return get_circle(is);
    if (type == "Line")
        return get_line(is);
    if (type == "Rectangle")
        return get_rectangle(is);
    else
        return 0;
}

//-----------------------------------------------------------------------------

int main()
try {
    Simple_window win(Point(400, 100), 800, 700, "My window");

    string ifname = "TestCase8.txt";
    ifstream ifs(ifname);
    if (!ifs)
        error("can't open ", ifname);
    Vector_ref<Shape> vec;
    while (true) {
        Shape* s = get_shape(ifs);
        if (s) {
            vec.push_back(s);
            win.attach(vec[vec.size() - 1]);
        }
        else
            break;
    }
    win.wait_for_button();
}
catch (exception& e) {
    cerr << e.what() << endl;
}
catch (...) {
    cerr << "exception \n";
}

26.8 测试集

Rectangle(Point(100,300),500,400)
Line(Point(100,300),Point(350,100))
Line(Point(350,100),Point(600,300))
Rectangle(Point(300,500),100,200)
Circle(Point(200,550),50)
Circle(Point(500,550),50)
Line(Point(150,550),Point(250,550))
Line(Point(200,500),Point(200,600))
Line(Point(450,550),Point(550,550))
Line(Point(500,500),Point(500,600))

26.11

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

using namespace Numeric_lib;
using namespace std::chrono;


// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
// 大神那里拷贝过来的填充随机矩阵多线程大法
// Multithreaded fill
void row_fill_task(Matrix<double, 2>& m, int r1, int r2, unsigned int seed)
{
    const int low = -10;
    const int high = 9;
    thread_local static default_random_engine ran{ seed };
    
    for (auto i = r1; i < r2; ++i)
        for (auto j = 0; j < m.dim2(); ++j)
            m(i, j) = randint(low, high);
}

Matrix<double, 2> threaded_fill(int dim)
{
    Matrix<double, 2> m{ dim, dim };

    const int N{ thread::hardware_concurrency() };      //线程数
    const int r = dim / N + ((dim % N) ? 1 : 0);
    vector<std::thread> vt;
    int M = m.dim1() - r;
    int i{ 0 };
    for (i = 0; i < M; i+=r)
        vt.push_back(std::thread{ row_fill_task, std::ref(m), i, i+r, randint(1,100) });
    vt.push_back(std::thread{ row_fill_task, std::ref(m), i, m.dim1(), randint(1,100) });
    for (auto& t : vt)
        t.join();

    return m;
}

//------------------------------------------------------------------------------
//慢方法
//------------------------------------------------------------------------------
double row_sum(Matrix<double, 2> m, int n)    // sum of elements in m[n]
{
    double s = 0;
    for (int i = 0; i < n; ++i) s += m(n, i);
    return s;
}
//------------------------------------------------------------------------------
double row_accum(Matrix<double, 2> m, int n)  // sum of elements in m[0:n)
{
    double s = 0;
    for (int i = 0; i < n; ++i) s += row_sum(m, i);
    return s;
}
//------------------------------------------------------------------------------

class Timer_Type {
public:
    Timer_Type() :t1{}, is_start{false}{}
    void start(const string& msg = "")
    {
        if (is_start)
        {
            cerr << "clock had been starting!\n";
            return;
        }
        is_start = true;
        cout << msg << " clock start!\n";
        t1 = system_clock::now();
    }

    void terminate(const string& msg = "")
    {
        is_start = false;
        auto t2 = system_clock::now();
        cout << msg << " took "
            << duration_cast<milliseconds>(t2 - t1).count()
            << " milliseconds\n";
    }

private:
    system_clock::time_point t1;
    bool is_start;  //是否开始计时
};

int main()
try
{
    const int N{ 10000 };     //方阵的维度
    Matrix<double, 2> m = threaded_fill(N);

    vector<double> v;
    Timer_Type timer;

    // compute accumulated sums of rows of m: (slow)
    //timer.start("Slow method");
    //for (int i = 0; i < m.dim1(); ++i) 
    //    v.push_back(row_accum(m, i + 1));
    //timer.terminate("Slow method");

    // compute accumulated sums of rows of m: (faster)
    double rows_acc{ 0 };
    timer.start("Faster method");
    for (int i = 0; i < m.dim1(); ++i)
    {
        rows_acc += row_sum(m, i);
        v.push_back(rows_acc);
    }
    timer.terminate("Faster method");
    cout << v.back() << '\n';

    return 0;
}
catch (exception& e)
{
    cerr << "Exception: " << e.what() << endl;
    return 1;
}
catch(...)
{
    cerr << "Exception occurred!\n";
    return 2;
}

26.12

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

using namespace std::chrono;

// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
// Multithreaded fill
void vector_fill_task(vector<double>& v, vector<double>::size_type i1, vector<double>::size_type i2, default_random_engine ran)
{
    constexpr int min = 0;
    constexpr int max = 1000;
    
    thread_local uniform_real_distribution<> ureal{ min,max };

    for (auto i = i1; i < i2; ++i)
        v[i] = ureal(ran);
}

vector<double> random_vector_double(vector<double>::size_type n, const unsigned seed)
{
    default_random_engine ran{ seed };
    const int N_thread{ thread::hardware_concurrency() };
    const int r = n / N_thread + ((n % N_thread) ? 1 : 0);
  
    vector<double> v(n);
    vector<std::thread> vt;
    int M = n - r;
    int i{ 0 };
    for (i = 0; i < M; i += r)
        vt.push_back(std::thread{ vector_fill_task, ref(v), i, i + r, ran });
    vt.push_back(std::thread{ vector_fill_task, ref(v), i, n, ran });
    for (auto& t : vt)
        t.join();

    return v;
}

//------------------------------------------------------------------------------

class Timer_Type {
public:
    Timer_Type() :t1{}, is_start{ false }{}
    void start(const string& msg = "")
    {
        if (is_start)
        {
            cerr << "clock had been starting!\n";
            return;
        }
        is_start = true;
        cout << msg << " clock start!\n";
        t1 = system_clock::now();
    }

    void terminate(const string& msg = "")
    {
        is_start = false;
        auto t2 = system_clock::now();
        cout << msg << " took "
            << duration_cast<milliseconds>(t2 - t1).count()
            << " milliseconds\n";
    }

private:
    system_clock::time_point t1;
    bool is_start;  //是否开始计时
};


void check_vector(vector<double> v, const string& title)
{
    if (v.size() == 0)
    {
        cout << "vector is empty\n";
        return;
    }
    cout << title << endl;
    cout << "begin\t\tmid\t\tend\n";
    cout << setprecision(8) << v[0] << '\t' << *(v.begin() + distance(v.begin(), v.end()) / 2) << '\t' << v.back() << endl;
}

int main()
try
{
    const int N1{ 500000 };     //浮点数的数量
    const int N2{ 5000000 };
    

    vector<double> v1 = random_vector_double(N1, N1);
    vector<double> v2 = random_vector_double(N2, N2);

    Timer_Type timer;
    
    check_vector(v1, "v1 before sort");
    check_vector(v2, "v2 before sort");

    timer.start("N = 500 000");
    sort(v1.begin(), v1.end());
    timer.terminate("N = 500 000");
    
    timer.start("N = 5 000 000");
    sort(v2.begin(), v2.end());
    timer.terminate("N = 5 000 000");

    check_vector(v1, "v1 after sort");
    check_vector(v1, "v2 after sort");

    return 0;
}
catch (exception& e)
{
    cerr << "Exception: " << e.what() << endl;
    return 1;
}
catch (...)
{
    cerr << "Exception occurred!\n";
    return 2;
}

26.13

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


using namespace std::chrono;


// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
// Multithreaded fill

//返回随机字符串，用户指定长度
string rand_string(int len)
{
    if (len <= 0)
        return "";

    //以ascii的26个小写字母作为随机字符串的字符
    constexpr int litter_min = 97;
    constexpr int litter_max = 122;
    thread_local static std::default_random_engine ran;
    thread_local uniform_int_distribution<> uint_char{ litter_min, litter_max };
    stringstream ss;
    for (auto i = 0; i < len; ++i)
        ss << static_cast<char>(uint_char(ran));

    return ss.str();
}
void vector_fill_task(vector<string>& v, vector<string>::size_type i1, vector<string>::size_type i2, default_random_engine ran)
{
    constexpr int len_min = 0;
    constexpr int len_max = 99;

    uniform_int_distribution<> uint{ len_min, len_max };

    for (auto i = i1; i < i2; ++i)
        v[i] = rand_string(uint(ran));  //获得随即长度[0:100)的随机字符串
}

vector<string> random_vector_string(vector<double>::size_type n, const unsigned seed)
{
    default_random_engine ran{ seed };
    const auto N_thread{ thread::hardware_concurrency() };
    const int r = n / N_thread + ((n % N_thread) ? 1 : 0);

    vector<string> v(n);
    vector<std::thread> vt;
    int M = n - r;
    int i{ 0 };
    for (i = 0; i < M; i += r)
        vt.push_back(std::thread{ vector_fill_task, ref(v), i, i + r, ran });
    vt.push_back(std::thread{ vector_fill_task, ref(v), i, n, ran });
    for (auto& t : vt)
        t.join();

    return v;
}

//------------------------------------------------------------------------------

class Timer_Type {
public:
    Timer_Type() :t1{}, is_start{ false }{}
    void start(const string& msg = "")
    {
        if (is_start)
        {
            cerr << "clock had been starting!\n";
            return;
        }
        is_start = true;
        cout << msg << " clock start!\n";
        t1 = system_clock::now();
    }

    void terminate(const string& msg = "")
    {
        is_start = false;
        auto t2 = system_clock::now();
        cout << msg << " took "
            << duration_cast<milliseconds>(t2 - t1).count()
            << " milliseconds\n";
    }

private:
    system_clock::time_point t1;
    bool is_start;  //是否开始计时
};


void check_vector(vector<string> v, const string& title)
{
    if (v.size() == 0)
    {
        cout << "vector is empty\n";
        return;
    }
    cout << title << '\n';
    cout << "begin:\n";
    cout << v[0] << '\n';
    cout << "mid:\n";
    cout << v[v.size()/2] << '\n';
    cout << "end:\n";
    cout << v.back() << '\n';
}

int main()
try
{
    const int N1{ 500000 };     //浮点数的数量
    const int N2{ 5000000 };


    vector<string> v1 = random_vector_string(N1, N1);
    vector<string> v2 = random_vector_string(N2, N2);

    Timer_Type timer;

    check_vector(v1, "v1 before sort");
    check_vector(v2, "v2 before sort");

    timer.start("N = 500 000");
    sort(v1.begin(), v1.end());
    timer.terminate("N = 500 000");

    timer.start("N = 5 000 000");
    sort(v2.begin(), v2.end());
    timer.terminate("N = 5 000 000");

    check_vector(v1, "v1 after sort");
    check_vector(v1, "v2 after sort");

    return 0;
}
catch (exception& e)
{
    cerr << "Exception: " << e.what() << endl;
    return 1;
}
catch (...)
{
    cerr << "Exception occurred!\n";
    return 2;
}

26.14

//
// Stroustrup - Programming Principles & Practice
//
// Chapter 26 Exercise 14
//
// Repeat random string container fill using map so the sequences are already
// sorted. I used a set instead since there wasn't really a 'pair'.
//

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

using namespace std::chrono;

std::mutex mtx;                     // where is the best place for this?

// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
// Timing
class Make_timer {
public:
    Make_timer() : t1{ system_clock::now() } { }

    void reset() { t1 = system_clock::now(); }

    void operator()(const std::string& label)
    {
        auto t2 = system_clock::now();
        std::cout << "  " << label << " took: "
            << duration_cast<microseconds>(t2 - t1).count()
            << " microseconds\n";
    }
private:
    system_clock::time_point t1;
};

// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
// Random string generation
std::string get_string()
{
    constexpr unsigned int min = 1;         // smallest string
    constexpr unsigned int max = 100;       // largest string
    constexpr unsigned short low = 33;      // low end of char-range
    constexpr unsigned short high = 126;    // high end of char-range

    std::stringstream ss;

    thread_local static std::default_random_engine ran;

    auto len = std::uniform_int_distribution<>{ min, max }(ran);

    for (auto i = 0; i < len; ++i)
        ss << static_cast<char>(uniform_int_distribution<>{low, high}(ran));

    return ss.str();
}

template<typename C> C random_fill(int n)
{
    C vs;
    for (auto i = 0; i < n; ++i)
        vs.insert(get_string());
    return vs;
}

// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
// Multi-threading  fill-set
void fill_task(std::set<std::string>& vs, int n, std::mutex& m)
{
    set<std::string> v = random_fill<std::set<std::string>>(n);

    std::unique_lock<std::mutex> lck{ m };
    for (const auto& a : v)
        vs.insert(a);
}

set<std::string> threaded_fill(int n)
// fill a large set with random strings
// thread number performance:
// 1: ~107
// 4: ~32s
// 8: ~28s
{
    std::set<std::string> vs;

    constexpr int num_threads = 8;

    std::mutex mtx;
    vector<std::thread> vt;            // still using vector for threads
    for (auto i = 0; i < num_threads; ++i)
        vt.push_back(std::thread{ fill_task,
                                 std::ref(vs),
                                 n / num_threads,
                                 std::ref(mtx) });

    for (auto& t : vt)
        t.join();

    return vs;
}

// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
// Multi-threading  fill-vector
//返回随机字符串，用户指定长度
string rand_string(int len)
{
    if (len <= 0)
        return "";

    //以ascii的26个小写字母作为随机字符串的字符
    constexpr int litter_min = 97;
    constexpr int litter_max = 122;
    thread_local static std::default_random_engine ran;
    thread_local uniform_int_distribution<> uint_char{ litter_min, litter_max };
    stringstream ss;
    for (auto i = 0; i < len; ++i)
        ss << static_cast<char>(uint_char(ran));

    return ss.str();
}
void vector_fill_task(vector<string>& v, vector<string>::size_type i1, vector<string>::size_type i2, default_random_engine ran)
{
    constexpr int len_min = 0;
    constexpr int len_max = 99;

    uniform_int_distribution<> uint{ len_min, len_max };

    for (auto i = i1; i < i2; ++i)
        v[i] = rand_string(uint(ran));  //获得随即长度[0:100)的随机字符串
}

vector<string> random_vector_string(vector<double>::size_type n, const unsigned seed)
{
    default_random_engine ran{ seed };
    const auto N_thread{ thread::hardware_concurrency() };
    const int r = n / N_thread + ((n % N_thread) ? 1 : 0);

    vector<string> v(n);
    vector<std::thread> vt;
    int M = n - r;
    int i{ 0 };
    for (i = 0; i < M; i += r)
        vt.push_back(std::thread{ vector_fill_task, ref(v), i, i + r, ran });
    vt.push_back(std::thread{ vector_fill_task, ref(v), i, n, ran });
    for (auto& t : vt)
        t.join();

    return v;
}

// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
// Utility
template<typename C>
void check_output(const C& c)
{
    std::cout << "first element: " << c.front() << '\n'
        << "last element: " << '\n'
        << c.back() << '\n';
}

// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
int main()
try {
    const int test1 = 500000;
    const int test2 = 5000000;

    Make_timer timer;

    std::cout << "Filling both sets...\n";
    timer.reset();
    set<string> s1 = threaded_fill(test1);
    set<string> s2 = threaded_fill(test2);
    timer("set fills");

    std::cout << "Filling and sorting both vectors...\n";
    timer.reset();
    vector<string> v1 = random_vector_string(test1, test1);
    vector<string> v2 = random_vector_string(test2, test2);
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
    timer("vector fills and sorts");
    
    return 0;
}
catch (std::exception& e) {
    std::cerr << "Exception: " << e.what() << '\n';
    return 1;
}
catch (...) {
    std::cerr << "Unknown exception\n";
    return 2;
}