Chapter 4. Containers and Algoritms

4.1 Libraries 

프로그래밍 언어에는 라이브러리가 필요하다. 

C++ 의 STL 기능들을 살펴볼 것이다. 

4.1.1 Standard-Library Overview

제공되는 라이브러리는 아래와 같이 분류됨.

* 런타임 언어 지원 ( 할당과 런타임 타입 정보 )

* C standard library ( 타입시스템에 위배하는 것에 대한 최소한의 수정 )

* 문자열과 I/O 스트림 (국제적 문자셋과 지역화 지원을 포함)

* 컨테이너의 프레임 워크 / 알고리즘 

* 숫자 계산

* 정규식 표현

* 동시성 프로그래밍을 위한 지원

* 템플릿 메타 프로그래밍을 위한 유틸들 ( type traits ), 제네릭 프로그래밍, 제너럴 프로그래밍

* 스마트 포인터 / 가비지 콜렉터

* 특별한 목적의 컨테이너 ( array / bitset / tuple )

라이브러리를 써야하는 이유

* 프로그래머의 수준에 상관없이 유용하다

* 오버헤드 없이 일반적인 형태 제공

* 배우기 쉽고 간단한 사용

4.1.2 The Standard-library Headers and Namespace 

헤더 포함으로 이용가능, std:: prefix

4.2 Strings

문자열 리터럴에서 제공할 수 있는 정보를 보충하기 위한 string 타입을 제공함.

문자열붙이기 (concatenation) 같은 문자열 연산에 용이.

string 은 move 생성자를 가지고 있으므로 긴 문자열이라도 효율적으로 반환 될 수 있음.

String 은 수정가능하므로 = , += , [], substring 연산들이 지원된다.

또 비교 연산도 가능.

4.3 Stream I/O

포맷팅된 캐릭터 인풋과 아웃풋을 iostream 을 통해 지원한다.

4.3.1 Output

모든 빌트인 타입에 대해 출력을 정의해 놓았음. 또 사용자 정의 타입에 대해서도 아웃풋을 정의하기 용이하다.

<< ("put to") 연산자는 ostream 타입의 객체에 대해 사용되며, 출력을 위해 사용된다.

cerr 는 에러 리포팅을, cout 은 표준 출력을 의미.

cout 으로 쓰여진 값은 기본적으로 문자열의 시퀀스로 변환 된다.

즉 cout << 10; 에서 1다음에 0이 있는 문자열의 시퀀스로 노출되게 된다.

캐릭터 상수는 따옴표로 나타내지며 캐릭터는 숫자가 아닌 문자로 취급된다.

int b = 'b'; 

char c = 'c';

cout << 'a' << b << c 

일때 'b' 는 98이므로 다음과 같이 출력됨 a98c

4.3.2 Input

istream 을 입력을 위해 제공. 반대로 >> ("get from") 연산을 포함

공백은 입력을 종료시키므로 라인을 얻기위해서는 getline() 와 같은 별도함수 필요.

개행문자는 버려진다.

확장을 위한 정립된 방식이 존재하기 때문에 먼저 최대 사이즈를 계산할 필요가 없다.

4.3.3 I/O of User-Defined Types

ostream& operator<<(ostream& os, const Entry& e)

{

return os << e.name << e.number ; 

}

와 같이 사용자 정의 타입도 사용가능

비슷하게

istream& operator>>(istream& is, Entry& e)

{

char c,c2;

if (is>>c && c == '{' && is>>c2 )

return is;

else{

is.setf(ios_base::failbit);

return is;

}

}

와 같이 정의된 형식의 입력인지 확인하는 용도로 사용될 수 있다.

is >> c 는 "is 로부터 읽어 c 로 넣는데 성공했는가?" 의 의미를 가진다.

is.get(c) 는 공백을 그냥 넘어가지 않는다. ( 입력한다 ) 

명령행 SVN

- Trouble Shooting

다음과 같은 문제가 발생했을때 다음 명령어를 사용하여 커밋하도록 한다.

문제

* This Commit is not recursive, and there are moved/renamed folders selected for commit. Such moves/renames are always performed recursively in the repository. Do you want to commit anyway ?"

