Maintenance script: Repair batch-0001 pages from live compare

2026-03-26T23:56:00Z

Repair batch-0001 pages from live compare

← Older revision		Revision as of 23:56, 26 March 2026
Line 148:		Line 148:
	// `beg' marks the beginning of the protocol-name		// `beg' marks the beginning of the protocol-name
	iter beg = i;		iter beg = i;
	while (beg != b && isalpha(beg[-1]))		while (beg != b && isalpha(beg[-1]))
	--beg; //protocol-typed의 위치에 존재하는 문자열이 조건에 맞을 경우 앞으로 한칸씩 움직이면서 검사한다.		--beg; //protocol-typed의 위치에 존재하는 문자열이 조건에 맞을 경우 앞으로 한칸씩 움직이면서 검사한다.
	// is there at least one appropriate character before and after the separator?		// is there at least one appropriate character before and after the separator?
	if (beg != i && !not_url_char(i[sep.size()]))		if (beg != i && !not_url_char(i[sep.size()]))
	return beg;		return beg;
	}		}
Line 304:		Line 304:

	accumulate함수: 처음2개의 전달인자를 3번째 전달인자에 누적시킴(주의 0.0대신 0을 사용하면 정수로 인식 소수점 부분을 버려버림)		accumulate함수: 처음2개의 전달인자를 3번째 전달인자에 누적시킴(주의 0.0대신 0을 사용하면 정수로 인식 소수점 부분을 버려버림)
	* 이함수를 사용하기 위해서는 ~~<~~numeric~~>~~을 include 해줘야 한다.		* 이함수를 사용하기 위해서는 <numeric>을 include 해줘야 한다.
	==== average_grade함수 ====		==== average_grade함수 ====
	double average_grade(const Student_info& s)		double average_grade(const Student_info& s)
Line 386:		Line 386:
	sort, remove_if, partition 은 모두 요소를 새로운 위치로 이동시키지만, 컨테이너 자체의 속성인 크기를 변경하지는 않는다.		sort, remove_if, partition 은 모두 요소를 새로운 위치로 이동시키지만, 컨테이너 자체의 속성인 크기를 변경하지는 않는다.
	삭제를 하기 위해서는 다음과 같은 방식으로 컨테이너의 메소드를 이용해야한다.		삭제를 하기 위해서는 다음과 같은 방식으로 컨테이너의 메소드를 이용해야한다.
	~~~cpp~~ v.erase(remove_if(students.begin(), students.end(), fgrade), students.end());		<code>v.erase(remove_if(students.begin(), students.end(), fgrade), students.end());</code>

	''컨테이너와 반복자의 관계''		''컨테이너와 반복자의 관계''
Line 395:		Line 395:
	----		----
	[[AcceleratedC++]]		[[AcceleratedC++]]

imported>Unknown at 05:22, 7 February 2021

2021-02-07T05:22:25Z

New page

{| class="wikitable"
|-
| [[AcceleratedC++/Chapter5]]
| [[AcceleratedC++/Chapter7]]
|}

{| class="wikitable"
|-
| __TOC__
|}

= Chapter 6 Using Library Algorithms =
* 5장에서 본것처럼 우리가 다루는 컨테이너들은 내부 사정은 다를지라도, 우리는 그것을 모르고도 똑같이 쓸 수가 있다. 즉 일관된 인터페이스를 제공한다는 것이다. 컨테이너나 반복자와 마찬가지로 표준 라이브러리도 일관된 인터페이스를 제공한다. 벡터를 배웠으면 리스트도 금방 쓸수 있는 것처럼, 하나의 알고리즘 쓰는 법을 배우면, 다른 것 쓰는 법도 금방 알수가 있다.
== 6.1 Analyzing strings ==
** Chapter5의 마지막에 루프를 줄인 다음과 같은 구문이 있었다. ret의 끝에다가 bottom의 처음부터 끝까지 넣는다는 뜻이다.
ret.insert(ret.end(), bottom,begin(), bottom.end());

** 근데 이것보다 더 일반적인, (즉 컨테이너에 독립적인) 방법이 있다. 컨테이너의 멤버함수를 이용하는 것이 아닌, 표준 알고리즘을 이용하는 것이다. 위의 것과 동일한 기능을 한다.
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를 수행한다는 것이다. 그럼 다음과 같이 쓰고 싶은 사람도 있을 것이다.
copy(bottom.begin(), bottom.end(), ret.end());

** 앞에서도 말했지만, end()에는 아무것도 없다.
** 왜 이렇게 설계했는가? 프로그래머로 하여금 쓰고 싶은 연산을 골라서 쓸수 있게 하기 때문이다.

