라이브러리 알고리즘 사용하기 using LIBRARY ALGORITHMS

Presentation on theme: "라이브러리 알고리즘 사용하기 using LIBRARY ALGORITHMS"— Presentation transcript:

1 라이브러리 알고리즘 사용하기 using LIBRARY ALGORITHMS
Chapter 6 라이브러리 알고리즘 사용하기 using LIBRARY ALGORITHMS

2 6장에서는 표준 알고리즘을 사용하면, 표준 알고리즘들은 일관적인 인터페이스 제공
동일한 코드를 반복해서 작성하는 수고를 덜 수 있다. 더 작고 단순한 프로그램이 된다. 때로 놀라울 정도로! 표준 알고리즘들은 일관적인 인터페이스 제공 컨테이너, 반복자가 동일한 인터페이스를 제공하는 것처럼 vector, string, list, map은 insert()를 이용하여 요소 삽입, erase()로 요소 삭제 반복자는 ++연산자를 이용하여 다음요소로 반복자를 이동, *연산자를 이용하여 반복자의 요소를 접근.. 등 몇 가지에 익숙해지면 나머지는 쉽다.

3 6.1 string 분석하기 두 문자 그림을 합치는 문제에서, 벡터 top과 bottom에 스트링이 저장되어 있을 때,
ret에 이미 top을 추가한 상태에서, 두 벡터를 합치는 방법 ?? top bottom ******* * To * $$$$$$$$$$ $ John $ $ $ ******* * To * $$$$$$$$$$ $ John $ $ $ 합치면

4 두 벡터 결합 방법 방법 1-1: 방법 1-2: 방법 2: 알고리즘을 사용한 보다 일반적인 해결책은
ret에 이미 top을 추가한 상태에서, ret의 끝에 bottom의 복사본을 추가하는 작업 방법 1-1: 방법 1-2: 방법 2: 알고리즘을 사용한 보다 일반적인 해결책은 for(vector<string>::const_iterator it=bottom.begin(); it!=bottom.end(); ++it) ret.push_back(*it); ret.insert( ret.end(), bottom.begin(), bottom.end() ); copy(bottom.begin(), bottom.end(), back_inserter(ret));

5 알고리즘 copy(b, e, d) copy(begin, end, out) 제너릭 알고리즘(generic algorithm)
특정 종류의 컨테이너에만 해당되는 것이 아니라, 전달되는 인자에 따라 액세스 방법을 결정해서 처리해 준다. 인자로 대개 반복자를 취하고, 그 반복자를 이용하여 컨테이너의 요소들을 다룸 copy(bottom.begin(), bottom.end(), back_inserter(ret)); while (begin!=end) *out++ = *begin++;

6 반복자 어댑터: back_inserter(c)
반복자 어댑터(iterator adapter): back_inserter(c) 인자로 컨테이너 c를 취하며, 목적지로 사용될 경우, 컨테이너 c의 끝에 요소들을 추가하는 반복자를 내어준다. <iterator>에 정의되어 있음. 오류인 경우: copy(bottom.begin(), bottom.end(), ret); // ret가 반복자가 아니므로 (컴파일 오류) copy(bottom.begin(), bottom.end(), ret.end()); // ret.end()에 요소가 없으므로 // (컴파일 오류가 나지 않으므로 더욱 주의 요망) copy가 왜 이렇게 설계되어 있을까요? 요소를 복사하는 작업과 컨테이너를 확장하는 작업을 분리하기 위해

