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

• 16.3 and 16.4, count, count_if
• 16.5
• 16.6
• 16.7 Binary Search
• 16.8 word frequency
• 16.9 and 16.10 读取Order的结构化输入，排序，合并两个容器
• 16.13 text clean
• 16.14 单词查询程序

#include
#include
#include

using std::cerr;
using std::cout;
using std::cin;
using std::vector;

inline std::default_random_engine& get_rand()
{
    static std::default_random_engine ran;	// note: not thread_local
    return ran;
};

inline int randint(int min, int max) { return std::uniform_int_distribution<>{min, max}(get_rand()); }

inline int randint(int max) { return randint(0, max); }

namespace Naive_STL
{
    template
    size_t count(Iter b, Iter e, const T& val)
    {
        size_t n{ 0 };
        while (b != e)
        {
            if (*b == val)
                ++n;
            ++b;
        }
        return n;
    }

    template
    size_t count_if(Iter b, Iter e, Pred pred)
    {
        size_t n{ 0 };
        while (b != e)
        {
            if (pred(*b))
                ++n;
            ++b;
        }
        return n;
    }
}

template
class Less_than {
	T val;
public:
	Less_than(T v) :val(v) { }
	bool operator()(const T& v) const { return v < val; }
};


template
class Greater_than {
	T val;
public:
	Greater_than(T v) :val(v) { }
	bool operator()(const T& v) const { return v > val; }
};


bool odd(int i) { return i % 2 != 0; }


void f1()
{
    vector vi;
    for (int i = 0; i < 50; ++i)
        vi.push_back(randint(50));
    cout << "vi:n";
    for (vector::iterator p = vi.begin(); p != vi.end(); ++p)
        cout << *p << 'n';
    cout << "Enter value for which you want to know the count, -1 to exit: ";
    int val;
    while (cin >> val) {
        if (val == -1) break;
        int ctr = Naive_STL::count(vi.begin(), vi.end(), val);
        cout << val << " is " << ctr << " time" << (ctr != 1 ? "s " : " ")
            << "in vi.nNext value: ";
    }
}

void f2()
{
    vector vi;
    for (int i = 0; i < 10; ++i)
        vi.push_back(randint(10));
    cout << "vi:n";
    for (vector::iterator p = vi.begin(); p != vi.end(); ++p)
        cout << *p << 'n';

    // Test Less_than function object
    cout << "Enter value for less than count, -1 to exit: ";
    int val;
    while (cin >> val) {
        if (val == -1) break;
        int ctr = Naive_STL::count_if(vi.begin(), vi.end(), Less_than(val));
        cout << "There " << (ctr == 1 ? "is " : "are ") << ctr << " value"
            << (ctr == 1 ? " " : "s ") << "less than " << val << " in vi.n"
            << "Next value: ";
    }

    // Test Greater_than function object
    cout << "Enter value for greater than count, -1 to exit: ";
    while (cin >> val) {
        if (val == -1) break;
        int ctr = Naive_STL::count_if(vi.begin(), vi.end(), Greater_than(val));
        cout << "There " << (ctr == 1 ? "is " : "are ") << ctr << " value"
            << (ctr == 1 ? " " : "s ") << "greater than " << val << " in vi.n"
            << "Next value: ";
    }

    // Test odd() function
    int ctr = Naive_STL::count_if(vi.begin(), vi.end(), odd);
    cout << "There are " << ctr << " odd values in vi.n";
}

int main()
try
{
    f1();
    f2();
    return 0;
}
catch (std::exception& e)
{
    cerr << "exception: " << e.what() << 'n';
}
catch (...)
{
    cerr << "exceptionn";
}

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


template
bool new_find(Iter b, Iter e, Iter& res, const T& v)
//这里的e是指向最后一个元素的迭代器，不是指向最后一个元素之后的迭代器了
{
	while (b != e)
	{
		if (*b == v)
		{
			res = b;
			return true;
		}
		++b;
	}
	//当b指向最后一个元素时，再进行一次判断
	if (*b == v)
	{
		res = b;
		return true;
	}
	return false;
}

