1. Chapter 6 Using Library Algorithms ¶

• 5장에서 본것처럼 우리가 다루는 컨테이너들은 내부 사정은 다를지라도, 우리는 그것을 모르고도 똑같이 쓸 수가 있다. 즉 일관된 인터페이스를 제공한다는 것이다. 컨테이너나 반복자와 마찬가지로 표준 라이브러리도 일관된 인터페이스를 제공한다. 벡터를 배웠으면 리스트도 금방 쓸수 있는 것처럼, 하나의 알고리즘 쓰는 법을 배우면, 다른 것 쓰는 법도 금방 알수가 있다.
  

• Chapter5의 마지막에 루프를 줄인 다음과 같은 구문이 있었다. ret의 끝에다가 bottom의 처음부터 끝까지 넣는다는 뜻이다.
  

  ~cpp 
  ret.insert(ret.end(), bottom,begin(), bottom.end());
    

  
  
• 근데 이것보다 더 일반적인, (즉 컨테이너에 독립적인) 방법이 있다. 컨테이너의 멤버함수를 이용하는 것이 아닌, 표준 알고리즘을 이용하는 것이다. 위의 것과 동일한 기능을 한다.
  

  ~cpp 
  copy(bottom.begin(), bottom.end(), back_inserter(ret));
    

  
  
• 음. 또 새로운 것이 보이지 않는가? copy는 generic algorithm의 예이고, back_inserter는 반복자 어댑터의 예이다. 이게 무엇인지는 차근차근 살펴보도록 하자.
  
• Generic algorithm이라는 컨테이너의 부분이 아닌 알고리즘이다. 파라메터로 반복자를 받는다. 비슷하지 않은가? .이 없다 뿐이지 그냥 쓰자.
  
• Postfix와 Prefix : i++과 ++i의 차이점이다. ++i는 i를 사용하기 전에 값을 증가시키고, i++은 i를 사용한 후에 값을 증가시킨다.
  
• 다음으로 반복자 어댑터(Iterator Adapters)를 살펴보자. 반복자 어댑터는 컨테이너를 인자로 받아, 정해진 작업을 수행하고 반복자를 리턴해주는 함수이다. copy알고리즘에 쓰인 back_inserter는 ret의 뒤에다가 copy를 수행한다는 것이다. 그럼 다음과 같이 쓰고 싶은 사람도 있을 것이다.
  

  ~cpp 
  copy(bottom.begin(), bottom.end(), ret.end());
    

• 앞에서도 말했지만, end()에는 아무것도 없다.
  
• 왜 이렇게 설계했는가? 프로그래머로 하여금 쓰고 싶은 연산을 골라서 쓸수 있게 하기 때문이다.
  
  

~cpp 
#ifndef GUARD_urls_h
#define GUARD_urls_h
#include <vector>
#include <string>
std::vector<std::string> find_urls(const std::string& s);
#endif
  

~cpp 
#include <algorithm>
#include <cctype>
#include <string>
#include <vector>
#include "urls.h"

using std::find;
using std::find_if;
using std::isalnum;
using std::isalpha;
using std::isdigit;
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();

 // look through the entire input
 while (b != e) {
  // look for one or more letters followed by `://'
  b = url_beg(b, e);
  // if we found it
  if (b != e) {
   // get the rest of the \s-1URL\s0
   iter after = url_end(b, e);
   // remember the \s-1URL\s0
   ret.push_back(string(b, after));
   // advance `b' and check for more \s-1URL\s0s on this line
   b = after;
  }
 }
 return ret;
}

string::const_iterator url_end(string::const_iterator b, string::const_iterator e)
{
 return find_if(b, e, not_url_char);
}

// find_if 함수의 테스팅에 이용되는 함수이다. char은 string 의 iterator의 값이다.
bool not_url_char(char c)
{
 // characters, in addition to alphanumerics, that can appear in a \s-1URL\s0
 static const string url_ch = "~;/?:@=&$-_.+!*'(),";
 // see whether `c' can appear in a \s-1URL\s0 and return the negative
 return !(isalnum(c) ||
          find(url_ch.begin(), url_ch.end(), c) != url_ch.end());
}

