1. Chapter 5 Using sequential containers and analyzing strings

1.1. 5.1 Separating students into categories

1.1.1. 5.1.1 Erasing elements in place
1.1.2. 5.1.2 Sequential versus random access

1.2. 5.2 Iterators

1.2.1. 5.2.1 Iterator types
1.2.2. 5.2.2 Iterator Operations
1.2.3. 5.2.3 Some syntactic sugar
1.2.4. 5.2.4 The meaning of students.erase(students.begin() + i)

1.3. 5.3 Using iterators instead of indices

1.4. 5.4 Ranking our data structure for better performance

1.5. 5.5 The list type

1.5.1. 5.5.1 Some important differences
1.5.2. 5.5.2 Why bother?

1.6. 5.6 Taking strings apart

1.7. 5.7, 5.8

[edit]

1. Chapter 5 Using sequential containers and analyzing strings ¶

여태까지 vector랑 string 갖고 잘 놀았다. 이제 이것들을 넘어서는 것을 살펴볼 것이다. 그러면서 라이브러리 사용법에 대해 더 깊게 이해하게 될것이다. 라이브러리는 자료구조?함수만을 제공해주는 것이 아니다. 튼튼한 아키텍쳐도 반영해준다. 마치 vector의 사용법을 알게 되면, 다른것도 쉽게 배울수 있는것처럼...

[edit]

1.1. 5.1 Separating students into categories ¶

f뜬 학생과 아닌 학생으로 나눠 보자.

~cpp 
bool fgrade(const Student_info& s)
{
	return grade(s) < 60;
}