7 6.1.1 split 함수- 인덱스 사용한 방법 5.6절의 split()
vector<string> split(const string& s){ vector<string> ret; typedef string::size_type string_size; string_size i = 0; while (i != s.size()) { // 단어의 시작 위치 찾고 while (i != s.size() && isspace(s[i])) ++i; // 단어의 끝 위치 찾고 string_size j = i; while (j != s.size() && !isspace(s[j])) ++j; // 그것을 vector에 넣고 if (i != j) { ret.push_back( s.substr(i, j - i) ); i = j; } return ret;

8 split() 함수 – 반복자와 알고리즘 사용
vector<string> split(const string& str) { vector<string> ret; typedef string::const_iterator iter; // string 타입이 // 반복자 지원 iter i = str.begin(); while (i != str.end()) { // 맨 앞 공백들을 무시 i = find_if(i, str.end(), not_space); // 다음 단어의 끝을 찾음 iter j = find_if(i, str.end(), space); // [i,j)의 문자들을 복사 if (i != str.end()) ret.push_back(string(i, j)); i = j; } return ret; 이것은 무엇?

9 알고리즘 find_if() iter j = find_if(i, str.end(), space); find_if() 함수는
처음 두 인자(argument)들은 시퀀스(sequence)를 나타내는 반복자 세 번째 인자는 동작함수(predicate)로서, true나 false를 리턴한다. find_if() 함수는 동작함수가 true의 결과를 내는 요소를 찾아 멈춘다. 동작함수가 false이면, 두 번째 인자를 리턴 한다. 동작 함수(predicate) // `true' if the argument is whitespace,`false' otherwise bool space(char c) { return isspace(c); } // `false' if the argument is whitespace, ‘true' otherwise bool not_space(char c) { return !isspace(c); }

10 ret.push_back(string(i, j)); 반복자로부터 직접 스트링을 생성.
[i, j) 범위의 문자들의 복사본 string을 생성한다. s.substr(i, j-i)는 인덱스에 대해서만 동작 반복자에 대해서 작동하지 않음

11 6.1.2 회문(palindromes) 회문: 앞쪽에서 보나 뒤쪽에서 보나 철자가 같은 단어 라이브러리를 사용하지 않는 경우
예) civic, eye, madam, …. 라이브러리를 사용하지 않는 경우 string str; string::size_type size; bool flag=true; cin >> str; size=str.size() – 1; for(string::size_type i=0; i != str.size(); i++) { if(str[i] != str[size - i]) { flag = false; break; // 반복문을 벗어남 } if(flag == true) cout << "correct" << endl; else cout << "incorrect" << endl;

12 알고리즘 equal() equal(s.begin(), s.end(), s.rbegin());
두 시퀀스들을 비교하여, 그 둘이 같은 값을 가졌는지를 검사해서, 같으면 true, 다르면 false를 리턴한다. 첫 번째 시퀀스: s.begin()에서 s.end() 두 번째 시퀀스: s.rbegin()에서 첫번째 시퀀스와 동일한 크기 만큼. 따라서, 끝을 나타내는 반복자가 필요 없다. 예. 두 단어를 입력받아서, equal() 함수를 이용하여 같은 단어인지 검사하려면? bool is_palindrome(const string& s) { return equal(s.begin(), s.end(), s.rbegin()); }

13 6.1.3 URL 찾기 웹 주소를 찾는 함수를 작성해 보자.. URL(Uniform Resource Locator)의 형식 protocol-name://resource-name 예) 입력 받은 문자열에서 URL을 모두 찾아 vector에 저장하는 문제 find_urls() 함수에서는 반복자 b를 사용하여 스트링을 순회하며 :// 문자들을 찾는다. 찾았으면, 반대방향으로 protocol-name을 찾고, 원래 방향으로 resource-name을 찾는다. 13

14 find_urls() text http://www.acceleratedcpp.com more text
b=url_beg(b,e) after=url_end(b,e) find_urls() 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 URL on this line b = after; } return ret; 14

15 url_end() 함수 string::const_iterator
url_end(string::const_iterator b, string::const_iterator e) { return find_if(b, e, not_url_char); } bool not_url_char(char c) // URL에 나타날 수 있는 문자들 static const string url_ch = // c가 URL에 나타날수 있는 문자이면, false리턴 return !( isalnum(c) || find(url_ch.begin(), url_ch.end(), c) != url_ch.end()); 15

16 url_beg() 함수 text http://www.acceleratedcpp.com more text beg i
string::const_iterator url_beg(string::const_iterator b, string::const_iterator e) { static const string sep = "://"; typedef string::const_iterator iter; // i marks where the separator was found iter i = b; 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; // 식별자 앞과 뒤에 최소한 하나의 적절한 문자가 있으면 if (beg != i && !not_url_char(i[sep.size()])) return beg; } // the separator we found wasn't part of a URL; // advance i past this separator i += sep.size(); return e; 16

17 알고리즘 search() search(b, e, pb, pe)
search( i, e, sep.begin(), sep.end())에서 찾았으면, [i, e)사이에서 ‘:’의 위치를 리턴. 못 찾았으면, 두번째 반복자 e를 리턴한다. 컨테이너가 인덱싱을 지원하면, 반복자도 인덱싱 지원한다. beg[-1] *(beg-1)와 같음 i[sep.size()] 식별자 :// 뒤의 문자 *(i+sep.size())와 같음

18 URL찾기- main()함수 int main() { string s; while( getline(cin, s) ) {
vector<string> v = find_urls(s); for (vector<string>::const_iterator i = v.begin(); i != v.end(); ++i) cout << *i << endl; } return 0;

19 알고리즘 find() 사용 예 int num_to_find = 3; vector<int> v1;
for( int i = 0; i < 10; i++ ) { v1.push_back(i); } vector<int>::iterator result; result = find( v1.begin(), v1.end(), num_to_find ); if( result == v1.end() ) { cout << "Did not find any element matching " << num_to_find << endl; else { cout << "Found a matching element: " << *result << endl;