[C++ Primer Plus] 16. The string Class and the Standard Template Library

대답해야 할 질문

• smart pointer의 3가지 종류를 말하고 이를 설명하시오.
• shared_ptr에서 발생할 수 있는 circular referencing 상황을 설명하고 해결법을 말하시오.
• iterator의 5가지 종류를 말하고 차이점을 설명하시오.

The string class

• 지엽적인 내용 같아서 생략

Smart Pointer Template Classes

• Smart Pointer(이하 '스마트 포인터')는 포인터에 몇개 기능이 더 있는 클래스 오브젝트다.
• 기본적으로 dynamic memory allocation을 하면 delete를 해야 한다. 빠트리면 leak이 난다. 그러니까 leak을 피하는 방법은 프로그래머가 'delete를 해야지!'하고 기억하는 것이다. 이건 뭐 방법이라고는 할 수 없다.
• 스마트 포인터는 자신가 죽을 때, 자기가 referencing하고 있는 메모리를 해제한다. 즉, delete를 더이상 신경 쓸 필요가 없다.
• 스마트 포인터의 종류로는 auto_ptr(deprecated in C++11), unique_ptr(after C++11), shared_ptr(after C++11)가 있다. (C++11의 weak_ptr은 객체의 생애주기에 영향을 미치지 않으므로 뺐다. 책에서도 설명하지 않는다. 이 포스트에서는 따로 조사해서 설명할 예정)

Using Smart Pointers

• 스마트 포인터를 쓰면 new를 이용해 객체를 생성한 이후 delete 시점 같은 것을 생각할 필요가 없다. 문법은 다음과 같다.

#include <memory>

auto_ptr<double> pd(new double); // pointer-to-double
shared_ptr<string> ps(new string); // pointer-to-string

• 스마트 포인터는 dynamic memory allocation에만 적용된다. 즉, 아래 코드는 금지다.

std::string str = "Hello, world!";
shared_ptr<std::string> sp(&str); // NO!!!

Smart Pointer Considerations

• 스마트 포인터는 왜 3개나 있을까? 왜 auto_ptr은 deprecated 됐을까? 문제는 아래 코드에서부터 시작한다.

auto_ptr<string> ps (new string("Hello, world!"));
auto_ptr<string> vocation;
vocation = ps; // 이 코드로 인해 string 하나를 스마트포인터 2개가 보고 있다.

• 위 코드가 그냥 저대로만 작동하면 string을 두 번 delete하게 되므로 에러가 발생한다. 이를 피하는 방법은 총 3가지다.
  1. assignment operator를 쓰면 deep copy가 되게 한다. 즉, 위 예시에선 string을 복사하게 된다.
  2. ownership(이하 '소유권')의 개념을 도입한다. assignment operator를 쓰면 객체의 소유권이 넘어가게 하는 방식이다. 이러면 이전에 레퍼런싱하던 ps는 더이상 객체를 referencing 하지 못한다. 이게 auto_ptr과 unique_ptr이 쓰는 방식이다. 단, unique_ptr은 여기에 더 많은 제약을 둔다.
  3. 스마트 포인터가 레퍼런싱하는 객체를 보는 스마트포인터가 몇개인지 셀 수 있도록 한다. 레퍼런싱 하는 스마트포인터가 0개가 될 때만 delete를 실행한다. 이 전략이 shared_ptr이 쓰는 방법이다.
• auto_ptr은 두번째 전략을 쓰고 있는데, 문제는 오용될 여지가 크다는 것이다.

#include <memory>
#include <string>
#include <iostream>

int main(void)
{
	std::auto_ptr<std::string> arr[5] = {
		std::auto_ptr<std::string>(new std::string("str1")),
		std::auto_ptr<std::string>(new std::string("str2")),
		std::auto_ptr<std::string>(new std::string("str3")),
		std::auto_ptr<std::string>(new std::string("str4")),
		std::auto_ptr<std::string>(new std::string("str5")),
	};
	for (int i = 0; i < 5; ++i)
		std::cout << *arr[i] << std::endl;
	std::auto_ptr<std::string> catcher(arr[3]); // arr[3]의 ownership이 catcher로 넘어가버렸다.
	for (int i = 0; i < 5; ++i)
		std::cout << *arr[i] << std::endl;

	return 0;
}

• 위 코드는 에러를 발생시킨다. catcher가 arr[3]의 ownership을 훔쳤기 때문이다. 이런 여지가 있으면 프로그래머는 auto_ptr을 쓸 때마다 제대로 된 값을 가리키고 있는지 확인해야 하는 번거로움이 생긴다.

Why unique_ptr Is Better than auto_ptr

• unique_ptr이 어떻게 아래 상황을 피하는지 알아보자.

unique_ptr<string> p3(new string("unique"));
unique_ptr<string> p4;
p4 = p3;

