STL 여섯 가지 주요 컴포넌트 - 컨테이너 - 시퀀스 컨테이너

 

 

 

STL에는 여섯 가지 주요 컴포넌트가 있다.

 

컨테이너, 제네릭 알고리즘, 반복자, 함수 객체, 어댑터, 할당기가 포함되어 있다.

 

STL에는 두 가지 종류의 컨테이너가 있는데,

하나는 시퀀스 컨테이너이고, 다른 하나는 정렬 연관 컨테이너이다.

 

시퀀스 컨테이너는 타입이 동일한 객체들을 선형으로 구성한 컬렉션이다.

STL의 시퀀스 컨테이너에는 다음 세 가지 종류가 있다.

 

vector<T> : 가변 길이 시퀀스를 임의 접근할 수 있으며,

시퀀스 맨 끝에서 수행되는 삽입과 삭제는 아모타이즈드 상수 시간에 수행이 가능하다.

(여기서 임의 접근이 가능하다는 것은

시퀀스의 i번째 원소를 접근하는데 걸리는 시간이 상수 시간이라는 것을 의미한다.

이는 다시 말해, i값에 상관없이 소요 시간은 항상 일정하다는 뜻이다.)

 

deque<T> : 이것 도한 가변 길이 시퀀스를 임의 접근할 수 있으며,

시퀀스 맨 앞과 끝에서 수행되는 삽입과 삭제는 모두 아모타이즈드 상수 시간에 수행이 가능하다.

O(1) 된다는 의미

 

list<T> : 가변 길이 시퀀스에 대해서 선형 시간 접근만이 가능하며

(즉, 소요 시간은 O(N). 여기서 N은 시퀀스의 현재 길이).

삽입과 삭제는 시퀀스 내에서라면 어디서든지 상수 시간 내에 수행이 가능하다.

 

각각의 시퀀스 컨테이너 타입에 관해 상세히 설명하기에 앞서,

우선 한 가지 명심해야 할 것이 있다.

그것은 우리가 일반적으로 사용하는 C++ 배열 타입에 해당하는 T a[N]도

시퀀스 컨테이너와 동일하게 취급할 수 있다는 점이다.

이는 STL제네릭 알고리즘이 배열에 대해서도

여타 다른 시퀀스 타입의 경우와 동일하게 동작할 수 있도록 설계되었기 때문이다.

그리고 또 하나,

라이브러리에서 제공하는 타입 중에 문자들의 시퀀스를 표현하는

string 타입도 STL 알고리즘과 함께 사용이 가능하며,

reverse 제네릭 알고리즘은 시퀀스의 순서를 거꾸로 뒤집을 때 사용하는데,

string 객체와 배열에서도 잘 동작한다.

 

제네릭 reverse 알고리즘을 벡터&리스트와도 함께 사용해보기

 

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <cassert>
#include <algorithm>

using namespace std;

template <typename Container>
Container make(const char s[])
{
	return Container(&s[0], &s[strlen(s)]);
}

int main()
{
	// string
	cout << "Using reverse algorithm with a string" << endl;
	string string1 = "mark twain";
	reverse(string1.begin(), string1.end());
	assert(string1 == "niawt kram");
	cout << " --- OK." << endl;

	// char
	cout << "Using reverse algorithm with an array" << endl;
	char array1[] = "mark twain";
	int N1 = strlen(array1);
	reverse(&array1[0], &array1[N1]);
	assert(string(array1) == "niawt kram");
	cout << "--- Ok." << endl;
	
	// vector
	cout << "Using reverse algorithm with a vector" << endl;
	vector<char> vector1 = make<vector<char>>("make twain");
	reverse(vector1.begin(), vector1.end());
	assert(vector1 == make<vector<char>>("niawt kram"));
	cout << "--- Ok." << endl;

	// list
	cout << "Demonstrating generic reverse algorithm on a list" << endl;
	list<char> list1 = make<list<char>>("niawt kram");
	cout << "--- Ok." << endl;


	return 0;
}

 

reverse 함수 호출에서 인자로 사용된

string1.begin()과 string.end()는 string 클래스에 정의되어 있는

멤버 함수는 begin과 end를 호출한다.

이 멤버 함수들은 포인터와 유사한 객체은 반복자를 리턴하는데,

begin 멤버 함수는 string1의 맨 처음을 가리키는 반복자를 리턴하며,

end 멤버 함수는 string1의 맨 끝을 가리키는 반복자를 리턴한다.

 

reverse 함수는 이 두 개의 반복자로 지정된 구간(range)에

속하는 문자들을 문자열 내부에서(in-place) 역순으로 뒤집는다.

 

 

 

 

 

 

++ Plus ++

아모타이즈드 상수 시간이 뭔데?

 

아모타이즈드 시간 복잡도

어떤 경우에는 알고리즘의 컴퓨팅 시간을 가장 현실적으로 규명해낼 수 있는 것이

최악 소요시간도 아니고, 평균 소요 시간도 아닌 아모타이즈드 시간(amortized time)인 경우가 있다.

이 개념은 부채 상환(amortization)이라고 하는

제조업계의 회계 방식과 유사한 것으로,

부채 상환에서는 일괄(one-time)

비용(설계 비용을 예로 들 수 있다)이 생산된 부품의 수로 나눠져서 각각의 유닛에 할당된다.

일련의 연산을 수행할 때 소요시간이 큰 폭으로 변화하고,

N개 연산을 수행하는데 걸리는

총 소요 시간이 최악 소요 시간의 N배보다 더 나은 바운드를 가지는 경우에는

아모타이즈드 시간을 이용하여

컨테이너 상의 연산이 소비한 시간을 설명하는 것이 아주 유용하다.

예를 들어,

STL 벡터의 맨 뒤에 원소를 삽입하는데 필요한

최악 소요 시간은 컨테이너의 사이즈를 N이라고 했을 때 O(N)이 된다.

삽입 연산에 필요한 메모리 공간이 없는 경우에는 새로 메모리 공간을 할당하고,

그 다음에 원소들을 새로 할당된 메모리 공간으로 모두 옮겨야 하기 때문이다.

그러나 길이 N의 벡터는 확장될 필요가 있을 때마다 2N의 메모리 공간을 할당하여,

이후 N-1번의 삽입 동안에는 재할당과 복사가 발생하지 않게 된다.

결과적으로,

이후에 발생할 N-1번의 삽입은 개별적으로는 상수시간(constant time)에 수행되므로,

N개의 삽입 연산에 걸리는 총 시간은 O(N)이며,

N개의 연산의 평균을 계산하면 삽입 연산의 소요 시간은 O(1) 시간이 되는 것이다.

 

따라서, 삽입 연산의 아모타이즈드 시간은 상수 즉,

삽입 연산의 소요 시간이 "아모타이즈드 상수(amortized constant)이다."라고 말 할 수 있는 것이다.

++++