[C/C++] 표준 템플릿 라이브러리(STL) - (1)

C++ STL

-  일반적으로 C++ STL은 다음과 같은 세 개의 라이브러리들을 의미한다.

1.  임의 타입의 객체를 보관할 수 있는 컨테이너(container)
2.  컨테이너에 보관된 원소에 접근할 수 있는 반복자(iterator)
3.  반복자들을 가지고 일련의 작업을 수행하는 알고리즘(algorithm)

 

• 벡터(std::vector)

-  C++ STL에서 컨테이너는 크게 두 가지 종류가 있다.
1.  배열처럼 객체들을 순차적으로 보관하는 시퀀스 컨테이너(sequence container)

=>  vector, list, deque 이렇게 3개 정의되어 있음.

2.  키를 바탕으로 대응되는 값을 찾아주는 연관 컨테이너(associative container)

-  vector의 경우, 임의의 위치에 있는 원소에 접근을 O(1) 로 수행가능

-  맨 뒤에 새로운 원소 추가 및 삭제도 O(1) 에 수행 가능

=>  맨 뒤에 원소를 추가하는 작업은 엄밀히 말하자면 amortized O(1) 이라고 한다.(amortized : 분할상환)
==>  할당된 공간을 다 채웠을 때는 새로운 큰 공간을 다시 할당해야 하며 이 때, 기존의 원소들을 복사하는 과정이 발생해서 O(n)으로 수행된다.
==>  O(n)으로 수행되는 경우가 매우 드물기 때문에 전체적으로 평균을 냈을 때는 O(1)으로 수행이 되기 때문에 amortized O(1) 이라고 부른다.

-  임의의 위치에 원소를 추가하거나 제거하는 것은 O(n)으로 느리다.

=>  임의의 위치에 추가 또는 삭제시 그 뒤의 원소들을 한 칸 씩 이동시켜 주어야 하기 때문

-  vector 요약

=>  임의의 위치 원소 접근([], at) : O(1)
=>  맨 뒤 원소 추가 및 제거(push_back / pop_back) amortized O(1), (평균적으로 O(1) 이지만 최악의 경우 O(n))
=>  임의의 위치 원소 추가 및 제거(insert / erase) : O(n)

 

• 반복자(iterator)

-  컨테이너의 원소에 접근할 수 있는 포인터와 같은 객체

-  반복자는 컨테이너에 iterator 멤버 타입으로 정의되어 있다.

=>  vector의 경우 반복자를 얻기 위해서는 begin() 함수와 end() 함수를 사용할 수 있다.
==>  begin() : vector의 첫번째 원소를 가리키는 반복자를 리턴
==>  end() : vector 마지막 원소의 한 칸 뒤를 가리키는 반복자를 리턴
==>  end()가 마지막 원소의 한 칸 뒤를 리턴함으로써 빈 벡터를 표현하기가 쉽다.
ex)  begin() == end() 라면 원소가 없는 벡터를 의미하는 것이다.

-  vector의 반복자 타입은 std::vector<>::iterator 멤버 타입으로 정의됨.

=>  vector.begin() 이나 vector.end() 함수가 이를 리턴함.
=>  반복자가 가리키는 원소의 값을 보고싶다면 'cout << *itr << endl' 로 가능.
==>  * 연산자를 사용하긴 하지만 itr은 실제 포인터가 아니고 * 연산자를 오버로딩해서 포인터처럼 동작하게 만든 것.
==>  * 연산자는 itr이 가리키는 원소의 레퍼런스를 리턴한다.
=>  반복자는 그냥 배열을 가리키는 포인터와 정확히 똑같이 동작한다고 생각하면 된다.

-  vector 컨테이너에 원소를 추가하거나 제거하게 되면 기존에 사용하였던 모든 반복자들은 사용할 수 없게된다.

-  vector에서 지원하는 반복자로 const_iterator가 있다.

=>  const 포인터를 생각하면 된다.
==>  const_iterator 의 경우 가리키고 있는 원소의 값을 바꿀 수 없다.
=>  const 반복자의 경우 cbegin(), cend() 함수를 이용하여 얻을 수 있다.
=>  반복자의 값을 바꾸지 않고 참조만 하는 경우가 많으므로 const iterator를 적절히 이용하는 것이 좋다.

-  vector에서 지원하는 반복자 중 마지막 종류로 역반복자(reverse iterator)가 있다.

=>  벡터 뒤에서부터 앞으로 거꾸로 간다.
==>  rbegin(), rend() 함수를 이용해 얻을 수 있다.
==>  rbegin() : vector의 마지막 원소를 가리키는 반복자를 리턴
==>  rend() : vector 첫번째 원소의 한 칸 앞을 가리키는 반복자를 리턴
=>  역반복자의 경우 값이 증가하면 앞쪽 원소로 가게 된다.

-  역반복자도 상수 역반복자가 있다. const_reverse_iterator

=>  crbegin(), crend()로 얻을 수 있다.

-  vector의 index를 담당하는 타입은 부호 없는 정수이다.

=>  vector의 index를 담당하는 타입으로 i를 선언 및 정의해서 vector를 역으로 출력하면 i 값이 0일 때, i-- 를 하면 -1이 되는 것이 아니라, 해당 타입에서 가장 큰 정수가 되어버린다.
==>  해결하기 위해서는 부호 있는 정수로 선언해야 하는데 vector의 index 타입과 일치하지 않아서 타입 캐스팅을 해야 한다는 문제가 발생한다. 
==>  가장 현명한 선택은 역으로 원소를 참조하고 싶다면, 역반복자를 사용하는 것이다.

 