template
size_t new_count(Iter b, Iter e, const T& v)
{
	size_t n{ 0 };
	while (b != e)
	{
		if (*b == v)
			++n;
		++b;
	}
	//当b指向最后一个元素时，再进行一次判断
	if (*b == v)
		++n;
	return n;
}

int main()
{
	vector vi;
	for (int i = 0; i < 10; ++i)
		vi.push_back(randint(10));

	typedef vector::iterator vi_it;

	cout << "vi:n";
	for (vi_it it = vi.begin(); it < vi.end(); ++it)
		cout << *it << 'n';

	cout << "Enter int to search for and count (-1 to quit): ";
	int n;
	while (cin >> n) {
		if (n == -1) break;
		bool is_found{ false };
		vi_it it_res;
		is_found = new_find(vi.begin(), vi.end() - 1, it_res, n);
		int count = new_count(vi.begin(), vi.end() - 1, n);
		if (!is_found) 
			cout << n << " is not in vi. Next int: ";
		else 
			cout << n << " is at index " << it_res - vi.begin()
			<< " (occurs " << count << " time" << (count == 1 ? "" : "s")
			<< "). Next int: ";
	}
	return 0;
}

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

struct Fruit {
	string name;
	int count;
	double unit_price;
};

struct Fruit_comparison {
	bool operator()(const Fruit* pa, const Fruit* pb) const
	{
		return pa->name < pb->name;
	}
};

ostream& operator<<(ostream& os, const Fruit* f)
{
    os << left << setw(16) << f->name << setw(16) << f->count
        << setw(16) << fixed << setprecision(2) << f->unit_price;
    return os;
}

int main()
try {
    set inventory;
    inventory.insert(new Fruit{ "Quince", 5 });    // test default parameter
    inventory.insert(new Fruit{ "Apple", 200, 0.37 });
    inventory.insert(new Fruit{ "Orange", 150, 0.45 });
    inventory.insert(new Fruit{ "Grape", 13, 0.99 });
    inventory.insert(new Fruit{ "Kiwi", 512, 1.1565 });
    inventory.insert(new Fruit{ "Plum", 750, 2.33 });

    for (auto p = inventory.begin(); p != inventory.end(); ++p) 
        cout << *p << 'n';

    for (auto p = inventory.begin(); p != inventory.end(); ++p)
        delete* p;

    return 0;
}
catch (runtime_error& e) 
{
    cerr << "exception: " << e.what() << endl;
}
catch (...) 
{
    cerr << "Exception occurredn";
}

自己实现的二分搜索，区分了随机迭代器和双向迭代器

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

//default sort standard '<' (less than)

// Random-Access-Iterator
template
bool my_bin_search_v1(RA_Iter left, RA_Iter right, const T& val)
//binary search val in [left, right)
{
	if (left == right)
		return false;
	RA_Iter mid = left + (right - left) / 2;
	if (*mid < val)
		return my_bin_search_v1(mid + 1, right, val);
	else if (*mid > val)
		return my_bin_search_v1(left, mid, val);
	else
		return true;
}

template
// Random-Access-Iterator
RA_Iter my_bin_search_ret_iter_v1(RA_Iter left, RA_Iter right, const T& val)
//binary search val in [left, right)
{
	RA_Iter not_found = right;
	RA_Iter mid;
	while (left != right)
	{
		mid = left + std::distance(left, right) / 2;	// set mid point to middle of sequence
		if (*mid < val)
			left = ++mid;
		else if (*mid > val)
			right = mid;
		else
			return mid;
	} 
	return not_found;
}


