Accelerated C++学习笔记7—<使用库算法>

第6章  使用库算法

本章中主要教我们怎样使用几个库算法来解决与处理字符串和学生成绩相关的问题。

1、分析字符串

使用一个循环来连接两幅字符图案

<span style="font-family:KaiTi_GB2312;">for(vector<string>::const_iterator it = bottom.begin(); it != bottom.end(); ++it)
ret.push_back(*it);</span></span>

等价于

<span style="font-family:KaiTi_GB2312;">ret.insert(ret.end(), bottom.begin(), bottom.end());</span></span>

也等价于

<span style="font-family:KaiTi_GB2312;">copy(bottom.begin(), bottom.end(), back_inserter(ret));</span></span>

分析：这里指的是复制了bottom中的全部的元素而且把它们加入到ret的末尾。

在这个函数借宿之后。ret的长度将加入bottom.size()。

补充：back_inserter(c) 对容器c产生一个迭代器，这个迭代器会给c加入元素。这个容器必须支持链表，向量以及字符串类型都会支持push_back操作。

copy(b, e, d) 把[b,e)所指示的系列拷贝到由d指示的目的地中。

2、实现split的方法

<span style="font-family:KaiTi_GB2312;">//假设參数是空白区域则为true。否则为false
bool space(char c)
{
	return isspace(c);
}

//假设參数是空白区域则为false。否则为true
bool not_space(char c)
{
	return !isspace(c);
}

vector<string> split(const string& str)
{
	typedef string::const_interator iter;
	vector<string> ret;

	iter != str.begin();
	while(i != str.end())
	{
		//忽略前端空白
		i = find_if(i, str.end(), not_space);

		//找到下一个单词的结尾
		iter j = find_if(i, str.end(), space);

		//复制在[i,j)中的字符
		if(i != str.end())
			ret.push_back(string(i,j));
		i = j;
	}
	return ret;
}</span></span>

补充：

find_if(b,e,p)  依据谓词p来检查每个元素；find(b,e,t) 在序列中查找一个特定值的算法。

3、回文

回文就是顺读和逆读都一样的单词。

<span style="font-family:KaiTi_GB2312;">// lesson6.2.cpp : 定义控制台应用程序的入口点。
//功能：推断回文
//2014.5.22

#include "stdafx.h"
#include <algorithm>
#include <cctype>
#include <iostream>
#include <string>

using namespace std;

bool is_palindrome(const string& s)
{
  return equal(s.begin(), s.end(), s.rbegin());
}

int _tmain(int argc, _TCHAR* argv[])
{
	string s;
  while (cin >> s)
  {
    if (is_palindrome(s))
      cout << s << " is a palindrome" << endl;
    else
      cout << s << " is not a palindrome" << endl;
  }
	return 0;
}</span></span>

执行结果：

程序分析：rbegin返回一个迭代器。这个迭代器会从容器的最后一个元素開始。而且从后向前地逆向訪问容器。

4、查找URL

一个URL（统一资源地址）的字符序列：protocol-name://resource-name

主函数：

<span style="font-family:KaiTi_GB2312;">// lesson6_1.cpp : 定义控制台应用程序的入口点。
//功能：查找URL
//时间：2014.5.22

#include "stdafx.h"
#include <algorithm>
#include <cctype>
#include <iostream>
#include <string>
#include <vector>

#include "urls.h"

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
	string s;
	while (getline(cin,s))
	{
		vector<string> v = find_urls(s);
		for(vector<string>::const_iterator i = v.begin(); i != v.end(); ++i)
			cout << *i << endl;
	}
	return 0;
}
</span></span>

程序分析：getline(is,s) 从is读一行输入并把它储存在s中
urls头文件：

<span style="font-family:KaiTi_GB2312;">#ifndef GUARD_urls_h
#define GUARD_urls_h

#include <vector>
#include <string>

std::vector<std::string> find_urls(const std::string& s);

#endif</span></span>

urls源文件：

<span style="font-family:KaiTi_GB2312;">#include <algorithm>
#include <cctype>
#include <string>
#include <vector>

#include "urls.h"

using std::find;
using std::find_if;

