Accelerated C++学习笔记7—<使用顺序容器并分析字符串>

浏览数：44 / 时间：2015年06月08日

第6章  使用库算法


本章中主要教我们如何使用几个库算法来解决与处理字符串和学生成绩相关的问题。
1、分析字符串
使用一个循环来连接两幅字符图案
for(vector<string>::const_iterator it = bottom.begin(); it != bottom.end(); ++it)
ret.push_back(*it);</span>

等价于
ret.insert(ret.end(), bottom.begin(), bottom.end());</span>

也等价于

copy(bottom.begin(), bottom.end(), back_inserter(ret));</span>

分析：这里指的是复制了bottom中的所有的元素并且把它们添加到ret的末尾。在这个函数借宿之后，ret的长度将添加bottom.size()。

补充：back_inserter(c) 对容器c产生一个迭代器，这个迭代器会给c添加元素，这个容器必须支持链表，向量以及字符串类型都会支持push_back操作。
copy(b, e, d) 把[b,e)所指示的系列复制到由d指示的目的地中。

2、实现split的方法
//如果参数是空白区域则为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>

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

3、回文
回文就是顺读和逆读都一样的单词。
// 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>

运行结果：


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

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

主函数：
// 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>

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

#include <vector>
#include <string>

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

#endif</span>

urls源文件：
#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>

运行结果：


程序分析：
1）isalnum函数是检验它的参数是否是一个字母数字字符（一个字母或者一个数字）；
2）isalpha 判断不是字母；
3）search(b,e,b2,e2) 在序列[b,e)中查找一个特定的算法，查找由[b2,e2)所指示的序列；

6、对计算成绩的方案进行比较
编写程序解决下面两个不同的问题：
1）读所有学生的记录，把做了全部家庭作业的学生与其他的学生分隔开
2）对每一组中的所有学生分别使用每一个的计算成绩的方案，报告每一组的中值成绩。
主函数：
// 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>

简单检查一个学生是否做个所有的家庭作业：
#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>

不同的分析函数：
//功能：分析
//时间：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>

程序分析：
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）使用两次传递的解决方案
#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>

这里计算了两次成绩，所以需要改进

2）一种一次传递的解决方案
#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>
程序分析：
1）partition(b,e,p)    以谓词p为基础从而划分在域[b,e)中的元素以使那些使谓词为真的元素处于容器的头部。返回一个迭代器，这个迭代器指示了第一个令谓词为假的元素；
2）stable_partition(b,e,p)  会让在每一个区域内的元素的输入顺序保持不变  

Accelerated C++学习笔记7—<使用顺序容器并分析字符串>,古老的榕树,5-wow.com

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

标签： 编程语言 Java C C# Javascript js Python Ruby Spring 程序 VB

相关文章

随机文章

您可能还喜欢

您可能还喜欢