template
// Random-Access-Iterator
pair my_equal_range_v1(RA_Iter left, RA_Iter right, const T& val)
//binary search val in [left, right), return [b, e) pair what all elements are equal val
{
	RA_Iter b = right, e = right;

	//first find if val in [left, right)
	RA_Iter mid = my_bin_search_ret_iter_v1(left, right, val);
	if (mid != right)	//find it!
	{
		RA_Iter le = mid, ri = mid;

		// look for b
		do {
			mid = left;
			std::advance(mid, std::distance(left, ri) / 2);	// set mid point to middle of sequence
			if (*mid < val)
				left = ++mid;
			else
				ri = mid;
		} while (left != ri);
		b = left;

		//than look for e
		std::advance(le,1);
		do {
			mid = le;
			std::advance(mid, std::distance(le, right) / 2);	// set mid point to middle of sequence
			if (*mid > val)
				right = mid;
			else
				le = ++mid;
		} while (le != right);
		e = right;
	}

	return make_pair(b, e);
}





// Not Random-Access-Iterator

template
bool my_bin_search_v2(Iter left, Iter right, const T& val)
//binary search val in [left, right)
{
	if (left == right)
		return false;
	Iter mid = left;
	std::advance(mid, std::distance(left, right) / 2);	// set mid point to middle of sequence
	if (*mid < val)
		return my_bin_search_v2(++mid, right, val);
	else if (*mid > val)
		return my_bin_search_v2(left, mid, val);
	else
		return true;
}

template
Iter my_bin_search_ret_iter_v2(Iter left, Iter right, const T& val)
//binary search val in [left, right)
{
	Iter not_found = right;
	Iter mid;
	while (left != right)
	{
		mid = left;
		std::advance(mid, std::distance(left, right) / 2);	// set mid point to middle of sequence
		if (*mid < val)
			left = ++mid;
		else if (*mid > val)
			right = mid;
		else
			return mid;
	}
	return not_found;
}


template
pair my_equal_range_v2(Iter left, Iter right, const T& val)
//binary search val in [left, right), return [b, e) pair what all elements are equal val
{
	if (left == right)
		return make_pair(right, right);
	Iter b = right, e = right;
	Iter le, ri, mid;
	
	//first find if val in [left, right)
	mid = my_bin_search_ret_iter_v2(left, right, val);
	if (mid != right)	//find it!
	{
		le = ri = mid;
		
		// look for b
		do {
			mid = left;
			std::advance(mid, std::distance(left, ri) / 2);	// set mid point to middle of sequence
			if (*mid < val)
				left = ++mid;
			else
				ri = mid;
		} while (left != ri);
		b = left;

		//than look for e
		advance(le,1);
		do {
			mid = le;
			std::advance(mid, std::distance(le, right) / 2);	// set mid point to middle of sequence
			if (*mid > val)
				right = mid;
			else
				le = ++mid;
		} while (le != right);
		e = right;
	}
	return make_pair(b, e);
}


template
void print(Iter first, Iter last)
{
	while (first != last) {
		cout << *first << 'n';
		++first;
	}
}

int main()
try {
	// test for vector
	vector vi;
	for (int i = 0; i < 20; ++i)
	{
		vi.push_back(2 * i);
		vi.push_back(2 * i);
		vi.push_back(2 * i);
	}
	cout << "Vector:n";
	print(vi.begin(), vi.end());

	cout << "Enter int to find (-1 to exit): ";
	int i;
	while (cin >> i && i != -1) {
		cout << i << " is "
			<< (my_bin_search_v1(vi.begin(), vi.end(), i) ? "" : "not ")
			<< "in vi. n";
		auto section = my_equal_range_v1(vi.begin(), vi.end(), i);
		if (section.first != vi.end())
		{
			cout << "equal range:n";
			print(section.first, section.second);
		}
		cout << "Next int: ";
	}
	

	// test for list
	list li(vi.size());
	copy(vi.begin(), vi.end(), li.begin());
	cout << "nList:n";
	print(li.begin(), li.end());

	cout << "Enter int to find (-1 to exit): ";
	while (cin >> i && i != -1) {
		cout << i << " is "
			<< (my_bin_search_v2(li.begin(), li.end(), i) ? "" : "not ")
			<< "in li.n";
		auto section = my_equal_range_v2(li.begin(), li.end(), i);
		if (section.first != li.end())
		{
			cout << "equal range:n";
			print(section.first, section.second);
		}
		cout << "Next int: ";
	}

	
	return 0;
}
catch (runtime_error& e) 
{
	cerr << "exception: " << e.what() << endl;
}
catch (...) 
{
	cerr << "Exception occurredn";
}

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