#ifndef _MSC_VER
using std::isalnum;
using std::isalpha;
using std::isdigit;
#endif

using std::search;
using std::string;
using std::vector;

bool not_url_char(char);

string::const_iterator
url_end(string::const_iterator, string::const_iterator);

string::const_iterator
url_beg(string::const_iterator, string::const_iterator);

vector<string> find_urls(const string& s) 
{
  vector<string> ret;
  typedef string::const_iterator iter;
  iter b = s.begin(), e = s.end();

  // 检查整个输入
  while (b != e) 
  {
    // 查找一个或多个紧跟://的字母
    b = url_beg(b, e);

    // 假设查找成功
    if (b != e) 
	{
      // 获取URL的其余部分
      iter after = url_end(b, e);

      // 记住这个URL
      ret.push_back(string(b, after));

      // 将b向前推进并查找位于本行中的其它的URL
      b = after;
    }
  }

  return ret;
}

//调用url_end目的是为了找出这个URL的结尾
string::const_iterator
url_end(string::const_iterator b, string::const_iterator e) 
{
  return find_if(b, e, not_url_char);
}

//编写这个not_url_char的谓词
bool not_url_char(char c) {
  // 除去字母数字之外，其它有可能出如今一个URL中的字符
  static const string url_ch = "~;/?
:@=&$-_.+!*'(),";

  // 看c是否出如今一个URL并返回求反的结果
  return !(isalnum(c) || find(url_ch.begin(), url_ch.end(), c) != url_ch.end());

  //补充：isalnum函数是检验它的參数是否是一个字母数字字符（一个字母或者一个数字）
}

//负责识别是否有一个有效的URL,我们必须保证在://分隔符之前有一个或多个的字母。并且在它的后面至少有一个字符。
string::const_iterator
url_beg(string::const_iterator b, string::const_iterator e) 
{
  static const string sep = "://";

  typedef string::const_iterator iter;

  // `i' 标记了查找到的分隔符的位置
  iter i = b;

  while ((i = search(i, e, sep.begin(), sep.end())) != e) 
  {
      //确保切割符不是本行中唯一的一个符号
    if (i != b && i + sep.size() != e)
	{

      // `beg标记协议名称的开关
      iter beg = i;
      while (beg != b && isalpha(beg[-1])) //isalpha 推断不是字母
	   --beg;

      // 在分隔符前面以及后面至少有一个字符吗？
      if (beg != i && !not_url_char(i[sep.size()]))
	return beg;
    }

    //我们找到的分隔符不是一个URL的一部分
	if(i != e)
    i += sep.size();
  }

  return e;
}</span></span>

执行结果：

程序分析：

1）isalnum函数是检验它的參数是否是一个字母数字字符（一个字母或者一个数字）；

2）isalpha 推断不是字母。

3）search(b,e,b2,e2) 在序列[b,e)中查找一个特定的算法，查找由[b2,e2)所指示的序列。

6、对计算成绩的方案进行比較

编敲代码解决以下两个不同的问题：

1）读所有学生的记录。把做了所有家庭作业的学生与其它的学生分隔开

2）对每一组中的全部学生分别使用每个的计算成绩的方案，报告每一组的中值成绩。

主函数：

<span style="font-family:KaiTi_GB2312;">// lesson6_3.cpp : 定义控制台应用程序的入口点。
//功能：计算成绩
//时间：2014.5.22

#include "stdafx.h"
#include <vector>
#include <iostream>

#include "analysis.h"
#include "Student_info.h"

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
	//做以及没做家庭作业的学生
	vector<Student_info> did,didnt;

	//读入学生记录并划分他们
	Student_info student;
	while(read(cin,student))
	{
		if(did_all_hw(student))
			did.push_back(student);
		else
			didnt.push_back(student);
	}

	//证实这些分析将向我们出示某些结果
	if(did.empty())
	{
		cout << "No student did all the homework!" << endl;
		return 1;
	}
	if(didnt.empty())
	{
		cout << "Every student did all the homework!" << endl;
		return 1;
	}

	//进行分析
	write_analysis(cout, "median", median_analysis, did, didnt);
	write_analysis(cout, "average", average_analysis, did, didnt);
	write_analysis(cout, "median of homework turned in", optimistic_median_analysis, did, didnt);

	return 0;
}</span></span>