=== 6.1.1 Another way to split ===
** 5장에서 공부한 것 중에 주어진 string을 공백을 기준으로 잘라서, vector에다 넣은 다음 리턴해주는 함수가 있었다.(split) 이것을 좀 더 간단히 만들어보자. 앞의 것은 굉장히 알아보기 힘들게 되어있다.
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()를 깔끔하게 처리해준다. 우리가 신경안써도 된다는 것이다.

=== 6.1.2 Palindromes ===
** Palindrome이란 앞에서부터 읽어도 뒤에서부터 읽어도 똑같은 단어를 의미한다.
bool isPalindrome(const string& s)
{
return equal(s.begin(), s.end(), s.rbegin());
}

** 참 깔끔하다. rbegin()은 역시 반복자를 리턴해주는 함수이다. 거꾸로 간다. equal함수는 두개의 구간을 비교해서 같을 경우 bool 의 true 값을 리턴한다. 파라매터로 첫번째 구간의 시작과 끝, 두번째 구간의 시작 iterator 를 받는다. 두번째 구간의 끝을 나타내는 iterator 를 요구하지 않는 이유는, 두개의 구간의 길이가 같다고 가정하기 때문이다. 이는 equal 함수의 동작을 생각해 볼때 합당한 처리이다.
=== 6.1.3 Finding URL ===
#ifndef GUARD_urls_h
#define GUARD_urls_h
#include <vector>
#include <string>
std::vector<std::string> find_urls(const std::string& s);
#endif

#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 스토리지 지정자는 함수의 최초 생성시 저장공간에 단 한번만 할당되며, 다시 호출을 하여도 새로 할당되지 않는다.

== 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)

=== 6.2.1 Working with student records ===

==== 모든 과제를 제출했는지를 판별하는 함수 ====
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를 리턴함

==== 학생 레코드를 읽고 분류하는 코드 ====
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리턴

=== 6.2.2 Analyzing the grades ===
==== 초기 median_analysis 함수 ====
// 이 함수는 제대로 동작하지 않습니다.
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함수는 오버라이딩된 함수이므로 컴파일러가 전달인자를 파악하지 못함
# 과제를 하나도 내지 않은 학생일경우 오류 발생
==== 해결책 ====
새로운 함수 grade_aux 작성
double grade_aux(const Student_info& s)
{
try{
return grade(s);
} catch(domain_error) {
return grade(s.midterm, s.final, 0);
}
}

median_anlysis함수 수정
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);
}

==== write_analysis함수 작성 ====
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;
}

==== main함수 ====
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;
}

=== 6.2.3 Grading based on average homework grade ===
평균 과제 성적에 기반한 성적 계산
==== average함수 ====
double average(const vector<double>& v)
{
return accumulate(v.begin(), v.end(), 0.0) / v.size();
}

accumulate함수: 처음2개의 전달인자를 3번째 전달인자에 누적시킴(주의 0.0대신 0을 사용하면 정수로 인식 소수점 부분을 버려버림)
* 이함수를 사용하기 위해서는 <numeric>을 include 해줘야 한다.
==== average_grade함수 ====
double average_grade(const Student_info& s)
{
return grade(s.midterm, s.final, average(s.homework));
}

==== average_analysis함수 ====
double average_analysis(const vector<Student_info>& students)
{
vector<double> grades;
transform(students.begin(), students.end(),
back_inserter(gardes), aveage_grade);
return median(grades);
}

=== 6.2.4 Median of the completed homework ===
완료된 과제의 중앙 값
==== optimistic_median함수 ====
// 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));
}

==== optimistic_median_analysis함수 ====
숙제라네요..ㅎㅎ
[[AcceleratedC++/Chapter6/Code]]
== 6.3 Classifying students, revisited ==
5장에서 사용한 list를 사용하지 않고, vector를 그대로 사용하여 그와 비슷한 성능의 알고리즘

=== 6.3.1 A two -pass solution ===
==== extract_fails 함수====
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개의 전달인자 범위의 값을 지운다.

==== pgrade 함수 ====
bool pgrade(const Student_info& s)
{
return !fgrade(s);
}

fgrade함수를 반전시킨 함수

=== 6.3.2 A single-pass solution ===
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배빠름
== 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된 반복자를 무효화시킨다.
따라서 저장된 반복자에 관해서 프로그래밍을 하면서 조심해야할 필요가 있다.
따라서 상기와 같은 함수를 이용한 뒤에는 이전에 할당된 반복자가 유효하다고 보고 프로그램의 로직을 만들어서는 안된다.

----
[[AcceleratedC++]]

AcceleratedC++/Chapter6 - Revision history

Maintenance script: Repair batch-0001 pages from live compare

imported>Unknown at 05:22, 7 February 2021