用到的 Chrono (Date).h 和 Chrono (Date).cpp 参考第九章的答案，那里给出了源码，这里不再贴出

#include"../../std_lib_facilities.h"
#include"../../Ch09_ClassDetials/Ch09_Class/Chrono (Date).h"

//有一个经典的读取结构化数据的例题

using Chrono::Date;
using Chrono::Month;
using Chrono::Day;

static const string Order_marker{ "Order" };
static const string Name_marker{ "Name" };
static const string Address_marker{ "Address" };
static const string Date_marker{ "Date" };
static const string Purchase_marker{ "Purchase" };

void end_of_loop(istream& is, const char term, const string& msg);

struct Purchase {
	string name;
	int count;
	double unit_price;
};

//读入Purchase
istream& operator>>(istream& is, Purchase& pc)
{
	char ch = 0;
	if(is >> ch && ch != '{')
	{
		is.unget();
		is.clear(ios_base::failbit);	//读入结构化 Purchase 失败
		return is;
	}
	string nm;	// product name
	int cnt;	// count
	double up;	// unit_price
	
	
	while (is.get(ch) && isspace(ch))
		continue;
	do {
		nm += ch;
	} while (is.get(ch) && ch != '|');
	if (!is || ch != '|')
		error("bad Purchase record");
	while (nm.back() == ' ')
		nm.pop_back();
	
	char ch2;
	is  >> up >> ch >> cnt >> ch2;
	if(!is || ch != '|' || ch2 != '}')
		error("bad Purchase record");

	pc.name = nm;
	pc.count = cnt;
	pc.unit_price = up;
	return is;
}

//Purchase写出
ostream& operator<<(ostream& os, const Purchase& pc)
{
	os << "{ " << pc.name << " | " << pc.count 
		<< " | " << pc.unit_price << " }";
	return os;
}



class Order {
	string name;
	string addr;
	Date date;
	vector vpc;
public:
	Order() {}
	Order(const string& n, const string& a, const Date& d)
		:name{ n }, addr{ a }, date{ d }{}
	
	const string& get_name() const { return name; }
	const string& get_addr() const { return addr; }
	const Date& get_date() const { return date; }
	const vector& get_vpc() const { return vpc; }

	void set_name(const string& n) { name = n; }
	void set_addr(const string& a) { addr = a; }
	void set_date(const Date& d) { date = d; }
	void set_vpc(const vector& v) { vpc = v; }
};

//读入格式化字符串，用于读入Order::name 和 Order::addr
void read_format_string(istream& is, string& str, const string& marker)
{
	char ch = 0;
	if (is >> ch && ch != '(')
	{
		is.unget();
		is.clear(ios::failbit);
		return;
	}
	string flag, s;
	is >> flag;
	if (!is || flag != marker)
		error("bad start of ",marker);
	while (is.get(ch) && isspace(ch))
		continue;
	is.putback(ch);
	getline(is, s, ')');
	if (!is || s.empty())
	{
		error("bad Name reading");
		return;
	}
	while(s.back() == ' ')
		s.pop_back();		//去掉字符串最后的空格符
	str = s;
}


//读入Order::date
void read_format_date(istream& is, Date& date, const string& marker)
{
	char ch = 0;
	if (is >> ch && ch != '(')
	{
		is.unget();
		is.clear(ios::failbit);
		return;
	}
	string Date_flag;
	Date dd;
	is >> Date_flag;
	if (!is || Date_flag != marker)
		error("bad start of ", marker);
	is >> dd >> ch;
	if (!is || ch != ')')
		error("bad Date reading");
	date = dd;
}