简单检查一个学生是否做个全部的家庭作业：

<span style="font-family:KaiTi_GB2312;">#include <algorithm>

#include "Student_info.h"

using namespace std;

//函数的目的就是查找储存在里面的全部值中是否有为0的
bool did_all_hw(const Student_info& s)
{
	return((find(s.homework.begin(), s.homework.end(), 0)) == s.homework.end());
}</span></span>

不同的分析函数：

<span style="font-family:KaiTi_GB2312;">//功能：分析
//时间：2014.5.22
#include <slgorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <stdexcept>
#include <vector>

#include "Student_info.h"
#include "grade.h"
#include "median.h"

using namespace std;

//建立一个辅助函数在grade内运行try语句而且处理异常
double grade_aux(const Student_info& s)
{
	try
	{
		return grade(s);
	}
	catch(domain_error)
	{
		return grade(s.midterm, s.final, 0)
	}
}
//median_analysis
double median_analysis(const vector<Student_info>& students) 
{
  vector<double> grades;

  transform(students.begin(), students.end(),back_inserter(grades), grade_aux);

  return median(grades);
}

//使用一个分析例程来比較两个学生数据的集合
void write_analysis(ostream& out, const string& name, double analysis(const vector<Student_info>&), const vector<Student_info>& did, const vector<Student_info>& didnt)
{
	out << name << ": median(did) = " << analysis(did) << ",median(didnt) = " << analysis(didnt) << endl;
}

//计算家庭作业的平均成绩
double average(const vector<double>& v)
{
	return accumulate(v.begin(), v.end(), 0.0) / v.size();  //这里一定要注意用0.0这样求出的值才不会丢了小数点部分
}

//计算总成绩
double average_grade(const Student_info& s)
{
	return grade(s.midterm, s.final, average(s.homework));
}

//平均函数分析
double average_analysis(const vector<Student_info>& students)
{
	vector<double> grades;

	transform(students.begin(), students.end(), back_inserter(grades), average_grade);

	return median(grades);
}

//上交家庭作业的中值,s.homework的非零元素的中值，假设没有这种元素存在的话。则为0
double optimistic_median(const Student_info& s)
{
	vector<double> nonzero;
	remove_copy(s.homework.begin(), s.homework.end(), back_inserter(nonzero),0);

	if(nonzero.empty())
		return grade(s.midterm, s.final, 0);
	else
		return grade(s.midterm, s.final, median(nonzero));
}

//optimistic_median_analysis
double optimistic_median_analysis(const vector<Student_info>& students)
{
	vector<double> grades;

	transform(students.begin(),students.end(), back_inserter(grades), optimistic_median);

	return median(grades);
}
</span></span>

程序分析：

1）accumulate(b,e,t)                 把区间[b,e)中的元素的总和加上t之后储存在t中，是在<numeric>中定义的。

2）find(b,e,t)                       在序列[b,e)中查找值t;

3）find_if(b,e,p)                    在序列[b,e)中依据谓词p来检查每个元素。

4）search(b,e,b2,e2)                 在序列[b,e)中查找一个特定的算法。查找由[b2,e2)所指示的序列；

5）copy(b,e,d)                       把序列[b,e)拷贝到由d指示的目的地中，复制整个序列；

6）remove_copy(b,e,d,t)              把序列[b,e)中全部不等于t的元素拷贝到由d指示的目的地中；

7）remove_copy_if(b,e,d,t)           把序列[b,e)中全部使谓词p为假的元素拷贝到由d指示的目的地中；

8）remove_if(b,e,p)                  使在区间[b,e)中使谓词p为假的元素位于这个域的头部，返回一个迭代器，这个迭代器指示了位于那些不被删除的元素之后的那个位置

9）remove(b,e,t)                     作用和上面那个一样，可是检測了哪些元素值不等于t；

10）transform(b,e,d,f)               依据域[b,e)中的元素执行函数f，把f的结果存储在d中；  

7、对学生进行分类并回想下我们的问题

1）使用两次传递的解决方式

