순차 컨테이너의 사용 및 문자열 분석 USING SEQUENTIAL CONTAINERS AND ANALYZING STRINGS Chapter 5

5 장에서는 … 지금까지 핵심적인 C++ 언어의 기능 및 string 과 vector 에 대해서 공부 이러한 툴만 가지고도 많은 문제를 해결할 수 있다 5 장에서는 단순한 기능 이상의 내용에 초점을 맞추어 보겠다. 그리고, 라이브러리 사용 방법에 관한 더 깊은 내용을 공부. 더 복잡한 문제를 해결할 수 있는 방법을 제시해준다 표준 라이브러리는 유용한 자료구조와 함수를 제공할 뿐 아니라, 일관성 있는 아키텍처를 제공 한다. 한 가지 종류의 컨테이너의 사용법만 배우면, 다른 모든 라이브러리의 사용법을 쉽게 이해할 수 있다. 2

5.1 학생들을 카테고리별로 분류 학생의 성적에 따라 pass/fail 로 분류 Pass: 과정을 이수한 학생을 하나의 vector 에 저장 Fail: 낙제 점수를 받은 학생들을 또 다른 vector 에 저장 절의 grade() 함수에서 계산한 성적이 60 점이 안되면. 방법 첫 번째 시도 : students 벡터의 각 레코드를 테스트해서, 이수한 학생은 pass, 낙제한 학생은 fail 에 그 레코드를 추가 두 번째 시도 : students 벡터에서 낙제 학생의 레코드만 fail 에 추가하고, students 벡터에서 그 레코드를 삭제 3 // predicate to determine whether a student failed bool fgrade( const Student_info& s) { return grade(s) < 60; }

첫 번째 시도 : pass 와 fail 벡터로 분리 두 벡터를 생성 students 의 각 레코드에 대해서, 학생의 성적에 따라 pass 나 fail 에 해당하는 레코드를 복사하여 추가 4 // 버전 1: 이수한 학생과 이수하지 못한 학생을 분리 vector extract_fails (vector & students) { vector pass, fail; for (vector ::size_type i = 0; i != students.size(); ++i) if (fgrade(students[i])) fail.push_back(students[i]); else pass.push_back(students[i]); students = pass ; // 이수 레코드 벡터를 다시 students 에 복사 return fail; // 낙제 레코드 벡터를 리턴 }

첫 번째 시도의 문제점 extract_fails() 함수 분석 pass 와 fail 을 구성할 때, 원본 레코드도 여전히 그대로 유지 for 문의 수행을 마친 상태에서, 각 학생 레코드의 두 개의 복사본이 존재 문제점 모든 학생 레코드를 담는 두 개의 복사본을 저장할 충분한 메모리가 필요하다 보다 효율적인 방법은.. 필요한 만큼 이상의 데이터를 여러 번 복사하는 일은 피해야 함 즉, 두 벡터를 생성하는 대신 pass 벡터를 없애고, students 벡터에 이수가능 학생들 레코드만 남긴다. 5

두 번째 시도 : 원하는 요소 삭제하기 학생 레코드에서 원하는 요소 삭제 students 에서 이수 불가 성적은 fail 에 추가하고, students 로부터 그 레코드를 삭제한다. 6 // 버전 2: 제대로 동작하지만 느림 vector extract_fails(vector & students) { vector fail; vector ::size_type i = 0; // invariant: elements [0, i) of students represent passing grades while (i != students.size()) { if (fgrade(students[i])) { fail.push_back(students[i]); students.erase(students.begin() + i); } else ++i; } return fail; }

두 번째 시도의 문제점 extract_fails() 함수에서 새로운 것은 vector 타입에서 제공하는 erase() 멤버함수를 이용해서 students 로부터 요소를 삭제. students.erase( students.begin() + i ); vector 로부터 요소를 제거 : 시간이 많이 걸린다 삭제된 것 다음에 있는 모든 요소들이 빠른 임의접근을 위해 모두 이동된다. 7 인덱스 i 번째 요소 : 벡터의 시작 요소 + i 이미 처리한 요소 아직 처리하지 않은 요소 FAIL students.size() 가 하나 줄어든다. 이미 처리한 요소 아직 처리하지 않은 요소 이 요소들이 앞으로 복사됨 i 번째 벡터의 크기가 변경됨 i 는 다음 요소를 가리킴

