| 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번째 주소부터 ë„£ì�Œ(?)ë¬¸ì œì �
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� 반복�를 무효화시킨다.
ë”°ë�¼ì„œ ì €ìž¥ë�œ 반복ìž�ì—� 관해서 프로그래ë°�ì�„ 하면서 ì¡°ì‹¬í•´ì•¼í• í•„ìš”ê°€ 있다.
ë”°ë�¼ì„œ ìƒ�기와 ê°™ì�€ 함수를 ì�´ìš©í•œ ë’¤ì—�는 ì�´ì „ì—� í• ë‹¹ë�œ 반복ìž�ê°€ ìœ íš¨í•˜ë‹¤ê³ ë³´ê³ í”„ë¡œê·¸ëž¨ì�˜ 로ì§�ì�„ 만들어서는 안ë�œë‹¤.










