Chapter 4 - 1. Containers and Algorithms, Libraries

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) 는 공백을 그냥 넘어가지 않는다. ( 입력한다 ) 



Chapter 3 - 1. Abstraction Mechanisms, Classes

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 를 호출할 것이다.



Chapter 2 - 2. The Basics, Error Handling

2.4.3 Error Handling ~ 2.5 postscript

- 본 문은 노트 정리 차원에서 기술한 내용입니다.


에러 핸들링을 위한 편의 시설 - 시스템 그 자체. 빌트인 타입과 if 문 등의 statement 만이 아닌 어플리케이션에 적합한 타입 ( string / map .. ) 이용하고 알고리즘들을 이용할수있다. 이런 고수준 구조가 존재 할 수록 버그를 만들 여지가 줄고 에러를 더 잡기 쉬움.

가장 중요한 것은 추상화.


2.4.3.1 Exceptions

vector 구현자에게 있어 out of range 에러를 사용자에게 알려주고 싶다.

예를 들면 다음과 같이 연산자 오버로딩을 통해 에러를 던질 수 있다.


double& Vector::operator[](int i)

{

if (i<0 || size()<=i) throw out_of_rang e{"Vector::operator[]"};

return elem[i];

}


throw 는 out-of-range 타입의 예외를 연산자 호출부로 전달한다.

그러기 위해 콜스택 풀기가 필요. 


try - 블럭으로 예외가 발생할 것 같은 곳에 두고 catch 로 발생한 예외를 잡아낸다.

이 메커니즘은 에러 핸들링을 간단/시스템적으로/가독성있게 만들어준다.



2.4.3.2 Invariants

vector 의 멤버가 어떤 타당한 값을 가지고 있지 않으면 아무 의미도없다. 주석을 통해 elem 은 double 형의 sz 개의 배열을 가지고 있어야 하지만 이를 강제하는 것은 없다. 이렇게 어떤 클래스가 유효함을 보장하기 위해 사실이어야 하는 진술이 class invariant 라고 불림.

생성자를 통해 초기화 되어 소멸자가 호출되기 전까지 지켜져야함


invariant 보장을 위해 다음과 같이 정의 

Vector::Vector(int s)

{

if (s<0) throw length_error{};

elem = new double[s];

sz = s;

}

standard-library 의 length-error 사용.

보통 에러를 '핸들링' 한다는 것은 최소한의 로컬 클린업과 rethrowing exception 을 의미.


클래스의 invariant , 함수의 preconditions 는 비슷하다. 

invariant 는

- 우리가 뭘 원하는지 이해하는데 도움을 준다

- 특정한 것에 초점을 맞추게 한다. ( 디버깅 / 테스트 후에 우리 코드를 올바르게 만들 수 있는 더 많은 기회)


2.4.3.3  static assertions

컴파일 타임 체크. - 다라서 constexpr 로 표현되는 predicate 여야한다.

static_assert(<predicate>, <message>);