<span style="font-family:KaiTi_GB2312;">#include <algorithm>
#include <iterator>
#include <vector>

#include "Student_info.h"
#include "grade.h"

using namespace std;

vector<Student_info> extract_fails(vector<Student_info>& students)
{
	vector<Student_info> fail;
	remove_copy_if(students.begin(), students.end(),back_inserter(fail),pgrade);

	students.erase(remove_if(students.begin(),students.end(), fgrade)， students.end());

	return fail;
}</span></span>

这里计算了两次成绩。所以须要改进

2）一种一次传递的解决方式

<span style="font-family:KaiTi_GB2312;">#include <algorithm>
#include <vector>

#include "Student_info.h"
#include "grade.h"

using std::stable_partition;
using std::vector;

vector<Student_info> extract_fails(vector<Student_info>& students)
{
   vector<Student_info>::iterator iter = stable_partition(students.begin(), students.end(), pgrade);
   vector<Student_info> fail(iter, students.end());
   students.erase(iter, students.end());

   return fail;
}</span></span>

程序分析：

1）partition(b,e,p)    以谓词p为基础从而划分在域[b,e)中的元素以使那些使谓词为真的元素处于容器的头部。

返回一个迭代器，这个迭代器指示了第一个令谓词为假的元素；

2）stable_partition(b,e,p)  会让在每个区域内的元素的输入顺序保持不变  

8、以下的这个程序片段做什么的？

<span style="font-family:KaiTi_GB2312;">vector<int> u(10,100);
vector<int> v;
copy(u.begin(), u.end(), v.begin());</span>

编写一个包括这个片段的程序并编译以及执行这个程序。

方法一：

<span style="font-family:KaiTi_GB2312;">// lesson6_5_1.cpp : 定义控制台应用程序的入口点。

//改进上面方法：利用迭代适配器,循环
//时间：2014.5.24

#include "stdafx.h"
#include <algorithm>
#include <iterator>
#include <vector>

using namespace std;


int _tmain(int argc, _TCHAR* argv[])
{
	vector<int> u(10,100);
	vector<int> v;

	copy(u.begin(),u.end(),inserter(v,v.begin()));
	return 0;
}</span>

方法二：

<span style="font-family:KaiTi_GB2312;">// lesson6_5_2.cpp : 定义控制台应用程序的入口点。
//改进：使用最初的循环来做
//时间：2014.5.24

#include "stdafx.h"
#include <algorithm>
#include <vector>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
	vector<int> u(10, 100);
	vector<int> v;
	
	for(vector<int>::const_iterator it = u.begin(); it != u.end(); ++it)
		v.push_back(*it);
	return 0;
}
</span>

程序说明：vector<int> u(10,100)定义了一个vector u，该vector中存有10个100。将u中的元素通过copy函数所有拷贝到v。

9、计算成绩的分析程序的一部分功能是读入学生记录并对其进行分类。这一部分程序依赖于学生是否做了所有的家庭作业，这个问题和extract_fails中所须要解决的类似

<span style="font-family:KaiTi_GB2312;">// lesson6_6.cpp : 定义控制台应用程序的入口点。
//功能：计算成绩的分析程序的一部分功能是读入学生记录并对其进行分类。这一部分程序依赖于学生是否做了所有的家庭作业，这个问题和extract_fails中所须要解决的相似
//时间：2014.5.24

#include "stdafx.h"
#include <vector>
#include <iostream>

#include "analysis.h"
#include "Student_info.h"

using namespace std;

//分类问题
vector<Student_info> extract_didnt(vector<Student_info>& input)
{
	vector<Student_info>::iterator iter = stable_partition(input.begin(),input.end(),did_all_hw);
	vector<Student_info> output(iter,input.end());
	input.erase(iter, input.end());

	return output;
}