- 이 커밋은 이름이나 옮겨진 폴더의 하위 경로까지 선택되지 않았습니다. 그대로 진행하시겠습니까 ?

전체 커밋을 시도하기 위해

svn commit --depth infinity . -m "Merge"

와 같이 입력한다.

Chap 3. A tour of C++: Abstraction Mechanisms ( 추상화 메커니즘 )

3.2 Classes

잘 선택된 클래스의 집합으로 구성된 프로그램은 이해가 쉽고 빌트인 타입만을 사용하여 구성된 것보다 더 올바른 구성이다.

3가지 중요 클래스

* Concrete classes

* Abstract classes

* Classes in class hierarchies

더 많은 클래스가 이 클래스를 조합하여 구현될 수도 있다.

3.2.1 Concrete Types

빌트인 타입과 비슷하게 동작한다. 이 타입의 정의의 특징은 그것의 표현이 정의의 일부에 있다는 것에 있다.

이 타입은 다음과 같은 동작이 가능하다.  

* 구체화 타입의 객체는 스택에 위치한다.

* 객체를 직접 참조한다. ( 포인터나 레퍼런스를 통하지 않고 ) 

* 객체를 즉시, 완벽하게 초기화 하는 것 가능

* 객체를 복사하는 것이 가능

private 로 representation 을 위치 시킬수도 있지만 어쨌든 존재하는 것이므로 변경된다면 재컴파일이 필요.

유연성을 향상시키기위해 representation 의 주요 부분을 free store 에 두고 클래스 객체 그 자체에 저장된 부분을 통해 접근하게 하는 것도 방법. vector / string 은 그렇게 구현됨. 

3.2.1.1 An Arithmetic Type

class complex {

double re, im; // representation: two doubles

public:

complex(double r, double i) :re{r}, im{i} {} // construct complex from two scalars

complex(double r) :re{r}, im{0} {} // construct complex from one scalar

complex() :re{0}, im{0} {} // default complex: {0,0}

double real() const { return re; }

void real(double d) { re=d; }

double imag() const { return im; }

void imag(double d) { im=d; }

complex& operator+=(complex z) { re+=z.re , im+=z.im; return ∗this; } // add to re and im

// and return the result

complex& operator−=(complex z) { re−=z.re , im−=z.im; return ∗this; }

complex& operator∗=(complex); // defined out-of-class somewhere

complex& operator/=(complex); // defined out-of-class somewhere

};

클래스 정의 그자체는 representation 에 접근하기 위한 연산을 포함하고 있다.

클래스에 정의한 함수들은 기본적으로 인라인화 되며, 이것은 함수콜을 통하지 않게 됨을 의미, 빠른 연산을 가능하게 할 수 있다.

 인자 없는 생성자를 default constructor 라고 하며 이것은 초기화 되지 않은 객체가 존재하지 않음을 보장해 준다.

함수 옆에 const 키워드는 이 함수가 이 객체에 대해 변경을 하지 않을 것임을 의미한다.

많은 연산자들은 complex 에 직접적인 표현에 대한 접근을 요하지 않으므로 클래스 정의로부터 분리하여 정의 할 수 있다.

complex operator+(complex a, complex b) { return a+=b; }

complex operator−(complex a, complex b) { return a−=b; }

complex operator−(complex a) { return {−a.real(), −a.imag()}; } // unar y minus

complex operator∗(complex a, complex b) { return a∗=b; }

complex operator/(complex a, complex b) { return a/=b; }

이 연산자를 overloaded operators ( 연산자 오버로드 ) 라고 함. 

단항 연산자는 오버로드가 불가능하며 기본 연산자 의미에 맞지않는 연산자로 오버로드하는 것은 불가능하다.

3.2.1.2 A Container

컨테이너는 요소들의 집합을 포함한 것들을 뜻한다. 따라서 Vector 도 훌륭한 컨테이너.

하지만 우리가 정의한 vector 는 리소스를 반환하지 않는 것에서 큰 문제가 있는데, 

C++ 에 가비지 컬렉터의 의미가 있지만 어떤 환경에서는 이용하지 못할 수도 있고, 제공하는 것보다 더 정밀한 소멸이 필요할 수도 있다.