//이 예제의 핵심 함수이다.
string::const_iterator url_beg(string::const_iterator b, string::const_iterator e)
{
 /*
  b 는 protocol type의 시작위치를 가르키게된다.
  i 는 :// 의 시작 위치를 가리키는 역할을 한다.
  e 는 url의 마지막 텍스트를 가리키는 역할을 한다.
  */
 static const string sep = "://";
 typedef string::const_iterator iter;

 // `i' marks where the separator was found
 iter i = b;

 // string 에서 sep 의 문자열의 시작부분을 찾아서 i에 iterator를 대입한 후 e와 비교하여
 // 같지 않으면 실행한다. (즉, sep를 찾았을 경우)
 while ((i = search(i, e, sep.begin(), sep.end())) != e) {
  // make sure the separator isn't at the beginning or end of the line
  if (i != b && i + sep.size() != e) {
   // `beg' marks the beginning of the protocol-name
   iter beg = i;
   while (beg != b && isalpha(beg[-1]))
    --beg; //protocol-typed의 위치에 존재하는 문자열이 조건에 맞을 경우 앞으로 한칸씩 움직이면서 검사한다.
   // is there at least one appropriate character before and after the separator?
   if (beg != i && !not_url_char(i[sep.size()]))
    return beg;
  }
  // the separator we found wasn't part of a \s-1URL\s0; advance `i' past this separator
  i += sep.size();
 }
 return e;
}
  

1. 중앙값 대신 평균을 사용하며, 제출하지 않은 과제에는 0점을 주는 방식(6.2.3)
   
2. 실제로 제출한 과제에 대해서만 중앙값을 적용하는 방법(6.2.4)
   
3. 중앙값을 이용하여 평균을 이용(6.2.2)
   

~cpp 
double grade_aux(const Student_info& s)
{
	try{
		return grade(s);
	} catch(domain_error) {
		return grade(s.midterm, s.final, 0);
	}
}
 

~cpp 
double median_anlysis(const vector<Strudent_info>& students)
{
	vector<double> grades;
	transform(students.begin(), students.end(),
		back_inserter(grades), grade_aux);  //grade를 grade_aux로 수정
	return median(grades);
}
 

~cpp 
void write_analysis(ostream& out, const string& name,
				double analysis(const vector<Student_info>&),
				const vector<Student_infor>& did,
				const vector<Student_infor>& didnt)
{
	cout << name << ": median(did) = " << analysis(did) <<
				", median(didnt) = " << analysis(didnt) << endl;
}
 

~cpp 
int main()
{
 // students who did and didn't do all their homework
 vector<Student_info> did, didnt;
 // read the student records and partition them
 Student_info student;
 while (read(cin, student)) {
  if (did_all_hw(student))
   did.push_back(student);
  else 
   didnt.push_back(student);
 }
	 // 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;
}
 

~cpp 
double average(const vector<double>& v)
{
	return accumulate(v.begin(), v.end(), 0.0) / v.size();
}
 

~cpp 
double average_grade(const Student_info& s)
{
	return grade(s.midterm, s.final, average(s.homework));
}
 

~cpp 
double average_analysis(const vector<Student_info>& students)
{
	vector<double> grades;
	transform(students.begin(), students.end(),
		back_inserter(gardes), aveage_grade);
	return median(grades);
}
 

~cpp 
// s의 0이 아닌 요소들의 중앙 값, 만약 0이 아닌 요소가 하나도 없다면 결과는 0이 됩니다.
double optimistic_median(const Student_info& s)
{
	vector<double> nonzero;
	remove_copy(s.homework.begin(), s.homework.end(),
				back_inserter(nonzero), 0);
	if(nozero.empty())
		return grade(s.midterm, s.final, 0);
	else
		return grade(s.midterm, s.final, median(nonzero));
}
 

~cpp 
vector<Student_info> extract_fails(vector<Student_info>& students){
	vector<Student_info> fail;
	remove_copy_if(student.begin(), stduents.end(),
				back_inserter(fail), pgrade);
	students.erase(remove_if(studens.begin(), students.end(),
						fgrade), stduents.end());
	return fail;
}
 

~cpp 
bool pgrade(const Student_info& s)
{
	return !fgrade(s);
}
 

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

	return fail;
}