U E D R , A S I H C RSS

AcceleratedC++/Chapter6

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

  • 5장ì—�서 공부한 것 중ì—� 주어진 stringì�„ 공백ì�„ 기준으로 잘ë�¼ì„œ, vectorì—�다 ë„£ì�€ 다ì�Œ 리턴해주는 함수가 있었다.(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;
    }
      
  • 훨씬 알아보기 쉬워졌다. 5장ì�˜ splitì�€ find_if마다 열심히 루프를 ë�Œë ¸ì—ˆë‹¤. ì�´ì œ 차근차근 살펴보ìž�.
  • find_ifì�˜ ì�¸ìž�를 ë³´ë©´, 앞ì�˜ ë‘�ê°œì�˜ ì�¸ìž�는 범위를 ì�˜ë¯¸í•œë‹¤. 첫ì�¸ìž�~ë‘�번째ì�¸ìž� ë§�ì�´ë‹¤. 마지막 ì�¸ìž�는 bool형ì�„ 리턴하는 함수를 넣어준다. 즉 predicaterì�´ë‹¤. 그러면 find_if는 주어진 범위 ë‚´ì—�서 predicator를 만족하는 부분ì�˜ 반복ìž�를 리턴해 준다.
  • isspace는 표준 ë�¼ì�´ë¸ŒëŸ¬ë¦¬ì—�서 ì§€ì›�하는 함수임ì—�다 불구하고, 왜 따로 만들었ì�„까? 바로 isspace는 여러 언어 버젼으로 오버로딩 ë�˜ì–´ 있기 때문ì�´ë‹¤. 템플릿 함수ì�˜ ì�¸ìž�로 오버로딩ë�œ 함수를 넘겨주는 것ì�€ 쉽지 않다. ì–´ë–¤ 버젼ì�¸ì§€ 알수가 없기 때문ì�´ë‹¤. ì�´ê²ƒì�´ 우리가 isspaceì—­í• ì�„ 하는 함수를 새로 만든 ì�´ìœ ë‹¤.
  • 5장ì—�서는 string(i,j) 대신ì—�, substrì�´ë�¼ëŠ” 함수를 ì�´ìš©í–ˆì—ˆëŠ”ë�°, ì�´ë²ˆì—� ì“°ì§€ 않ì�€ ì�´ìœ ëŠ” substrì�€ 반복ìž�를 ì�¸ìž�로 받지 않기 떄문ì�´ë‹¤.
  • ë˜�한 제네릭 알고리즘ì�€ end()를 ê¹”ë�”하게 처리해준다. 우리가 신경안ì�¨ë�„ ë�œë‹¤ëŠ” 것ì�´ë‹¤.

  • 1.1.2. 6.1.2 Palindromes

  • Palindromeì�´ëž€ 앞ì—�서부터 ì�½ì–´ë�„ ë’¤ì—�서부터 ì�½ì–´ë�„ 똑같ì�€ 단어를 ì�˜ë¯¸í•œë‹¤.
    ~cpp 
    bool isPalindrome(const string& s)
    {
     return equal(s.begin(), s.end(), s.rbegin());
    }
      
  • ì°¸ ê¹”ë�”하다. rbegin()ì�€ 역시 반복ìž�를 리턴해주는 함수ì�´ë‹¤. 거꾸로 간다. equal함수는 ë‘�ê°œì�˜ 구간ì�„ 비êµ�해서 ê°™ì�„ 경우 bool ì�˜ true ê°’ì�„ 리턴한다. 파ë�¼ë§¤í„°ë¡œ 첫번째 구간ì�˜ 시작과 ë��, ë‘�번째 구간ì�˜ 시작 iterator 를 받는다. ë‘�번째 구간ì�˜ ë��ì�„ 나타내는 iterator 를 요구하지 않는 ì�´ìœ ëŠ”, ë‘�ê°œì�˜ 구간ì�˜ 길ì�´ê°€ 같다고 가정하기 때문ì�´ë‹¤. ì�´ëŠ” equal 함수ì�˜ ë�™ìž‘ì�„ ìƒ�ê°�í•´ 볼때 합당한 처리ì�´ë‹¤.
  • 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;
    }
      
  • ì�´ 예제는 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 스토리지 지정ìž�는 함수ì�˜ 최초 ìƒ�성시 저장공간ì—� 단 한번만 할당ë�˜ë©°, 다시 호출ì�„ 하여ë�„ 새로 할당ë�˜ì§€ 않는다.

  • 1.2. 6.2 Comparing grading schemes

    Chapter 4.2�서 제시� 중앙값� �용한 방�으로 성�� 계산할 경우 악��으로
    과제물� 제출하지 않는 학�� 발�� 염려�다.
    과연 어� 정�로 결과� �향� 주는지 실제로 프로그램� 작성하여 확�해본다.
  • 중앙값 대신 í�‰ê· ì�„ 사용하며, 제출하지 않ì�€ 과제ì—�는 0ì �ì�„ 주는 ë°©ì‹�(6.2.3)
  • 실제로 제출한 과제ì—� 대해서만 중앙값ì�„ ì �용하는 방법(6.2.4)
  • 중앙값ì�„ ì�´ìš©í•˜ì—¬ í�‰ê· ì�„ ì�´ìš©(6.2.2)

  • ì�´ë¥¼ 위한 세부작업
    1. 모든 학�� 레코드를 �어들여, 모든 과제를 제출한 학�들과 그렇지 않� 학�들� 구분합니다.(6.2.1)
    2. � 계산법�(위�1,2를 �미, 3� �함해야할듯..@,.@) � 그룹� 모든 학�들�게 �� �용하고, � 그룹� 중앙 값� 출력합니다.(6.2.2)

    1.2.1. 6.2.1 Working with student records


    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. 6.2.2 Analyzing the grades

    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 작성
    ~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� 사용하면 정수로 �� 소수� 부분� 버려버림)
  • ì�´í•¨ìˆ˜ë¥¼ 사용하기 위해서는 <numeric>ì�„ include 해줘야 한다.
  • 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. 6.2.4 Median of the completed homework

    완료� 과제� 중앙 값

    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.2.4.2. optimistic_median_analysis함수

    숙제�네요..ㅎㅎ
    AcceleratedC++/Chapter6/Code

    1.3. 6.3 Classifying students, revisited

    5장�서 사용한 list를 사용하지 않고, vector를 그대로 사용하여 그와 비슷한 성능� 알고리즘

    1.3.1. 6.3.1 A two -pass solution

    ==== extract_fails 함수====
    ~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 � 모� 요소를 새로운 위치로 ��시키지만, 컨테�너 �체� �성� �기를 변경하지는 않는다.
    삭제를 하기 위해서는 다�과 같� 방�으로 컨테�너� 메소드를 �용해야한다.
    ~cpp v.erase(remove_if(students.begin(), students.end(), fgrade), students.end());

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

    Valid XHTML 1.0! Valid CSS! powered by MoniWiki
    last modified 2021-02-07 05:22:25
    Processing time 0.0197 sec