이때 사용할 수 있는 메커니즘이 소멸자이다.

다음과 같이 delete 키워드를 붙여 사용. 

˜Vector() { delete[] elem; } // destructor: release resources

벡터는 빌트인 타입과 같은 룰로 명명되고, 영역이 정의되며, 할당되며, 라이프타임등이 관리된다.

constructor 에서 리소스를 얻고 destructor 에서 리소스를 반환하는것은 Resource Acquisition Is Initialization / RAII 로 알려져 있으며, 

에러를 만들지 않는 습관이므로, 중요하다

3.2.1.3 Initializing Container

벡터는 요소를 컨테이너에 넣는 편리한 방법이 필요하다.

두가지 방법을 선호한다.

* initializer-list constructor : 요소의 리스트로 초기화

* push_back() : 새 엘리먼트를 시퀀스의 종단에 추가

다음과 같이 선언할수 있다. 

class Vector {

public:

Vector(std::initializ er_list<double>); // initialize with a list

// ...

void push_back(double); // add element at end increasing the size by one

// ...

};

push_back 은 임의의 개수의 입력을 넣는데 좋다.

Vector read(istream& is)

{

Vector v;

for (double d; is>>d;) // read floating-point values into d

v.push_back(d); // add d to v

return v;

}

이때 is 는 eof 를 만나거나 포멧팅에러를 만나면 종료된다.

{1,2,3,4} 와 같이 리스트를 전달받았을때 STL 에 정의된 std::initializer_list 타입으로 컴파일러가 생성하여 프로그램에 전달해주게 되며,

따라서 위와 같은 생성자가 호출될 수 있다.

3.2.2 Abstract Types

추상화 타입은 유저를 자세한 구현으로부터 자유롭게 한다. 

인터페이스를 표현으로부터 분리하고 지역변수를 포기하는 식으로 얻어질 수 있다. 

표현에 대한 정보가 없기 때문에 힙영역에 할당 되어야 하며, 따라서 레퍼런스와 포인터로 취급된다. 

벡터의 추상화 타입 container 를 정의하였다.

class Container {

public:

virtual double& operator[](int) = 0; // pure virtual function

virtual int size() const = 0; // const member function (§3.2.1.1)

virtual ˜Container() {} // destructor (§3.2.1.2)

};

virtual 키워드는 이 추상타입으로부터 파생된 클래스가 다시 정의할 수도 있음을 의미한다.

= 0 는 pure virtual function 임을 의미하는 것이며 반드시 정의해야함을 의미한다.

이 추상화 타입은 다음과 같이 이용 될 수 있다.

void use(Container& c)

{

const int sz = c.size();

for (int i=0; i!=sz; ++i)

cout << c[i] << '\n';

}

size() 와 [] 는 어떠한 구현에 대한 정보도 갖지 않았지만 이용될 수 있다. 이런 다른 클래스로의 다양함의 인터페이스를 제공하는 클래스를 polymorphic type 이라 칭한다.

어떤 표현을 초기화해야할지 알 수 없기 때문에 constructor 가 존재하지 않으며, 반대로 소멸자는 추상화 타입이 포인터나 레퍼런스로 취급되기때문에 컨테이너를 파괴하기 위해 정의 되어 있다.

이 추상화 타입을 부모로 하여 vector_container 를 선언 할 수 있다.

class Vector_container : public Container { // Vector_container implements Container

Vector v;

public:

Vector_container(int s) : v(s) { } // Vector of s elements

˜Vector_container() {}

double& operator[](int i) { return v[i]; }

int size() const { return v.siz e(); }

};

[] 와 size() 는 오버라이드 되어있으며 소멸자 또한 부모 소멸자를 오버라이드 했다. 

자식 소멸자는 부모로부터 묵시적으로 호출된다.

비슷하게 List_container 도 선언 할 수 있으며 ,

g() 함수는 Vector_contanier 를 사용하게, h() 함수는 List_container 를 사용하게 구현해 보았다.

3.2.3 Virtual Functions

이제 다시 use() 함수를 고려해보면, 어떤 [] 를 호출해야할지 어떻게 알 수 있을까?