//读入vector
void read_format_vpc(istream& is, vector& vpc, const string& marker)
{

	char ch = 0;
	is >> ch;
	if (ch != '(')
	{
		is.unget();
		is.clear(ios_base::failbit);	//读入结构化 Purchase 失败
		return;
	}

	string Purchase_flag;
	is >> Purchase_flag;
	if (!is || Purchase_flag != marker)
		error("bad start of ", marker);
	for (Purchase pc; is >> pc; )
		vpc.push_back(pc);

	end_of_loop(is, ')', "bad end of all Purchase records");
}

//读入Order
istream& operator>>(istream& is, Order& od)
{
	char ch = 0;
	is >> ch;
	if (ch != '{')
	{
		is.unget();
		is.clear(ios::failbit);
		return is;
	}
	string Order_flag;
	is >> Order_flag;
	if (!is || Order_flag != Order_marker)
		error("bad start of ", Order_marker);
	string nm, addr;
	Date dd;
	vector vpc;
	read_format_string(is, nm, Name_marker);
	read_format_string(is, addr, Address_marker);
	read_format_date(is, dd, Date_marker);
	read_format_vpc(is, vpc, Purchase_marker);
	od.set_name(nm);
	od.set_addr(addr);
	od.set_date(dd);
	od.set_vpc(vpc);
	is >> ch;
	if(!is || ch != '}')
		error("bad end of Order");
	return is;
}


//vector写出
ostream& operator<<(ostream& os, const vector& vpc)
{
	os << "t( " << Purchase_marker << 'n';
	for (const Purchase& pc : vpc)
		os << "tt" << pc << 'n';
	os << "t)";
	return os;
}

//Order写出
ostream& operator<<(ostream& os, const Order& od)
{
	os << "{ " << Order_marker << 'n';
	os << "t( " << Name_marker << ' ' << od.get_name() << " )n";
	os << "t( " << Address_marker << ' ' << od.get_addr() << " )n";
	os << "t( " << Date_marker << ' ' << od.get_date() << " )n";
	os << od.get_vpc() << 'n';
	os << '}';
	return os;
}

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


struct sort_by_name {
	bool operator()(const Order& od1, const Order& od2) const
	{
		return od1.get_name() < od2.get_name();
	}
};

struct sort_by_addr {
	bool operator()(const Order& od1, const Order& od2) const
	{
		return od1.get_addr() < od2.get_addr();
	}
};

template
struct price {
	T operator()(const T accu, const Purchase& pc) const
	{
		return accu + pc.count * pc.unit_price;
	}
};

template
struct price_all {
	T operator()(const T accu, const Order& od) const
	{
		T sum{ 0.0 };
		sum = accumulate(od.get_vpc().begin(), od.get_vpc().end(), sum, price{});
		//cout << "The sum of this order: " << sum << 'n';
		return accu + sum;
	}
};

template
void read_orders_from_file(const string& fname, C& c)
{
	ifstream ifs{ fname };
	if (!ifs)
		error(fname, "open failed");
	
	for (Order od; ifs >> od; )
		c.push_back(od);
}

template
void write_orders_to_file(const string& fname, C& c)
{
	ofstream ofs{ fname };
	if (!ofs)
		error(fname, "open failed");

	for (const Order& od : c)
		ofs << od << 'n';
}

template
//要求Iter指向Order
void write_orders_to_file(const string& fname, Iter b, Iter e)
{
	ofstream ofs{ fname };
	if (!ofs)
		error(fname, "open failed");

	while (b != e)
	{
		ofs << *b << 'n';
		++b;
	}
}

void merge_2files_to_file(const string& fname1, const string& fname2, const string& merge_to_fname)
{
	ifstream ifs1{ fname1 };
	if (!ifs1)
		error(fname1, "open failed");
	ifstream ifs2{ fname2 };
	if (!ifs2)
		error(fname2, "open failed");
	ofstream ofs{ merge_to_fname };
	if (!ofs)
		error(merge_to_fname, "open failed");

	istream_iterator ii1{ ifs1 };
	istream_iterator ii2{ ifs2 };
	istream_iterator eos;
	ostream_iterator oo{ ofs };

	merge(ii1, eos, ii2, eos, oo);
}

