| 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λ λ°λ³΅μλ₯Ό 무ν¨νμν¨λ€.
λ°λΌμ μ μ₯λ λ°λ³΅μμ κ΄ν΄μ νλ‘κ·Έλλ°μ νλ©΄μ μ‘°μ¬ν΄μΌν νμκ° μλ€.
λ°λΌμ μκΈ°μ κ°μ ν¨μλ₯Ό μ΄μ©ν λ€μλ μ΄μ μ ν λΉλ λ°λ³΅μκ° μ ν¨νλ€κ³ λ³΄κ³ νλ‘κ·Έλ¨μ λ‘μ§μ λ§λ€μ΄μλ μλλ€.