g() 함수에서는 vector_container의 [] 를 호출해야하고, h() 함수에서는 list_container의 [] 를 호출해야 하지만 

use() 함수에서는 vector 인지 list 인지 정확한 정보를 알 수 없다.

비밀은 vtbl ( virtual function table ) 이다. 

이 테이블에서는 가상함수의 포인터를 인덱싱하고 있으며, 따라서 container 의 인덱스와 vector / list 의 인덱스를 매칭시켜 적합한 함수가 호출되게 된다. (부모 vtbl 의 인덱스를 확인, 자식 vtbl에 매칭되는 함수를 호출한다 )

3.2.4 Class Hierachies

이전의 컨테이너로부터 우리는 간단한 클래스 계층구조를 살펴봤다.

클래스 계층구조란, 계층적인 관계를 나타내는 개념이라고 보면 된다.

원과 삼각형 모두 모양이라는 큰 개념의 한 종류라고 보는 식이다.

계층구조를 이용, 정의.....위와 별 다를게 없음, 중략... 

추상클래스에서는 가상 소멸자를 정의하는게 중요한데, 자식클래스의 객체는 보통 추상부모 클래스로부터 제공된 인터페이스를 통해 조작되기 때문이다. 특히, 부모의 포인터를 통해 삭제될 수 있다. 따라서 가상 함수 콜 메커니즘이 적절한 소멸이 이뤄지도록 보장해준다.

클래스 계층구조는 2가지 장점이 있다.

* 인터페이스 상속 : 부모 클래스의 객체가 필요한 어떤 곳에서도 자식 클래스의 객체가 이용될 수 있다. 

* 구현 상속 : 자식클래스의 구현을 간단히 한 함수/ 데이터를 제공하는 것도 가능하다.

다음과 같이 사용했다고 하자.

enum class Kind { circle, triangle , smiley };

Shape∗ read_shape(istream& is) // read shape descriptions from input stream is

{

// ... read shape header from is and find its Kind k ...

switch (k) {

case Kind::circle:

// read circle data {Point,int} into p and r

return new Circle{p,r};

case Kind::triangle:

// read triangle data {Point,Point,Point} into p1, p2, and p3

return new Triangle{p1,p2,p3};

case Kind::smiley:

// read smiley data {Point,int,Shape,Shape,Shape} into p, r, e1 ,e2, and m

Smiley∗ ps = new Smiley{p,r};

ps−>add_eye(e1);

ps−>add_eye(e2);

ps−>set_mouth(m);

return ps;

}

}

void user()

{

std::vector<Shape∗> v;

while (cin)

v.push_back(read_shape(cin));

draw_all(v); //call draw() for each element

rotate_all(v,45); //call rotate(45) for each element

for (auto p : v) delete p; // remember to delete elements

}

user() 는 어떤 shape 에 대해 조작하고 있는지 어떠한 아이디어도 없다.

한번 컴파일 되고 나면 새로운 shape 가 추가되더라도 새로 컴파일 하지 않아도 정상적으로 동작하게 된다.

user() 외에는 shape 에 대한 포인터가 없기 때문에 여기서 반환을 진행한다. 

경험있는 프로그래머는 이 코드의 문제를 눈치챘을 것이다.

* user 는 read_shape() 로부터 반환된 포인터를 delete 하는데 실패할 수 있다.

* shape 포인터의 컨테이너의 소유주는 가리키고 있는 포인터를 delete 하지 않을 수 있다.

이런 점에서, 힙영역에 할당된 객체의 포인터를 반환하는 것은 위험하다.

이때 사용할 수 있는 해결책 중에 한가지는 unique_ptr 를 이용하는 것이다.

case Kind::circle:

// read circle data {Point,int} into p and r

return unique_ptr<Shape>{new Circle{p,r}}; // §5.2.1

// ...

void user()

{

vector<unique_ptr<Shape>> v;

while (cin)

v.push_back(read_shape(cin));

draw_all(v); // call draw() for each element

rotate_all(v,45); //call rotate(45) for each element

} // all Shapes implicitly destroyed

unique_ptr 을 소유하고 있는 객체는 필요하지 않을 때(즉, unique_ptr 의 적용범위가 종료될때) delete 를 호출할 것이다.