int main()
try
{
	//16_9

	string ifname1{ "16_9_input1.txt" };
	string ofname1{ "16_9_output1.txt" };
	vector vod;
	read_orders_from_file(ifname1, vod);
	sort(vod.begin(), vod.end(), sort_by_name{});
	write_orders_to_file(ofname1, vod);

	string ifname2{ "16_9_input2.txt" };
	string ofname2{ "16_9_output2.txt" };
	list lod;
	read_orders_from_file(ifname2, lod);
	lod.sort(sort_by_addr{});
	write_orders_to_file(ofname2, lod.begin(), lod.end());

	//merge 2 output files
	string ofname3{ "16_9_output3.txt" };
	vector vod_merge(vod.size()+lod.size());
	lod.sort(sort_by_name{});
	merge(vod.begin(), vod.end(), lod.begin(), lod.end(), vod_merge.begin(), sort_by_name{});
	write_orders_to_file(ofname3, vod_merge);

	//16_10
	double sum{ 0.0 };
	sum = accumulate(vod_merge.begin(), vod_merge.end(), sum, price_all{});
	cout << "The sum of all orders: " << sum << 'n';
	return 0;
}
catch (runtime_error& e) {
	cerr << "Runtime error: " << e.what() << endl;
	return 1;
}
catch (...) {
	cerr << "Exception occurred!n";
	return 2;
}

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

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

unsigned freq_of_word(const map& words, const string& w)
{
	auto fi = words.find(w);
	if (fi != words.end())
		return fi->second;
	else
		return 0;
}

const string& most_freq_word(const map& words)
{
	auto mfi = words.begin();
	for (auto it = words.begin(); it != words.end(); ++it)
		if (mfi->second < it->second)
			mfi = it;
	return mfi->first;
}

const string& longest_word(const map& words)
{
	auto mfi = words.begin();
	for (auto it = words.begin(); it != words.end(); ++it)
		if (mfi->first.size() < it->first.size())
			mfi = it;
	return mfi->first;
}

const string& shortest_word(const map& words)
{
	auto mfi = words.begin();
	for (auto it = words.begin(); it != words.end(); ++it)
		if (mfi->first.size() > it->first.size())
			mfi = it;
	return mfi->first;
}

vector search_prefix_word(const map& words, const string& prefix)
{
	vector vs;
	for (auto it = words.begin(); it != words.end(); ++it)
		if (equal(prefix.begin(),prefix.end(),it->first.begin()))
			vs.push_back(it->first);
	return vs;
}

vector search_size_word(const map& words, const unsigned sz)
{
	vector vs;
	for (auto it = words.begin(); it != words.end(); ++it)
		if (sz == it->first.size())
			vs.push_back(it->first);
	return vs;
}

int main()
try {
	//先声明在16.13中实现的text_clean()函数原型
	void text_clean(const string& fname, map& words);

	string fname;
	cout << "Input file name: ";
	cin >> fname;
	map words;
	text_clean(fname, words);

	std::cout << "'toddler' was used "
		<< freq_of_word(words, "toddler") << " timesn";

	std::cout << "the most frequently used word was: "
		<< most_freq_word(words) << 'n';

	std::cout << "the longest word was: "
		<< longest_word(words) << 'n';

	std::cout << "the shortest word was: "
		<< shortest_word(words) << 'n';

	vector starts_f = search_prefix_word(words, "f");

	std::cout << "All of the prefix 'f' words were:n";
	for (const auto& a : starts_f)
		std::cout << a << ' ';
	std::cout << 'n';

	vector fours = search_size_word(words, 4);
	std::cout << "There were " << fours.size() << " four-letter words:n";
	for (const auto& a : fours)
		std::cout << a << ' ';
	std::cout << 'n';

	return 0;
}
catch (runtime_error& e)
{
	std::cerr << "Runtime error: " << e.what() << 'n';
	return 1;
}
catch (...)
{
	std::cerr << "Exception occurredn";
	return 2;
}