AcceleratedC++/Chapter6

AcceleratedC++/Chapter5

AcceleratedC++/Chapter7

Chapter 6 Using Library Algorithms

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

== 6.1 Analyzing strings ==

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

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

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

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를 수행한다는 것이다. 그럼 다음과 같이 쓰고 싶은 사람도 있을 것이다.

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

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

 === 6.1.1 Another way to split ===

• • 5장에서 공부한 것 중에 주어진 string을 공백을 기준으로 잘라서, vector에다 넣은 다음 리턴해주는 함수가 있었다.(split) 이것을 좀 더 간단히 만들어보자. 앞의 것은 굉장히 알아보기 힘들게 되어있다.

vector<string> split(const string& str)
{
 typedef string::const_iterator iter;
 vector<string> ret;
 iter i = str.begin();
 while(i != str.end()) {
  i = find_if(i, str.end(), not_space); // 공백이 아닌 부분을 찾고
  iter j = find_if(i, str.end(), space); // 공백인 부분을 찾아서
  if(i != str.end())
   ret.push_back(string(i,j)); // 그만큼의 문자열엘 벡터에 넣음
  i = j;
 }
 return ret;
}
  

• • 훨씬 알아보기 쉬워졌다. 5장의 split은 find_if마다 열심히 루프를 돌렸었다. 이제 차근차근 살펴보자.
  • find_if의 인자를 보면, 앞의 두개의 인자는 범위를 의미한다. 첫인자~두번째인자 말이다. 마지막 인자는 bool형을 리턴하는 함수를 넣어준다. 즉 predicater이다. 그러면 find_if는 주어진 범위 내에서 predicator를 만족하는 부분의 반복자를 리턴해 준다.
  • isspace는 표준 라이브러리에서 지원하는 함수임에다 불구하고, 왜 따로 만들었을까? 바로 isspace는 여러 언어 버젼으로 오버로딩 되어 있기 때문이다. 템플릿 함수의 인자로 오버로딩된 함수를 넘겨주는 것은 쉽지 않다. 어떤 버젼인지 알수가 없기 때문이다. 이것이 우리가 isspace역할을 하는 함수를 새로 만든 이유다.
  • 5장에서는 string(i,j) 대신에, substr이라는 함수를 이용했었는데, 이번에 쓰지 않은 이유는 substr은 반복자를 인자로 받지 않기 떄문이다.
  • 또한 제네릭 알고리즘은 end()를 깔끔하게 처리해준다. 우리가 신경안써도 된다는 것이다.

 === 6.1.2 Palindromes ===

• • Palindrome이란 앞에서부터 읽어도 뒤에서부터 읽어도 똑같은 단어를 의미한다.

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

• • 참 깔끔하다. rbegin()은 역시 반복자를 리턴해주는 함수이다. 거꾸로 간다. equal함수는 두개의 구간을 비교해서 같을 경우 bool 의 true 값을 리턴한다. 파라매터로 첫번째 구간의 시작과 끝, 두번째 구간의 시작 iterator 를 받는다. 두번째 구간의 끝을 나타내는 iterator 를 요구하지 않는 이유는, 두개의 구간의 길이가 같다고 가정하기 때문이다. 이는 equal 함수의 동작을 생각해 볼때 합당한 처리이다.

 === 6.1.3 Finding URL ===
#ifndef GUARD_urls_h
#define GUARD_urls_h
#include <vector>
#include <string>
std::vector<std::string> find_urls(const std::string& s);
#endif
  

#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;
}
  

• • 이 예제는 string STL을 이용해서 문자열을 검색하고, 우리에게 맞는 정보를 가공하는 것이 목적이다.
  • protocol-type://domainname 의 형태를 검사한다.
  • search(b, e, b2, e3) [b, e)의 문자열 시퀀스에서 [b2, e3) 문자열 시퀀스를 찾는다.
  • find(b, e, t) 문자열 시퀀스 [b, e)에서 값 t를 찾는다.
  • find_if(b, e, p) 문자열 시퀀스 [b, e)에서 함수 p를 통해 테스트한다.
  • static 스토리지 지정자는 함수의 최초 생성시 저장공간에 단 한번만 할당되며, 다시 호출을 하여도 새로 할당되지 않는다.

== 6.2 Comparing grading schemes ==
 Chapter 4.2에서 제시된 중앙값을 이용한 방식으로 성적을 계산할 경우 악의적으로
 과제물을 제출하지 않는 학생의 발생이 염려된다.
 과연 어느 정도로 결과에 영향을 주는지 실제로 프로그램을 작성하여 확인해본다.

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

이를 위한 세부작업

1. 1. 모든 학생의 레코드를 읽어들여, 모든 과제를 제출한 학생들과 그렇지 않은 학생들을 구분합니다.(6.2.1)
   2. 두 계산법을(위의1,2를 의미, 3도 포함해야할듯..@,.@) 각 그룹의 모든 학생들에게 각각 적용하고, 각 그룹의 중앙 값을 출력합니다.(6.2.2)

=== 6.2.1 Working with student records ===