int _tmain(int argc, _TCHAR* argv[])
{
	// students who did and didn't do all their homework
  vector<Student_info> did;

  // read the student records and partition them
  Student_info student;
  while (read(cin, student))
    did.push_back(student);

  vector<Student_info> didnt = extract_didnt(did);

  // verify that the analyses will show us something
  if (did.empty()) 
  {
    cout << "No student did all the homework!" << endl;
    return 1;
  }

  if (didnt.empty()) 
  {
    cout << "Every student did all the homework!" << endl;
    return 1;
  }

  // do the analyses
  write_analysis(cout, "median", median_analysis, did, didnt);
  write_analysis(cout, "average", average_analysis, did, didnt);
  write_analysis(cout, "median of homework turned in",
		 optimistic_median_analysis, did, didnt);

  return 0;
	return 0;
}
</span>

程序说明：这里须要注意的就是stable_partition.

10、编写一个函数，用这个函数来依照你自己的选择准则来对学生进行分类，使用它来取代extract_fails程序从而对它进行測试

主函数：

<span style="font-family:KaiTi_GB2312;">// lesson6_7.cpp : 定义控制台应用程序的入口点。

//功能：编写一个函数。用这个函数来依照你自己的选择准则来对学生进行分类，使用它来取代extract_fails程序从而对它进行測试
//时间：2014.5.24

#include "stdafx.h"
#include <algorithm>
#include <vector>
#include <iostream>
#include <string>

#include "6-7-classify.h"
#include "Student_info.h"
#include "grade.h"

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
	vector<Student_info> vs;
	Student_info s;
	string::size_type maxlen = 0;
	while(read(cin,s))
	{
		maxlen = max(maxlen, s.name.size());
		vs.push_back(s);
	}

	sort(vs.begin(), vs.end(),compare);

	vector<Student_info> fails = classify(vs, pgrade);

	for(int i = 0; i < fails.size(); ++i)
		cout << fails[i].name << " " << grade(fails[i]) << endl;

	return 0;
}
</span>

分类函数：

<span style="font-family:KaiTi_GB2312;">#include <algorithm>
#include "6-7-classify.h"

using namespace std;

//这就是依照自己的准则来分类
vector<Student_info> classify(vector<Student_info>& input, bool criteria(const Student_info&))
{
	ector<Student_info>::iterator iter = stable_partition(input.begin(), input.end(), criteria);
    vector<Student_info> output(iter, input.end());
    input.erase(iter, input.end());

    return output;
}</span>

11、在lesson6_7中继续编写一个函数在程序中用它来分析学生的成绩

主函数：

<span style="font-family:KaiTi_GB2312;">// lesson6_8.cpp : 定义控制台应用程序的入口点。

//功能：在lesson6_7中继续编写一个函数在程序中用它来分析学生的成绩

#include "stdafx.h"
#include <vector>
#include <iostream>

#include "6-8-classify.h"
#include "analysis.h"
#include "Student_info.h"

using namespace std;


int _tmain(int argc, _TCHAR* argv[])
{
	// students who did and didn't do all their homework
	vector<Student_info> did;

	// read the student records and partition them
	Student_info student;
	while (read(cin, student))
		did.push_back(student);

	vector<Student_info> didnt = classify(did, did_all_hw);//这里是我们的两点地方

	// verify that the analyses will show us something
	if (did.empty()) 
	{
		cout << "No student did all the homework!" << endl;
		return 1;
	}

	if (didnt.empty()) 
	{
		cout << "Every student did all the homework!" << endl;
		return 1;
	}

	// do the analyses
	write_analysis(cout, "median", median_analysis, did, didnt);
	write_analysis(cout, "average", average_analysis, did, didnt);
	write_analysis(cout, "median of homework turned in",optimistic_median_analysis, did, didnt);

	return 0;
}
</span>

12、使用一个库算法连接一个vector<string>对象中的全部元素

<span style="font-family:KaiTi_GB2312;">// lesson6_9.cpp : 定义控制台应用程序的入口点。
//功能：使用一个库算法连接一个vector<string>对象中的全部元素
//时间：2014.5.24

#include "stdafx.h"
#include <vector>
#include <string>
#include <iostream>
#include <iterator>
#include <numeric>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
	cout << "Please enter some words: ";
	vector<string> v;
	string s;
	while(cin >> s)
		v.push_back(s);
	string sum = accumulate(v.begin(),v.end(),string("the string is:"));
	cout << sum << endl;
	return 0;
}
</span>

执行结果：

                                                                                     ——To_捭阖_youth