vector 에서 삽입 / 삭제 vector 는 빠른 임의접근 (random access) 에 최적화됨 인덱스를 지원 : i 번째 요소를 바로 접근할 수 있음 vector 에서 삽입 / 삭제의 효율성 vector 의 끝에 삽입, 삭제는 OK. vector 의 끝이 아닌 다른 위치에 요소를 삽입하고 삭제하는 작업은 매우 느리다. 예를 들어, 학생 모두가 낙제하는 경우에, 함수의 실행시간은 학생 수의 제곱에 비례한다. 문제는, 자료구조가 vector 에 저장되어 있기 때문. 성능 해결 방법 1) 더 적합한 자료구조에 저장 2) 초기 설계의 오버헤드를 피하는 더 빠른 알고리즘을 사용 (6.3 절에서 다룸 ) 8

vector 에서 삭제 벡터에서 삭제할 때, 벡터의 크기도 변한다. 다음 코드에서의 문제점은 ?? 9 vector ::size_type size = students.size(); while (i != size) { if (fgrade(students[i])) { fail.push_back(students[i]); students.erase(students.begin() + i); } else ++i; }

순차 접근과 임의 접근 버전 1 과 버전 2 extract_fails() 함수의 자료 접근 속성 컨테이너의 요소들을 순차적으로만 접근한다 students 의 한 요소를 접근할 때, students[i] 를 사용 이는 students 의 요소를 임의의 순서로 접근할 수 있다 extract_fails() 함수는 순차 접근만 필요로 하므로 인덱스를 사용할 필요가 없다. 순차접근 방식만을 지원하는 연산들을 사용하여 컨테이너 요소에 접근하도록 함수를 다시 작성 할 필요 있다. 인덱스 대신에 C++ 라이브러리에서 제공하는 반복자를 이용 10 순차 접근 (sequential access) 임의 접근 (random access)

5.2 반복자 (iterator) 반복자의 성질 컨테이너와 컨테이너 안에 있는 요소를 구별시킨다 그 요소의 값을 확인할 수 있다 컨테이너 안에 있는 요소들 간에 이동을 할 수 있는 연산을 제공한다 컨테이너가 효율적으로 처리할 수 있는 방식으로 가용한 연산들을 한정시킨다 반복자는 인덱스와 유사하게 동작하므로, 인덱스를 사용하는 대신 반복자를 사용하는 프로그램으로 대체 가능. 11 for (vector ::size_type i = 0; i != students.size(); ++i) cout << students[i].name << endl; for (vector ::const_iterator iter=students.begin(); iter != students.end(); ++iter) cout << (*iter).name << endl; 인덱스 사용 반복자 사용

반복자 타입 모든 표준 컨테이너 ( 벡터 포함 ) 에서 제공하는 반복자 타입 container-type::const_iterator container-type::iterator 여기에서 container-type 은 vector 와 같은 컨테이너 타입이다. 반복자를 이용하여 컨테이너에 저장된 값을 변경한다면 : iterator 타입을 사용 저장된 값을 읽기만 한다면 : const_iterator 타입을 사용 12

반복자 연산 iter = students.begin(); // iter 는 students 의 첫 번째 요소를 가리킴 begin() 은 컨테이너의 초기 위치를 가리키는 vector ::iterator 를 리턴 iter != students.end(); // 컨테이너의 끝에 도달했는지를 확인 end() 는 컨테이너의 마지막 위치를 가리키는 vector ::iterator 를 리턴 == 와 != 비교 연산이 가능 ++iter 컨테이너의 다음 요소를 가리키도록 이동시킨다 반복자 타입에 대해 오버로드된 증가 연산자이다. (*iter).name // 간편한 사용법 : iter->name 역참조 연산자 (dereference operator) * : 반복자 iter 가 참조하는 요소에 해당하는 lvalue 를 리턴 13

