AcceleratedC++/Chapter5 | AcceleratedC++/Chapter7 |
Contents
|
1. Chapter 6 Using Library Algorithms ¶
- 5장에서 본것처럼 우리가 다루는 컨테이너들은 내부 사정은 다를지라도, 우리는 그것을 모르고도 똑같이 쓸 수가 있다. 즉 일관된 인터페이스를 제공한다는 것이다. 컨테이너나 반복자와 마찬가지로 표준 라이브러리도 일관된 인터페이스를 제공한다. 벡터를 배웠으면 리스트도 금방 쓸수 있는 것처럼, 하나의 알고리즘 쓰는 법을 배우면, 다른 것 쓰는 법도 금방 알수가 있다.
1.1. 6.1 Analyzing strings ¶
- 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()에는 아무것도 없다.
- 왜 이렇게 설계했는가? 프로그래머로 하여금 쓰고 싶은 연산을 골라서 쓸수 있게 하기 때문이다.
1.1.1. 6.1.1 Another way to split ¶
~cpp 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; }
1.1.2. 6.1.2 Palindromes ¶
~cpp bool isPalindrome(const string& s) { return equal(s.begin(), s.end(), s.rbegin()); }
1.1.3. 6.1.3 Finding URL ¶
~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.2. 6.2 Comparing grading schemes ¶
Chapter 4.2에서 제시된 중앙값을 이용한 방식으로 성적을 계산할 경우 악의적으로
과제물을 제출하지 않는 학생의 발생이 염려된다.
과연 어느 정도로 결과에 영향을 주는지 실제로 프로그램을 작성하여 확인해본다.
과제물을 제출하지 않는 학생의 발생이 염려된다.
과연 어느 정도로 결과에 영향을 주는지 실제로 프로그램을 작성하여 확인해본다.
- 중앙값 대신 평균을 사용하며, 제출하지 않은 과제에는 0점을 주는 방식(6.2.3)
- 실제로 제출한 과제에 대해서만 중앙값을 적용하는 방법(6.2.4)
- 중앙값을 이용하여 평균을 이용(6.2.2)
이를 위한 세부작업
- 모든 학생의 레코드를 읽어들여, 모든 과제를 제출한 학생들과 그렇지 않은 학생들을 구분합니다.(6.2.1)
- 두 계산법을(위의1,2를 의미, 3도 포함해야할듯..@,.@) 각 그룹의 모든 학생들에게 각각 적용하고, 각 그룹의 중앙 값을 출력합니다.(6.2.2)
1.2.1.1. 모든 과제를 제출했는지를 판별하는 함수 ¶
~cpp 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를 리턴함
1.2.1.2. 학생 레코드를 읽고 분류하는 코드 ¶
~cpp 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리턴
1.2.2.1. 초기 median_analysis 함수 ¶
~cpp // 이 함수는 제대로 동작하지 않습니다. 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번째 주소부터 넣음(?)
문제점
- grade함수는 오버라이딩된 함수이므로 컴파일러가 전달인자를 파악하지 못함
- 과제를 하나도 내지 않은 학생일경우 오류 발생
1.2.2.2. 해결책 ¶
새로운 함수 grade_aux 작성
median_anlysis함수 수정
~cpp double grade_aux(const Student_info& s) { try{ return grade(s); } catch(domain_error) { return grade(s.midterm, s.final, 0); } }
median_anlysis함수 수정
~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); }
1.2.2.3. write_analysis함수 작성 ¶
~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; }
1.2.2.4. main함수 ¶
~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; }
1.2.3.1. average함수 ¶
~cpp double average(const vector<double>& v) { return accumulate(v.begin(), v.end(), 0.0) / v.size(); }accumulate함수: 처음2개의 전달인자를 3번째 전달인자에 누적시킴(주의 0.0대신 0을 사용하면 정수로 인식 소수점 부분을 버려버림)
1.2.3.2. average_grade함수 ¶
~cpp double average_grade(const Student_info& s) { return grade(s.midterm, s.final, average(s.homework)); }
1.2.3.3. average_analysis함수 ¶
~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); }
1.2.4.1. optimistic_median함수 ¶
~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)); }
1.3.1. 6.3.1 A two -pass solution ¶
==== extract_fails 함수====
remove_if함수: 처음 2개의 전달인자 범위의 값들중 3번째 전달인자를 만족하는 함수를 컨테이너의 뒤로 이동. 3번째 전달인자를 만족하는 값중 젤첫째값을 가르침
erase멤버함수:처음 2개의 전달인자 범위의 값을 지운다.
~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; }remove_copy_if함수: 처음 2개의 전달인자 범의의값들을 4번째 전달인자 함수를 만족하지 않는 함수만 3번째 전달인자에 복사
remove_if함수: 처음 2개의 전달인자 범위의 값들중 3번째 전달인자를 만족하는 함수를 컨테이너의 뒤로 이동. 3번째 전달인자를 만족하는 값중 젤첫째값을 가르침
erase멤버함수:처음 2개의 전달인자 범위의 값을 지운다.
1.3.1.1. pgrade 함수 ¶
~cpp bool pgrade(const Student_info& s) { return !fgrade(s); }fgrade함수를 반전시킨 함수
1.3.2. 6.3.2 A single-pass solution ¶
~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; }stable_partition, partition 차이점?? 순서를 안바꾸다니?? @,.@
하이튼 2함수는 만족하지 않는 값의 첫째 위치를 리턴
two-pass보다 2배빠름
1.4. 6.4 Algorithms, containers, and iterators ¶
컨테이너와 알고리즘의 관계
알고리즘은 컨테이너 요소들을 다룹니다. 즉, 컨테이너를 다루는 것이 아닙니다.
sort, remove_if, partition 은 모두 요소를 새로운 위치로 이동시키지만, 컨테이너 자체의 속성인 크기를 변경하지는 않는다.
삭제를 하기 위해서는 다음과 같은 방식으로 컨테이너의 메소드를 이용해야한다.
컨테이너와 반복자의 관계
partiton, remove_if, erase, insert와 같은 연산은 erase된 반복자를 무효화시킨다.
따라서 저장된 반복자에 관해서 프로그래밍을 하면서 조심해야할 필요가 있다.
따라서 상기와 같은 함수를 이용한 뒤에는 이전에 할당된 반복자가 유효하다고 보고 프로그램의 로직을 만들어서는 안된다.
알고리즘은 컨테이너 요소들을 다룹니다. 즉, 컨테이너를 다루는 것이 아닙니다.
sort, remove_if, partition 은 모두 요소를 새로운 위치로 이동시키지만, 컨테이너 자체의 속성인 크기를 변경하지는 않는다.
삭제를 하기 위해서는 다음과 같은 방식으로 컨테이너의 메소드를 이용해야한다.
~cpp v.erase(remove_if(students.begin(), students.end(), fgrade), students.end());
컨테이너와 반복자의 관계
partiton, remove_if, erase, insert와 같은 연산은 erase된 반복자를 무효화시킨다.
따라서 저장된 반복자에 관해서 프로그래밍을 하면서 조심해야할 필요가 있다.
따라서 상기와 같은 함수를 이용한 뒤에는 이전에 할당된 반복자가 유효하다고 보고 프로그램의 로직을 만들어서는 안된다.