• unique_ptr은 3번째 줄, p4 = p3과 같은 코드를 받아들이지 않는다. 아예 컴파일이 안된다. 그로므로 unique_ptr은 auto_ptr에 비해 안전하다.
• 하지만 = 연산자를 무턱대고 금지시키면 문제가 발생할 수 있다. 아래와 같이 unique_ptr 자체를 리턴해야 하는 상황이다.

unique_ptr<string> demo(const char * s)
{
	unique_ptr<string> temp(new string(s));
    return temp;
}

int main()
{
	unique_ptr<string> ps = demo("Hello, world!"); // 이 상황은 되면 좋겠다.
}

• demo는 unique_ptr을 복사해서 반환할 것이다. 컴파일러는 demo의 반환값으로 temporary object인 unique_ptr을 반환한다. 어차피 임시 객체이니까 ps의 ownership에 문제가 생기지 않는다. 그래서 unique_ptr은 위 코드를 인정한다. 이런 유연성 또한 unique_ptr이 auto_ptr에 비해 월등한 이유다.
• 또한 move semantics를 사용해서 unique_ptr의 ownership을 옮길 수 있다.

Selecting a Smart Pointer

• 만약 한 오브젝트를 가리키는 여러 포인터가 필요하면 shared_ptr을 쓰고 그게 아니라면 unique_ptr을 쓰면 된다.

weak_ptr (자체 추가)

• weak_ptr은 C++11에 추가된 포인터로 shared_ptr의 circular reference 문제를 해결하기 위해 등장했다. 해당 문제는 다음과 같은 상황에서 발생한다. (아래 코드는 링크를 참조했다.)

#include <memory>
#include <string>
#include <iostream>
#include <vector>

class Party;
typedef std::shared_ptr<Party> PartyPtr;
class User;
typedef std::shared_ptr<User> UserPtr;

class Party
{
public:
	void AddUser(UserPtr);
	std::vector<UserPtr> users;
};

class User
{
public:
	User(PartyPtr, std::string);
	PartyPtr partyPtr;
	std::string name;
};

int main(void)
{
	PartyPtr partyPtr(new Party);
	for (int i=0; i<5; ++i)
	{
		UserPtr up(new User(partyPtr, "user"));
		partyPtr->AddUser(up);
	}

	for (int i=0; i<5; ++i)
	{
		std::cout << partyPtr->users[i]->name << std::endl;
	}

	// 여기서 party 객체가 사라지길 기대하지만 그러지 못한다.
	// 각 user 객체가 party에 대한 shared_ptr을 가지고 있기 때문이다.
	// party가 살아있기 때문에 user 객체들도 메모리를 떠돈다.
	partyPtr.reset();

	return 0;
}

void Party::AddUser(UserPtr up)
{
	users.push_back(up);
}

User::User(PartyPtr _pp, std::string _name)
{
	this->partyPtr = _pp;
	this->name = _name;
}

• 그룹 객체 - 소속 객체가 서로 포인터를 가지고 있는 것은 흔한 상황이다. 하지만 서로 shared_ptr을 가지고 있으면 메모리가 해제되지 못하고 쌓이는 상황이 발생한다. 이 문제를 해결해주는 것이 weak_ptr이다.
• weak_ptr은 shared_ptr을 통해서만 태어날 수 있다.