반복자에 + 연산 students.erase( students.begin()+i ) 의 뜻 처음 요소 + i 는 i 번째 요소를 가리킨다. (random access) 반복자와 인덱스 타입이 + 의 의미를 결정함 임의 접근 인덱스를 지원하지 않는 컨테이너는 반복자 + i 연산이 정의되지 않는다 즉, students.begin() + i 는 컴파일 되지 않는다. 그러한 컨테이너는 반복자를 통해서 순차 접근은 허용되면서, 해당 요소에 대한 임의 접근은 막게 된다. 14

5.3 인덱스 대신 반복자 사용하기 extract_fails() 함수 : 인덱스를 사용하지 않는 버전 15 // version 3: iterators but no indexing; still potentially slow vector extract_fails(vector & students) { vector fail; vector ::iterator iter = students.begin(); while ( iter != students.end() ) { if ( fgrade(*iter) ) { fail.push_back(*iter); iter = students.erase(iter); } else ++iter; } return fail; } erase 로부터 리턴 된 값을 iter 에 저장했는데, 왜 ??

5.4 성능향상을 위해 자료구조 다시 고민하기 vector 는 요소를 끝에 추가하는 경우 한번에 하나씩 증가된다면 효율적이다 (3.2.3 절 ) vector 의 안쪽에 삽입하거나 삭제하는 경우 삽입 또는 삭제 된 것 다음에 있는 모든 요소들이 이동됨 실행시간 측면에서 보면, vector 요소들의 개수의 제곱에 비례해서 느려진다. 매번 입력이 두 배씩 늘어난다면, 실행시간이 네 배가 느려진다. 더 빠르게 하려면, 컨테이너 상의 어느 위치에서나 효과적으로 요소들을 삽입, 삭제시킬 수 있는 자료구조를 사용해야 ! 16

5.5 list 타입 list 는 컨테이너의 어느 위치에나 빠른 삽입과 삭제를 제공하도록 최적화되어 있다 vector 처럼 list 는 여러 타입의 객체를 담을 수 있는 컨테이너 list 도 vector 처럼 템플릿 (template) 으로 정의되어 있기 때문에 vector 와 list 비교 list 는 vector 보다 더 복잡한 구조를 가진다 컨테이너를 순차적으로만 접근한다면 vector 보다 더 느리다 많은 요소들을 컨테이너의 중간에서 삽입 / 삭제한다면, 입력이 많을수록 list 가 더 빨라진다. vector 로 동작하는 프로그램을 list 로 동작하는 프로그램으로 변환 가능하다. 그 역도 가능. vector 는 지원하지만, list 는 지원하지 않는 주요 연산 : 인덱싱 17

list 와 vector vector 자료구조 저장 예. array-like, random-access/ indexing structure list 자료구조 저장 예. sequentially linked structure 18 vector 연산 push_back pop_back list 연산 push_back pop_back push_front pop_front

list 에서 요소 삭제 예. list 에서 한 요소를 삭제하는 것은 list 의 크기와 상관없이 효율적이다. 19 list ::iterator p = s.begin(); ++p; list ::iterator q = s.erase(p);

list 를 사용한 버전 vector 대신 list 를 사용하는 extract_fails() 함수 버전 3 의 함수에서 vector 를 list 로 바꾼 것 밖에 없음 라이브러리가 연산들을 어떻게 구현하는지에 대한 상세 내용은 꽤 다르다. 20 // version 4: use `list' instead of `vector' list extract_fails(list & students) { list fail; list ::iterator iter = students.begin(); while (iter != students.end()) { if (fgrade(*iter)) { fail.push_back(*iter); iter = students.erase(iter); } else ++iter; } return fail; }

list 를 사용한 main() 함수 21 int main() { list vs; Student_info s; string::size_type maxlen = 0; while (read(cin, s)) { maxlen = max(maxlen, s.name.size()); vs.push_back(s); } vs.sort(compare); list fails = extract_fails(vs); list ::iterator i; for (i= fails.begin(); i != fails.end(); ++i) cout name << " " << grade(*i) << endl; return 0; }

