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. 6.2.3 Grading based on average homework grade ¶
νκ· κ³Όμ μ±μ μ κΈ°λ°ν μ±μ κ³μ°
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. 6.3 Classifying students, revisited ¶
5μ₯μμ μ¬μ©ν listλ₯Ό μ¬μ©νμ§ μκ³ , vectorλ₯Ό κ·Έλλ‘ μ¬μ©νμ¬ κ·Έμ λΉμ·ν μ±λ₯μ μκ³ λ¦¬μ¦
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λ λ°λ³΅μλ₯Ό 무ν¨νμν¨λ€.
λ°λΌμ μ μ₯λ λ°λ³΅μμ κ΄ν΄μ νλ‘κ·Έλλ°μ νλ©΄μ μ‘°μ¬ν΄μΌν νμκ° μλ€.
λ°λΌμ μκΈ°μ κ°μ ν¨μλ₯Ό μ΄μ©ν λ€μλ μ΄μ μ ν λΉλ λ°λ³΅μκ° μ ν¨νλ€κ³ λ³΄κ³ νλ‘κ·Έλ¨μ λ‘μ§μ λ§λ€μ΄μλ μλλ€.