• 범위 기반 for문(range based for loop)

-  컨테이너의 원소를 for문으로 접근하는 패턴을 매우 간단하게 나타내는 방식을 C++ 11부터 제공한다. 이를 범위 기반(range-based) for문 이라고 부른다.

 

• 리스트

-  양방향 연결 구조를 가진 자료형

-  vector와 달리 임의의 위치에 있는 원소에 바로 접근할 수 없다.

=>  list 컨테이너 자체에서는 시작 원소와 마지막 원소의 위치만을 기억하기 때문

-  list의 경우 임의의 위치에 원소를 추가 및 제거하는 작업을 O(1) 으로 매우 빠르게 수행할 수 있음

=>  vector는 O(n) 소요

-  list의 반복자는 ++, -- 연산밖에 수행할 수 없다.

=>  itr + 5 와 같이 임의의 위치에 있는 원소를 가리킬 수 없다.

-  list는 메모리 상에서 원소들이 연속적으로 존재하지 않을 수 있다.

=>  vector의 경우 메모리 상에서 연속적으로 존재하기 때문에 쉽게 임의의 위치에 있는 원소를 참조할 수 있다.
※  list에서 정의되는 반복자의 타입은 BidirectionalIterator 이다. 양방향으로 이동할 수 있되, 한 칸 씩 밖에 이동할 수 없다.
※  vector에서 정의되는 반복자 타입은 RandomAccessIterator 이다. 임의의 위치에 접근할 수 있는 반복자이다. (RandomAccessIterator은 BidirectionalIterator를 상속받는다.)

-  list의 경우 vector와 달리 원소를 지우거나 추가해도 반복자가 무효화 되지 않는다.

=>  각 원소들의 주소값들은 바뀌지 않기 때문

 

• 덱(deque - double ended queue)

-  vector와 비슷하게 O(1)로 임의의 위치의 원소에 접근이 가능하며 맨 뒤에 있는 원소를 추가/제거 하는 작업도 O(1)로 수행 가능하다.

-  또한 vector와 달리 맨 앞에 원소를 추가/제거 하는 작업 까지도 O(1)로 수행 가능하다.

-  임의의 위치에 원소를 추가/제거 하는 작업은 O(n)으로 수행 가능

=>  속도는 vector보다 빠르다.

-  덱은 vector와 달리 원소들이 실제 메모리 상에 연속적으로 존재하지는 않는다.

=>  원소들이 실제로 어디에 저장되어 있는지에 대한 정보를 보관하기 위해 추가적인 메모리가 더 필요하다.
ex) 64비트 libc++ 라이브러리의 경우 1개의 원소를 보관하는 덱은 그 원소 크기에 비해 8배나 더 많은 메모리를 필요로 한다.

-  덱은 실행 속도를 위해 메모리를 (많이) 희생하는 컨테이너라고 생각하면 된다.

-  덱의 원소들은 일정 크기로 잘려서 각각의 블록 속에 존재한다.

=>  블록들이 메모리 상에 어느 곳에 위치하여 있는지 저장하기 위해 각각의 블록들의 주소를 저장하는 vector가 필요하다.
==>  여기서 사용되는 vector는 기존의 vector와 달리, 새로 할당 시에 앞쪽 및 뒤쪽 모두에 공간을 남겨놓는다. (기존 vector는 뒤쪽에만 공간을 남겼음)
==>  따라서 맨 앞과 맨 뒤에 O(1)의 속도로 insert/erase 수행 가능

-  덱은 뒤나 앞에 원소를 추가할 때 기존 블록이 다 찼다면 새로운 블록을 만들어서 뒤에 추가되는 원소를 넣으면 된다.

=>  기존의 원소들을 복사할 필요가 없다.
==>  vector는 기존 메모리가 다 차면 새로운 공간을 할당 후 원소들을 모두 복사해서 뒤에 추가하는 작업을 진행한다.
==>  평균적으로 덱이 vector보다 더 빠르게 작동한다.
=>  덱의 경우 블록 주소를 보관하는 벡터가 꽉 차면 새로운 공간에 모두 복사해야한다.
==>  블록 주소의 개수는 전체 원소 개수 보다 적고, 대체로 벡터에 저장되는 객체들의 크기가 주소값의 크기보다 크기 때문에 복사 속도가 훨씬 빠르다.

-  덱은 모든 원소가 메모리 상에 연속적으로 존재한다고 보장할 수 없기 때문에 포인터 연산을 통해서 덱의 원소들을 '안전하게' 접근할 수 없다.

• 어떤 컨테이너를 사용할지?

-  일반적인 상황에서는 그냥 벡터 사용

-  임의의 위치에 원소들을 추가/제거 하는 일을 많이 하고, 원소들을 순차적으로만 접근한다면 리스트 사용

-  맨 처음과 끝 모두에 원소를 추가하는 작업을 많이하면 덱 사용

-  O(1)로 작동한다는 것은 이론적인 결과일 뿐이며, 실제 프로그램을 짜면 O(log n), O(n)보다 느릴 수도 있다.(n의 크기에 따라)

=>  속도가 중요한 환경이라면 적절한 벤치마크를 통해 성능을 가늠해 보는 것이 좋다.

 

 

 

 

---

 

 

 

 

틀린 부분이나 이상한 부분이 있으면 댓글로 편하게 지적해주세요!

감사합니다!

 

 

참고

씹어먹는 C++ - <10 - 1. C++ STL - 벡터(std::vector), 리스트(list), 데크(deque)> (modoocode.com)