shared_ptr<string> sp(new string("Hello, shared!");
weak_ptr<string> wp = sp; // sp의 strong reference count가 아니라 weak reference count를 올린다.

• weak_ptr은 shared_ptr의 객체 생명 주기에 영향을 주는 strong reference는 안 올리고 weak reference만 올린다.

The Standard Template Library

• STL은 template을 활용한 cointainer, iterator, function objects, algorithm을 제공한다.
• STL은 OOP의 예시가 아니라 Generic Programming의 예시다.

Generic Programming

• OOP가 프로그래밍에서 데이터를 강조한다면 Generic Programming은 알고리즘을 강조한다. 이러한 측면은 iterator를 보면 이해할 수 있다.
• double array에서 특정 값을 찾아서 그 주소를 리턴해주는 함수를 만든다고 생각해보자. 코드는 아래와 같을 것이다.

double* find_arr(double* arr, int n, const double& val)
{
	for (int i=0; i<n; ++i)
    {
    	if (arr[i] == val)
        	return &arr[i];
    }
    return 0;
}

• 이번엔 array가 아니라 list에서 find 함수를 만든다고 생각해보자. list는 node라는 오브젝트들이 연결된 형태라고 가정한다. 그럼 코드는 아래와 같을 것이다.

Node* find_list(Node* head, const double& val)
{
	Node* start;
    for (start=head; start!=0; start++)
    {
    	if (*start == val)
        	return start;
    }
    return 0;
}

• 두 함수는 실제 코드는 일부분 다르지만 결국 이루고자 하는 목표나 방식은 거의 비슷하다. 결국은 처음부터 끝까지 순회하면서 같은 값이면 리턴하는 방식이다. 그렇다면 하나의 함수로 해결할 순 없을까?
• 이를 해결하기 위해 순회를 위한 클래스인 iterator를 만든다고 가정해보자. iterator는 다음 특징을 가져야 한다.
  • dereference를 통해 값에 접근할 수 있어야 한다. 예를 들어, *p를 통해 iterator가 가리키는 값이 무엇인지 알 수 있어야 한다.
  • iterator를 다른 iterator에 할당할 수 있어야 한다. 즉, p = q가 작동해야 한다.
  • iterator가 서로 같은지 검증할 수 있어야 한다. 즉, p == q와 p != q가 작동해야 한다.
  • iterator를 움직여서 container를 순회할 수 있어야 한다. p++ 또는 ++p를 통해 iterator가 다음 값을 가리키도록 할 수 있어야 한다.
• 위와 같은 iterator를 만들 수만 있다면 find_arr과 find_list는 아래 형태로 합칠 수 있다!

iterator find(iterator start, iterator end, const double & val)
{
	for (; start!=end; start++)
    {
    	if (*start == val)
        	return start;
    }
    return end;
}

• iterator는 위 조건만 맞춰진다면 pointer가 될 수도 있고 어떠한 오브젝트가 될 수도 있다.

Kinds of Iterators

• 각 알고리즘은 필요한 iterator의 조건이 다르다. 예를 들어, find 알고리즘의 iterator는 데이터를 읽는 기능은 필요하지만 쓰는 기능은 필요가 없다.
• STL은 이렇게 다른 iterator 조건을 다섯개로 나누어 제시하고 있다. 그들에게 필요한 조건을 표로 만들면 다음과 같다.

Iterator Capability	Input	Output	Forward	Bidirectional	Random Access
++i i++	O	O	O	O	O
Fixed and repeatable order	X	X	O	O	O
--i i--	X	X	X	O	O
i[n]	X	X	X	X	O
i + n	X	X	X	X	O
i - n	X	X	X	X	O
i += n	X	X	X	X	O
i -= n	X	X	X	X	O

Concepts, Refinements, and Models

• STL의 일부 기능인 iterator 같은 것들은 코드로 나타낼 수 없다. iterator의 기능 같은 것들은 type이 아니라 requirements에 가깝다. STL 알고리즘은 iterator가 요구사항을 만족할 때 제대로 작동한다. 이러한 요구사항을 concept라고 부른다.
• Concept는 상속의 개념이 있지만 코드로 이게 나타나지는 않는다. 그래서 Concept의 상속을 refinement라고 말한다. 예를 들어, Forward Iterator Concept는 OutputIterator와 InputIterator의 refinement다.
• 그리고 이러한 Concept를 실제 코드로 나타낸 것을 model이라고 한다.

Kinds of Containers

• STL은 container concept와 container type을 전부 가지고 있다. container concept는 sequence container나 assotiative container와 같은 카테고리에 해당한다.

Container Concepts

• container는 같은 종류의 오브젝트를 저장하는 오브젝트를 의미한다.
• container가 저장하는 오브젝트는 컨테이너에게 소유권이 있다. 즉, 컨테이너가 소멸할 때, 저장된 오브젝트들도 함께 소멸한다.
• 컨테이너에 아무 자료형이나 저장할 순 없다. copy constructorable과 assignable의 두 특성을 모두 가진 타입만이 컨테이너에 저장될 수 있다.
• basic container는 데이터가 저장되는 순서 등을 보장하지 않는다. 하지만 sequence container나 assotiative container와 같은 refinements는 이를 보장한다.

Sequences

• sequence containter엔 deque, forward_list, list, queue, priority_queue, stack, vector가 포함된다.
• sequence container는 각 원소들이 엄격한 순서대로 나열되어 있어야 한다. 즉, 메모리 상에서 순서가 맞춰져있어야 한다.

Associative Containers

• value를 key와 함께 저장한다.
• Associative Container의 장점은 Sequence Container에 비해 검색이 빠르다는 점이다. 대신 원하는 인덱스로 이동하는 속도가 느리다.

Function Objects (a.k.a. Functors)

• 많은 STL 알고리즘들이 function objects(=functor)를 쓴다.
• functor는 () 연산자를 사용해서 마치 함수처럼 사용할 수 있는 오브젝트다.

class Linear
{
private:
	double slope;
    double y0;
public:
	Linear(double sl_ = 1, double y_ = 0)
    	: slope(sl_), y0(y_) {}
    double operator() (double x) { return y0 + slope * x; }
};

Functor Concepts

• STL에서 Functor는 3가지 정도로 나뉜다.
  • generator: 매개변수 없이 호출할 수 있는 functor
  • unary function: 매개변수 하나로 호출하는 functor
  • binary function: 매개변수 두개로 호출하는 functor

References

• http://egloos.zum.com/sweeper/v/3059940

[TR1] weak_ptr

• C++ Primer Plus 6th, Chapter 16