==== 모든 과제를 제출했는지를 판별하는 함수 ====
  bool did_all_hw(const Student_info& s)
  {
  	return ((find(s.homework.begin(), s.homework.end(), 0)) ==
  		s.homework.end());
  }
 
find함수는 처음두개의 전달인자 범위에서 세번째 전달인자의 값을 찾지 못하면 2번째 전달인자를 리턴한다. (찾으면 첫번째전달인자   
를 리턴한다던데...@,.@잘못된거 아닌가??) 고로 찾지못하면 s.homework.begin() == s.homework.begin()이 되므로 true를 리턴함

==== 학생 레코드를 읽고 분류하는 코드 ====
  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;
  } 
 
empty멤버함수: 컨테이너가 비어 있으면 true, 아니면 false리턴
  
=== 6.2.2 Analyzing the grades ===
==== 초기 median_analysis 함수 ====
// 이 함수는 제대로 동작하지 않습니다.
double median_anlysis(const vector<Strudent_info>& students)
{
	vector<double> grades;
	transform(students.begin(), students.end(),
		back_inserter(grades), grade);
	return median(grades);
}
 
transform함수: 처음2개의 전달인자 범의의 값들을 4번째함수에 대입 리턴값을 3번째 주소부터 넣음(?)
문제점

1. grade함수는 오버라이딩된 함수이므로 컴파일러가 전달인자를 파악하지 못함
2. 과제를 하나도 내지 않은 학생일경우 오류 발생

==== 해결책 ====
새로운 함수 grade_aux 작성
double grade_aux(const Student_info& s)
{
	try{
		return grade(s);
	} catch(domain_error) {
		return grade(s.midterm, s.final, 0);
	}
}
 

median_anlysis함수 수정
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);
}
 

==== write_analysis함수 작성 ====
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;
}
 

==== main함수 ====
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;
}
 

=== 6.2.3 Grading based on average homework grade ===
평균 과제 성적에 기반한 성적 계산
==== average함수 ====
double average(const vector<double>& v)
{
	return accumulate(v.begin(), v.end(), 0.0) / v.size();
}
 
accumulate함수: 처음2개의 전달인자를 3번째 전달인자에 누적시킴(주의 0.0대신 0을 사용하면 정수로 인식 소수점 부분을 버려버림)

• 이함수를 사용하기 위해서는 <numeric>을 include 해줘야 한다.

==== average_grade함수 ====
double average_grade(const Student_info& s)
{
	return grade(s.midterm, s.final, average(s.homework));
}
 

==== average_analysis함수 ====
double average_analysis(const vector<Student_info>& students)
{
	vector<double> grades;
	transform(students.begin(), students.end(),
		back_inserter(gardes), aveage_grade);
	return median(grades);
}
 
=== 6.2.4 Median of the completed homework ===
완료된 과제의 중앙 값
==== optimistic_median함수 ====
// 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));
}
 

==== optimistic_median_analysis함수 ====
숙제라네요..ㅎㅎ
AcceleratedC++/Chapter6/Code
== 6.3 Classifying students, revisited ==
5장에서 사용한 list를 사용하지 않고, vector를 그대로 사용하여 그와 비슷한 성능의 알고리즘

=== 6.3.1 A two -pass solution ===
==== extract_fails 함수====
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;
}
 
remove_copy_if함수: 처음 2개의 전달인자 범의의값들을 4번째 전달인자 함수를 만족하지 않는 함수만 3번째 전달인자에 복사
remove_if함수: 처음 2개의 전달인자 범위의 값들중 3번째 전달인자를 만족하는 함수를 컨테이너의 뒤로 이동. 3번째 전달인자를 만족하는 값중 젤첫째값을 가르침
erase멤버함수:처음 2개의 전달인자 범위의 값을 지운다.

==== pgrade 함수 ====
bool pgrade(const Student_info& s)
{
	return !fgrade(s);
}
 
fgrade함수를 반전시킨 함수

=== 6.3.2 A single-pass solution ===
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;
}
 
stable_partition, partition 차이점?? 순서를 안바꾸다니?? @,.@
하이튼 2함수는 만족하지 않는 값의 첫째 위치를 리턴
two-pass보다 2배빠름
== 6.4 Algorithms, containers, and iterators ==
  컨테이너와 알고리즘의 관계

  알고리즘은 컨테이너 요소들을 다룹니다. 즉, 컨테이너를 다루는 것이 아닙니다.
  sort, remove_if, partition 은 모두 요소를 새로운 위치로 이동시키지만, 컨테이너 자체의 속성인 크기를 변경하지는 않는다.
  삭제를 하기 위해서는 다음과 같은 방식으로 컨테이너의 메소드를 이용해야한다.

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

  컨테이너와 반복자의 관계
  partiton, remove_if, erase, insert와 같은 연산은 erase된 반복자를 무효화시킨다.
  따라서 저장된 반복자에 관해서 프로그래밍을 하면서 조심해야할 필요가 있다.
  따라서 상기와 같은 함수를 이용한 뒤에는 이전에 할당된 반복자가 유효하다고 보고 프로그램의 로직을 만들어서는 안된다.   
  

---

AcceleratedC++