* 원문 링크 : ![[http]](/wiki/imgs/http.png)
http://www.sgi.com/tech/stl/stl_introduction.html
http://www.sgi.com/tech/stl/stl_introduction.html
- iterator를 "반복자"라고 하니깐 저도 헛갈리네용. 그냥 영어단어 그대로 적을 랍니다. T_Ta
1 개요 #
STL(Standard Template Library)은 container 클래스들, algorithm, iterator들을 담고 있는 C++ 라이브러리이다; 컴퓨터 과학분야에서 많이 사용되는 기본적인 알고리즘과 데이타 구조들을 제공한다. STL은 일반화된(generic) 라이브러리이며 이것은 STL의 구성요소들이 엄청나게 인자화되어있다는 것을 의미한다 - STL의 거의 모든 구성요소가 템플릿으로 구성되어있다. STL을 사용하기전에 C++에서 템플릿이 어떻게 동작하는지 이해할 필요가 있다.
2 Container와 algorithm #
수많은 클래스 라이브러리와 마찬가지로, STL도 container 클래스들을 포함하고 있다 : 이런 종류의 클래스들은 특정한 다른 객체들을 담아 두기 위한 목적으로 사용된다. STL은 다음과 같은 클래스들을 포함하고 있다.
- vector
- list
- deque
- set
- multiset
- map
- multimap
- hash_set
- hash_multiset
- hash_map
- hash_multimap
vector<int> v(3); // Declare a vector of 3 elements. v[0] = 7; v[1] = v[0] + 3; v[2] = v[0] + v[1]; // v[0] == 7, v[1] == 10, v[2] == 17
STL은 또한 container내에 저장될 데이타를 관리하는 거대한 알고리즘들의 모음집이다. vector의 요소들의 순서를 역으로 바꿀려면 다음의 예처럼 reverse 알고리즘을 사용하면 된다.
reverse(v.begin(), v.end()); // v[0] == 17, v[1] == 10, v[2] == 7
reverse를 호출하는 데 있어 주의하여야 하는 중요한 2가지 요소들이 있다. 첫째로는, 이것은 전역 함수이지 맴버함수가 아니다. 둘째, 하나가 아닌 두개의 인자를 가진다 : 이것은 container내부의 요소들의 범위를 지정할 수 있다는 의미가 된다. 위의 예제에서는 container v의 전체에 걸쳐서 작업이 수행되는 경우이다.
이런 사실에 대한 이유는 하나이다 : reverse외의 다른 algorithm들도 마찬가지이지만, 이들은 STL container 클래스들에 범용으로 적용이 가능하다. 이것은 reverse가 vector의 요소뿐만아니라 list에 대한 요소에서도 동작한다는 것을 의미한다. (심지어 C 배열에도 동작한다. 다음 예제는 적법한 문법이다.)
double A[6] = { 1.2, 1.3, 1.4, 1.5, 1.6, 1.7 };
reverse(A, A + 6);
for (int i = 0; i < 6; ++i)
cout << "A[" << i << "] = " << A[i];
이 예제에서는 vector를 역순으로 바꾸는 예제와 같이 범위를 지정하였다 - reverse의 첫번째 인자는 범위의 시작을 가리키는 포인터이고 두번째 인자는 범위의 끝은 나타내는 요소의 바로 다음번째를 가리킨다.
이 범위는 [A, A + 6)으로 표현할 수 있다. 범위를 표현하는 데 있어 비대칭적으로 지정하는 것을 명심하자. 첫째 인자는 포함되지만, 두번째 인자는 포함되지 않는 범위의 마지막인자의 다음 인자를 지정한다.
3 Iterator #
C 배열을 reverse하는 예제에서는 reverse함수의 인자는 확실하게 double* 타입의 포인터였다. vector나 list를 reverse하는 경우라면 reverse함수의 인자는 무엇일까? 게다가, reverse 함수에 선언되어있는 인자들은 어떤 것들이 될 수 있으며, v.begin()와 v.end()가 반환하는 값은 실제로 무엇인가? 답은 일반화된 포인터인 iterator이다.
포인터 그 자체도 iterator가 될 수 있으며, 이것이 reverse함수의 인자가 C 배열변수를 지정하는 것이 가능했던 이유다. 간단히 말하면, vector는 내장된 타입인 iterator와 const_iterator들을 정의한다. 위의 예에서는, v.begin()와 v.end()가 반환하는 타입은 vector<int>::iterator이다.
container들과 전혀 연관되어 있지 않은 istream_iterator와 ostream_iterator와 같은 iterator도 존재한다. iterator들은 container로부터 algorithm을 흡수토록 만들어주는 체계이다.(?): algorithm은 템플릿으로 되어있고, iterator의 타입에 의해 인자화되어있으므로, container의 단일한 타입에 제한되지 않는다.
예를 들어, 어떤 범위상에서 선형 검색을 수행하는 방법을 고려해보자. 이것은 STL의 find algorithm 이다.
template <class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T& value) {
while (first != last && *first != value) ++first;
return first;
}
find 함수는 3개의 인자를 가진다 : 범위를 지정하기 위한 2개의 iterator와 범위내에서 검색할 값이 그것이다. [first, last)범위내에서 각 iterator는 처음부터 끝까지 진행하게 되며, iterator가 찾고자 하는 값에 위치하거나 범위의 끝에 다다르면 멈춘다.
first와 last는 Input Iterator타입으로 선언되었으며, 이것은 템플릿의 인자로써 지정되어 있다. 다시말하면, Input Iterator라고 불리는 어떤 타입도 실제로는 존재하지 않는다 : 만일 find 알고리즘을 호출하면, 컴파일러는 형식적인 인자 Input Iterator와 T를 실제 타입으로 대체한다. 만약 검색하려는 처음 두개의 인자들이 int *이고 세번째 인자가 int타입이라면 이것은 다음과 같은 함수를 호출한 것과 같은 의미가 된다.
int* find(int* first, int* last, const int& value) {
while (first != last && *first != value) ++first;
return first;
}
4 개념(concept)과 모델링 #
STL algorithm 뿐만 아니라 다른 어떤 탬플릿 함수에 대해서 물어볼 수 있는 가장 중요한 질문중 하나는 전형적인 템플릿 인자들과 정확하게 대체될 타입들이 무엇들인가이다. 확실하게 예를 들자면, int* 또는 double*은 find함수의 탬플릿 인자인 Input Iterator와 대체될 수 있다. 하지만, int 또는 double은 대체될 수 없다 : find는 (내부적으로) *first라는 표현을 사용하며 int나 double 타입에 역참조 연산자(*를 뜻함)를 적용하는 것은 무의미하기 때문이다. 그러므로 여기에서 알 수 있는 점은 find는 타입에 대한 요구사항들을 내부적으로 가지고 있다는 것이고, 어떤 타입도 이 요청사항을 만족시켜야한다는 것이다.
어쨌거나 Input Iterator와 대체될 타입은 반드시 특정한 동작(operation)을 제공해야만 한다 : 지정한 타입에 대한 두 객체가 동일한지 비교할 수 있어야 하고, 객체를 가리키고 있는 주소를 얻기위해 지정한 타입에 대한 객체를 역참조하는 것이 가능해야 하며, 그외 기타등등이 있을 수 있다.
find만이 위와같은 요구사항을 가지고 있는 것은 아니다 : for_each나 count, 그외 다른 알고리즘들도 위와 같은 요구사항을 만족시켜야만 한다.
이 요구사항들은 어떤 용어를 지정할만큼 충분히 중요하다 : 우리는 이런 형태의 요청사항들을 concept이라고 부르며, 이런 형태의 특별한 concept을 Input Iterator라고 칭한다. 만약 어떤 특정 타입이 이같은 모든 요구조건을 만족하면, 이 타입은 이 concept을 따른다라고 하거나 이 concept의 모델이다라고 얘기한다. int*는 Input Iterator의 모든 요구조건을 만족하는 모든 Operation을 제공하므로, 이 타입은 Input Iterator의 한 모델이라고 말할 수 있다. concept은 C++ 언어의 부분은 아니다 : 프로그램내에서 concept을 정의하거나 특정한 타입을 concept의 모델로써 정의하는 방법은 없다. 그럼에도 불구하고, concept은 STL에서 아주 중요한 부분이다.
concept을 사용하는 것은 구현(implementation)으로부터 interface를 확실하게 분리하는 프로그램을 작성하는 것을 가능하게 만들어준다 : find 알고리즘을 작성한 저자는 (그 concept을 만족하는 모든 가능한 타입을 구현하는 것보다) Input Iterator concept에 의해 정의된 interface만을 고려했을 것이다. 비슷한 얘기로, 만약 find를 사용하기를 원한다면 find에 넘겨줄 인자들이 Input Iterator 모델이라는 것을 확인하는 것이 필요하다. 이것은 왜 find와 reverse가 list, vector, C 배열외의 많은 다른 타입들과 사용이 가능한지에 대한 이유라고 할 수 있다 : 특정한 타입만을 고려한 것이 아닌 concept을 고려한 프로그래밍은 소프트웨어 컴퍼넌트들을 재사용할 수 있도록 해주며, 서로서로 각 컴퍼넌트들이 연결될 수 있도록 해준다.
5 Refinement #
사실, Input Iterator는 다소 약한 concept이다 : 이것은 사용하는데 있어서 거의 요구사항이 없다. (that is, it imposes very few requirements.) Input Iterator는 포인터의 산술연산의 연산자들을 반드시 지원해야한다. (이것은 Input Iterator가 ++연산자를 앞이나 뒤에 붙여서 포인터를 증가시키는 것이 가능하다는 것을 의미한다) 그러나, 모든 포인터 산술연산을 지원할 필요는 없다. 이것은 find 알고리즘을 위해서는 충분하지만, 몇가지 다른 알고리즘들은 그들의 인자들이 추가적인 요구사항을 지켜주는 것을 원한다. 예를 들면, reverse 알고리즘은 그 인자들이 증가될수 있는 것 만큼이나 감소 연산도 실행할 수 있어야만 한다. it uses the expression --last. In terms of concepts, we say that reverse's arguments must be models of Bidirectional Iterator rather than Input Iterator.
The Bidirectional Iterator concept is very similar to the Input Iterator concept: it simply imposes some additional requirements. The types that are models of Bidirectional Iterator are a subset of the types that are models of Input Iterator: every type that is a model of Bidirectional Iterator is also a model of Input Iterator. Int*, for example, is both a model of Bidirectional Iterator and a model of Input Iterator, but istream_iterator, is only a model of Input Iterator: it does not conform to the more stringent Bidirectional Iterator requirements.
We describe the relationship between Input Iterator and Bidirectional Iterator by saying that Bidirectional Iterator is a refinement of Input Iterator. Refinement of concepts is very much like inheritance of C++ classes; the main reason we use a different word, instead of just calling it "inheritance", is to emphasize that refinement applies to concepts rather than to actual types.
There are actually three more iterator concepts in addition to the two that we have already discussed: the five iterator concepts are Output Iterator, Input Iterator, Forward Iterator, Bidirectional Iterator, and Random Access Iterator; Forward Iterator is a refinement of Input Iterator, Bidirectional Iterator is a refinement of Forward Iterator, and Random Access Iterator is a refinement of Bidirectional Iterator. (Output Iterator is related to the other four concepts, but it is not part of the hierarchy of refinement: it is not a refinement of any of the other iterator concepts, and none of the other iterator concepts are refinements of it.) The Iterator Overview has more information about iterators in general.
Container classes, like iterators, are organized into a hierarchy of concepts. All containers are models of the concept Container; more refined concepts, such as Sequence and Associative Container, describe specific types of containers.
6 Other parts of the STL #
If you understand algorithms, iterators, and containers, then you understand almost everything there is to know about the STL. The STL does, however, include several other types of components.
First, the STL includes several utilities: very basic concepts and functions that are used in many different parts of the library. The concept Assignable, for example, describes types that have assignment operators and copy constructors; almost all STL classes are models of Assignable, and almost all STL algorithms require their arguments to be models of Assignable.
Second, the STL includes some low-level mechanisms for allocating and deallocating memory. Allocators are very specialized, and you can safely ignore them for almost all purposes.
Finally, the STL includes a large collection of function objects, also known as functors. Just as iterators are a generalization of pointers, function objects are a generalization of functions: a function object is anything that you can call using the ordinary function call syntax. There are several different concepts relating to function objects, including Unary Function (a function object that takes a single argument, i.e. one that is called as f(x)) and Binary Function (a function object that takes two arguments, i.e. one that is called as f(x, y)). Function objects are an important part of generic programming because they allow abstraction not only over the types of objects, but also over the operations that are being performed.