list 와 vector 의 중요한 차이점 차이점 1: 반복자에 대한 연산으로 인한 효과 vector 에서 erase 와 push_back 은 반복자를 무효화한다. vector 로부터 한 요소를 erase 하면, 그 다음 요소들이 이동됨 삭제된 요소를 가리키는 반복자 및 일련의 반복자들이 무효화됨 vector 에 push_back 으로 한 요소를 추가하면, 새로운 요소를 위한 공간을 확보하기 위해 전체 vector 가 재할당됨 해당 vector 를 가리키고 있는 모든 반복자들은 무효화됨 list 에서 erase 와 push_back 은 반복자를 무효화시키지 않는다. 실제로 삭제된 요소를 가리키는 반복자만이 무효화된다. 22

list 와 vector 의 중요한 차이점 차이점 2: 임의 접근 여부 vector 는 임의접근 가능. vector 값을 정렬하기 위해, 표준라이브러리의 sort() 함수 사용 list 클래스 반복자는 임의 접근 기능을 제공하지 않는다 list 에 저장된 값을 정렬하기 위해 표준라이브러리의 sort() 함수를 사용할 수 없다 list 클래스는 sort 멤버함수를 제공한다 : list 정렬에 최적화 됨 23 list students; students.sort(compare); vector students; sort(students.begin(), students.end(), compare);

도대체 어떤게 좋다는 거죠 ? vector 가 더 적합한 경우 : 요소들을 순차적으로 접근만 하는 코드 list 가 더 적합한 경우 : 컨테이너의 반복자를 이용해서 요소를 삭제하는 코드 최적의 자료구조는 성능이 더 좋은 자료구조이다. 입력이 많지 않은 경우, list 가 vector 보다 더 느리다. 입력이 많은 경우, 부적절하게 ( 즉 삽입 삭제가 많은 경우 ) vector 를 사용하면 list 를 사용하는 것보다 훨씬 느리다. 성능 테스트 예 : 24 레코드 사이즈 listvector 초 7, 초 6.7 초 73, 초 초

5.6 string 분석하기 string 은 특별한 종류의 컨테이너 컨테이너는 문자들만을 포함 지원하는 연산 : 인덱싱, vector 반복자와 유사한 반복자 제공 s 가 적어도 하나의 문자를 포함하는 string 이면, s 의 첫번째 문자는 s[0], 마지막 문자는 s[s.size()-1] 예 : 전체 라인의 입력을 읽어서 해당 라인의 단어들을 공백문자로 구분되는 단어들로 분리하고 싶은 경우 입력 라인 : 분리된 단어 : “Given”, “the”, “existence”, “as” vector 에 저장 25 Given the existence as

26 vector split(const string& s) { vector ret; typedef string::size_type string_size; string_size i = 0; // invariant: we have processed characters [original value of i, j) while (i != s.size()) { // ignore leading blanks // invariant: characters in range [original i, current i) are all spaces while (i != s.size() && isspace (s[i])) ++i; // find end of next word string_size j = i; // invariant: none of the characters in range [original j, current i) is a space while (j != s.size() && ! isspace (s[j])) // 단축 평가 : && 와 | | ++j; // if we found some nonwhitespace characters if (i != j) { // copy from `s' starting at `i' and taking j-i chars ret.push_back( s. substr (i, j - i) ); i = j; } return ret; } Given the existence as ij

string 관련 함수 isspace( c ) 헤더가 필요 입력문자 c 가 공백문자 ( 스페이스, 탭, 백스페이스, 라인종료문자 ) 이면 true 를 리턴 ! isspace(c) s.substr(i, n) 문자열의 일부분을 얻는 함수 스트링 s 의 i 번째 위치부터 n 개의 문자열을 리턴 getline(cin, s) 함수 라인의 끝을 나타내는 문자 (‘\n’) 를 만날 때 까지 읽어서, 스트링 s 에 저장한다. 즉, 한 줄을 입력받는다. 주의사항 : 27 cin >> x; cin.ignore(); // cin 다음에 getline 이 올때, 버퍼에서 ‘\n’ 을 제거 getline(cin, s)

split() 함수를 테스트 28 #include using namespace std; int main() { string s; // read and split each line of input while ( getline(cin, s) ) { vector v = split(s); // write each word in `v' for (vector ::size_type i = 0; i != v.size(); ++i) cout << v[i] << endl; } return 0; }