vector<Student_info> extract_fails(vector<Student_info>& students)
{
	vector<Student_info> pass, fail;
	for(vector<Student_info>::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;
	return fail;
}

참조로 넘어간 students의 점수를 모두 읽어들여서, 60 이하면 fail 벡터에, 아니면 pass 벡터에 넣은 다음, students 벡터를 pass벡터로 바꿔준다. 그리고 fail을 리턴해준다. 즉 students에는 f 아닌 학생만, 리턴된 vector에는 f 뜬 학생만 남아있게 되는 것이다. 뭔가 좀 삐리리하다. 더 쉬운 방법이 있을 듯하다.

[edit]

1.1.1. 5.1.1 Erasing elements in place ¶

그렇다. 메모리 낭비가 있는 것이다. for루프가 끝날때에는 중복되는 두개의 벡터가 존재하는 것이다. 그래서 우리가 쓸 방법은 만약 f면 fail에 추가하고, f 아니면 그 자리에서 지우는 것이다. 반갑게도 이런 기능이 있다. 근데 졸라 느리다. 입력 데이터의 양이 커질수록 성능 저하는 급격하다. 벡터에서는 중간에 하나를 지우면, 메모리를 통째로 다시 할당하고, 지워주는 짓을 해야한다. O(n*n)의 시간이 필요한것으로 알고 있다. 벡터는 임의 접근이 가능한 대신, 중간 삽입이나 중간 삭제의 퍼포먼스를 포기한 것이다. 이제부터 여러가지 방법을 살펴볼 것이다.

먼저 느리지만, 직관적인 방법부터 살펴보자.

~cpp 
vector<Student_info> extract_fails(vector<Student_info>& students)
{
	vector<Student_info> fail;
	vector<Student_info>::size_type i = 0
	while(i != students.size()) {
		if(fgrade(students[i])) {
			fail.push_back(students[i]);
			students.erase(students.begin() + i);
		} else
			++i;
	}
	return fail;
}

왜 students.erase(studentsi) 하지 않는가? 모든 컨테이너에 일관성을 제공하기 위해서라고 한다. 바로 반복자라 불리우는 것을 이용해, (포인터보다 반복자가 먼저 나오네요.) 동일한 방법으로 제어를 할수 있는 것이다.
그림 보면 알겠지만, 복사 겁나게 해댄다. 하나 지울때마다 그 뒤에 있는걸 다 복사하는 것이다. 만약에 모두 fail이라면? 끔찍하다.
또한, 지워줌으로써 컨테이너의 사이즈가 변한다. 즉 모든 학생을 다 검사하지 못할수도 있다. 그래서 다음과 같이 바꿔주어야 한다.

~cpp 
vector<Student_info> extract_fails(vector<Student_info>& students)
{
	vector<Student_info> fail;
	vector<Student_info>::size_type i = 0;
         vector<Student_info>::size_type size = students.size();
	while(i != size) {
		if(fgrade(students[i])) {
			fail.push_back(students[i]);
			students.erase(students.begin() + i);
		} else
			++i;
	}
	return fail;
}

[edit]

1.1.2. 5.1.2 Sequential versus random access ¶

위의 벡터는 임의 접근이 필요하지 않다. 그냥 순차적으로 접근할 뿐이다. 임의접근을 포기함으로써 생기는 여러가지 이득이 있는 컨테이너가 있을 것이다. 그보다 먼저 컨테이너를 효과적으로 제어할수 있게 해주는 반복자라는 것을 먼저 살펴보자.

[edit]

1.2. 5.2 Iterators ¶

여태껏 잘쓰던 벡터형 변수n은 벡터의 n번째 요소를 말한다. 지금까지 하던거 보면 루프 안에서 ++i 이거밖에 없다. 즉 순차적으로만 놀았다는 뜻이다. 우리는 알지만 컴파일러는 알길이 없다. 여기서 반복자(Iterators)라는 것을 알아보자.

컨테이너와 컨테이너 안의 요소를 확인
그 요소 안에 저장되어 있는 값 확인
컨테이너 안의 요소들 사이를 왔다갔다 할수 있는 기능
컨테이너가 효과적으로 다룰수 있는 연산만을 가지고 놀도록 제한하는 기능

인수曰 : STL을 사용할때에는 반복자를 이용하는 것이 표준이라 한다.

인덱스로 짠 코드를 반복자로 짠 코드로 바꾼 예

~cpp 
for(vector<Student_info>::size_type i = 0 ; i != students.size() ; ++i)
	cout << students[i].name << endl;

~cpp 
for(vector<Student_info>::const_iterator i = students.begin() ; i != students.end() ; ++i)
	cout << (*i).name << endl;

생소한게 보이지 않는가? 하나하나씩 살펴보자.

[edit]

1.2.1. 5.2.1 Iterator types ¶

표준 컨테이너에 정의 되어 있는 반복자의 종류는 다음 두가지다.

const_iterator : 값을 변경시키지 않고 순회할때
iterator : 그냥 순회할때

세부적인 건 몰라도 된다.

필요에 따라 iterator에서 const_iterator로 캐스팅된다. 반대는 안된다.

[edit]

1.2.2. 5.2.2 Iterator Operations ¶

begin()과 end()는 각각 컨테이너의 맨 처음 요소를 가리키는 반복자와, 맨 마지막에서 한칸 지난 것을 가리키는 반복자를 리턴해준다.

++i : 그냥 쓰면 된다. 각 컨테이너마다 구현은 다를테지만, 놀라울 정도의 추상화로 사용자들로 하여금 모르고 써도 되게 만들었다. 반복자를 하나씩 증가시키는 것이다.

'*' : 역참조 연산자라 불리운다.

(*i).name : 반복자 i가 가리키는 요소의 멤버 name을 말한다. 괄호를 꼭 써주자. 우선순위가 .이 *보다 높기 때문에 에러난다.

[edit]

1.2.3. 5.2.3 Some syntactic sugar ¶

(*i).name 이렇게 하기 귀찮다. i->name 이렇게 하면 된다.

[edit]

1.2.4. 5.2.4 The meaning of students.erase(students.begin() + i) ¶

begin()이 맨 처음 요소를 가리키는 반복자를 리턴해준다고 했다. 그럼 i를 더하면? i번쨰 요소를 가리키는 반복자가 리턴될것이다.

하지만 임의 접근을 지원하지 않는 컨테이너에다 저짓하면 안된다. + 연산자가 정의되어 있지 않기 때문에 컴파일 에러 뜬다.

[edit]

1.3. 5.3 Using iterators instead of indices ¶

인덱스 쓰던 함수를 반복자로만 바꿔 보자.

~cpp  
vector<Students_Info> extract_fails(vector<Student_info>& students)
{
	vector<Student_info> fail;
	vector<Student_info>::iterator iter = students.begin();
	while(iter != students.end()) {
		if(fgrade(*iter)) {
			fail.push_back(*iter);
			iter = students.erase(iter);
		} else
			++iter;
	}
	return fail;
}

아까는 const였는데 이번엔 왜 아니냐고? 컨테이너 안에 있는 것을 지우지 않는가. 즉 변형시킨다는 것이다.

또 신기한게 보인다. 왜 students.erase(iter) 해준것을 또 iter에다 대입해주었는가? 삭제하면 반복자가 모두 갱신되기 때문이다. 지운 뒷부분은 몽땅 재할당 해야하니... 지금은 무슨 말인지 몰라도 좋다. 그렇다는 것만 알아두자. erase는 방금 지운 바로 그 부부을 리턴해준다.

또 코드 최적화 한다고 다음고 같은 삽질을 하는 사람도 있을 것이다.

~cpp 
while(iter != students.end())
/*...*/

을

~cpp 
vector<Student_info>::iterator iter = students.begin(). end_iter = students.end();
while(iter != end_iter)
/*...*/

이렇게 말이다. 하지만 안된다. 아까 말했듯이, 하나 지우면 그 뒤의 반복자는 모두 갱신되기 때문에, 미리 저장해놓은 end_iter는 쓸모가 없어진다. 쓰레기 값이 남는 것이다.

[edit]

1.4. 5.4 Ranking our data structure for better performance ¶

벡터는 임의 접근을 지원하는 대신에, 중간 삽입, 삭제의 성능이 꼬랐다. 그러므로 중간 삽입, 삭제가 최적화된 새로운 자료구조를 생각해 보자.

[edit]

1.5. 5.5 The list type ¶

바로 list다. 중간 삽입과 삭제를 상수시간 내에 수행할수 있다. 이제 vector로 짠 코드를 list로 짠 코드로 바꿔보자. 바뀐게 별로 없다. vector가 list로 바뀐거 말고는... 다시 한번 말하지만 list는 임의 접근을 지원하지 않는다. 따라서 vector에서 쓰던것처럼 [] 쓰면 안된다.

[edit]

1.5.1. 5.5.1 Some important differences ¶

벡터는 삽입, 삭제 할때마다 메모리를 몽땅 재할당한다. 따라서 ~~.end()는 버그의 온상이 왼다. 계속 바뀌므로... 하지만 list는 삽입, 삭제한다고 몽땅 재할당하지 않는다. 그래서 빠른 것이다. 또한 임의 접근을 지원하는 컨테이너만 쓸수 있는 표준 알고리즘 sort도 당연히 쓸수 없다. 그래서 list의 멤버함수로 sort가 있다. 다음과 같이 써주자.

~cpp 
students.sort(compare);

[edit]

1.5.2. 5.5.2 Why bother? ¶

표를 보면 알겠지만, 파일 크기가 커질수록 vector의 요소 삽입, 삭제 시간은 비약적으로 증가한다. list는 별로 안 증가한다.

[edit]

1.6. 5.6 Taking strings apart ¶

string도 vector처럼 쓸수 있다. 실제로는 vector<char>이니... vector의 대부분의 기능을 지원한다. []과 반복자는 물론 size() 등등도..

그러면서 주어진 string을 공백을 기준으로 자른 다음 vector에 넣어서 리턴하는 예제를 보여주고 있다. 별로 볼건 없다.

[edit]

1.7. 5.7, 5.8 ¶

그냥 string가지고 화면에 뿌리는 이상한 장난치고 있다. 별로 볼거 없다.

지금 보니까 쓸만한 팁이 하나 있다. 바로 한 컨테이너에 다른 컨테이너의 내용들을 넣는 예제이다.

~cpp 
for(vector<string>::const_iterator i = bottom.begin(); i != bottom.end(); ++i)
    ret.push_back(*it);

이렇게 쓸것을,

~cpp 
ret.insert(ret.end(), bottom.begin(), bottom.end());

이렇게 간단히 쓸수 있다.

AcceleratedC++

AcceleratedC++/Chapter5

Contents

1. Chapter 5 Using sequential containers and analyzing strings ¶

1.1. 5.1 Separating students into categories ¶

1.1.1. 5.1.1 Erasing elements in place ¶

1.1.2. 5.1.2 Sequential versus random access ¶

1.2. 5.2 Iterators ¶

1.2.1. 5.2.1 Iterator types ¶

1.2.2. 5.2.2 Iterator Operations ¶

1.2.3. 5.2.3 Some syntactic sugar ¶

1.2.4. 5.2.4 The meaning of students.erase(students.begin() + i) ¶

1.3. 5.3 Using iterators instead of indices ¶

1.4. 5.4 Ranking our data structure for better performance ¶

1.5. 5.5 The list type ¶

1.5.1. 5.5.1 Some important differences ¶

1.5.2. 5.5.2 Why bother? ¶

1.6. 5.6 Taking strings apart ¶

1.7. 5.7, 5.8 ¶