C++ STL - 시퀀스 컨테이너

  C++로 알고리즘을 하겠다고 생각한 후부터 늘 STL을 살펴봐야지, 살펴봐야지 하고 드디어 살펴보게 되었다. 실제로 알고리즘 문제를 풀 때 얼마만큼 적용해볼 수 있느냐가 문제일텐데... 우선은 아는 것이 중요하니 개념부터.

 

  언제나 늘 보던 그 씹어먹는 C++강좌와 위키피디아, 그리고 일부 C++관련 게시물을 참고했다.

 

---

C++ STL(Standard Template Library)

  해석하면 'C++ 표준 라이브러리'라고 불리는 이 라이브러리는 4가지의 라이브러리로 이루어져 있다고 한다.

 

1. 알고리즘
2. 컨테이너
3. 반복자
4. 함수자

  보통 STL이라고 하면 위의 3개(알고리즘, 컨테이너, 반복자) 위주로 사용되는 듯 하다. 실제로 알고리즘 문제 풀이를 살펴볼 때도 많이 봤던 익숙한 얼굴들이고... 그중에서도 오늘 훑어본 것들은 컨테이너와 반복자.

 

 

컨테이너(Container)

  컨테이너는 이름에서도 알 수 있듯 '데이터를 저장하는 객체'이다. 주목할만한 점은 C++의 '템플릿' 덕분에 어느 타입으로 선언하듯 다 사용할 수 있다는 것. 일반적인 자료형이 아니라 사용자가 직접 만든 임의의 객체라도 사용할 수 있다는 장점이 있다.

 

  컨테이너에는 크게 2가지가 있는데, 하나는 객체들을 순차적으로 보관하는 '연속(혹은 시퀀스) 컨테이너', 또 다른 하나는 Key-Value 구조를 갖는 '연관 컨테이너'이다. 오늘 적을 것은 연속 컨테이너와 이에 접근할 때 사용하는 반복자에 대한 것이다. 연속 컨테이너에는 vector, list, deque, 그리고 위키피디아에 의하면 slist가 있다고 한다. 

 

 

Vector

  알고리즘 풀이에서 가장 많이 보이는 걔. 배열이긴 배열인데 동적인 배열, 즉 가변길이 배열이라고 볼 수 있다. 그렇기에 벡터에 원소 삽입/제거 작업을 수행하면 자동적으로 길이를 조정한다. 벡터는 원소들이 메모리 상에서 순차적으로 저장되어 있어 임의 원소에 대한 접근이 빠르게 수행된다(O(1)). 다루는 것 자체는 그냥 평범한 배열처럼 다룰 수 있다. (그래서 원소에 접근할 때도 vector[index] 의 꼴로 접근할 수 있다는 것 같다.) 사용하기 위해서는 vector 라이브러리를 import하면 된다.

 

  vector의 멤버 함수는 다음과 같다.

 

이름	기능
push_back	벡터의 맨 끝에 원소를 추가한다.
pop_back	마지막 원소를 삭제한다.
insert	원소를 원하는 위치에 삽입한다.
erase	원하는 범위 속의 원소들을 삭제한다.
at	지정한 위치에 있는 원소를 반환한다.
front	벡터의 맨 앞에 있는 원소를 반환한다.
back	벡터의 맨 뒤에 있는 원소를 반환한다.
size	벡터의 size를 반환한다. (즉, 원소의 개수를 반환)
capacity	벡터에 할당된 메모리 크기를 반환한다.
empty	벡터가 비어있으면(아무런 원소도 없으면) true, 아니면 false를 반환.

  이 이외에도 다양한 것들이 존재한다.

 

Capacity와 Size

  벡터의 요소들을 살펴보면 capacity와 size가 따로 존재함을 알 수 있다. 위의 표에서도 강조했지만 이 둘은 같은 것이 아닌데, capacity가 존재하는 이유는 벡터가 현재 길이(size)보다 좀 더 많은 공간을 할당해두기 때문에 이를 따로 나타내기 위해서다. 따로 찾아보니 메모리 할당 시 기존 메모리의 2배 정도를 할당한다는 것 같다. (size의 2배라는 말은 아님...) 따라서 사전에 미리 할당 된 공간을 다 쓰지 않는 이상, 벡터의 맨 뒤에 원소를 새로이 추가하는 작업은 O(1)이 걸리게 된다.

 

  다만 할당된 공간을 다 쓰게 된다면? 이 경우, 더 큰 크기로 벡터 공간을 다시 할당하고 원소들을 새 벡터에 복사해와야 하는 과정이 필요하기 때문에 위의 경우보다 시간이 더 걸리게 된다. 이게 O(n)이 걸리는데, 앞에서도 언급했듯 벡터는 공간을 미리 할당해놓는 특성 탓인지 O(n)이 걸릴 경우가 거의 없어서 평균적으로는 O(1)으로 수행된다고 이야기한다고... 아무튼 Capacity는 Size와 같은 것이 아니다. 명심명심.

 

 

반복자 (Iterator)

  반복자는 쉽게 말해 '컨테이너 속 원소들에 접근할 수 있는 포인터'의 역할을 수행한다고 한다. 포인터와 같은 역할을 수행하기 때문인지, 반복자를 통해 컨테이너 속 원소에 접근하려면 마치 포인터처럼 * 을 사용한다.

 

  앞서 언급한 벡터에서 반복자를 얻는 방법은 begin()과 end()를 사용하는 것이다. 이 둘은 각각 벡터의 첫 번째 원소를 가리키는 반복자, 벡터의 마지막 원소의 한 칸 뒤를 가리키는 반복자를 반환한다. 위 표에 있는 insert나 erase함수도 원소를 삽입/삭제할 위치에 대한 매개변수를 반복자 타입으로 받는다.

 

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v;
    
    for (int i = 0; i < 5; i++)
    {
    	v.push_back(i + 1);
    }
    
    for (std::vector<int>::iterator itr = v.begin(); itr < v.end(); itr++)
    {
    	std::cout << * itr << " \n";
    }

    return 0;
}

  대충 이런 식으로 쓴다고 보면 될 것 같다.

 

  다만 반복자를 이용해서 벡터에 접근할 때는 주의할 사항이 있는데, 벡터에 반복자를 사용해서 원소를 추가하거나 지우면(즉, insert나 erase를 사용하게 되면) 기존에 벡터를 가리키던 반복자를 사용할 수 없게 된다는 것이다. 이에 대한 해결법은 STL의 알고리즘 라이브러리를 배우면서 알 수 있다니 일단 그 때 다시 보는 걸로...

 

  또한 벡터의 경우, 역반복자라는 것도 존재한다. 말 그대로 벡터의 구성 요소들을 뒤에서부터 접근하는 반복자인데, '그냥 for문으로 벡터의 끝에서 처음까지 접근하면 안 되는 걸까?' 싶었지만 안 되는 이유가 있으니까 만들어졌겠지... 그 이유는 벡터의 index를 나타내는 타입이 '부호 없는 정수'이기 때문이라고 한다.

 

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);

	//size_type : 벡터의 원소의 개수 형식
    for (std::vector<int>::size_type i = v.size() - 1; i >= 0; i--)
    {        
        std::cout << v[i] << std::endl;
    }

    return 0;
}

 

  따라서 이 코드를 실행해보면 에러가 난다. 에러 내용인 'vector subscript out of range'는 벡터의 크기를 벗어나는 데이터를 참조하려 하였을 경우에 발생하는 에러. 의도대로라면 반복문의 i가 -1이 되며 반복문이 끝나야 하겠지만, 0인 i에서 1을 뺐을 때 -1이 아닌 다른 정수가 되어버리기 때문에 접근이 잘못되는 것이다. 그러니 역반복자를 기억해두었다가 잘 써먹자.

 

 

List

  리스트는 이중연결리스트, 즉 양방향 연결 구조를 가진 자료형이라고 한다. 리스트 속 각 원소들은 자기 앞/뒤에 있는 원소들을 기억하고 있고, 리스트 자체는 자신의 처음과 끝 원소밖에 기억하지 않기 때문에 벡터처럼 임의의 원소에 대해서는 접근할 수 없다. 대신, 임의의 위치에 원소를 추가하거나 제거하는 과정은 O(1)으로 매우 빠르게 수행된다. 원소들이 앞뒤 원소를 기억하는 리스트의 구조 상 벡터와는 달리 원소들이 메모리 상에서 연속적으로 존재하지 않을 수도 있다. 사용하기 위해서는 list 라이브러리를 import하면 된다.

 

  리스트 자체가 임의의 원소에 접근할 수 없기 때문인지, 리스트의 반복자는 순차적인 연산(++나 --)은 가능하지만 다른 연산 (+나 -)은 불가능하다. 즉, 리스트의 반복자는 오직 앞뒤로 한 칸 씩만 움직일 수 있다.

 

 

Deque (덱)

  덱은 벡터와 비슷하지만 조금 특이한 구조이다. 특징은 아래와 같다.

• 임의의 원소에 접근할 수 있다. 속도도 벡터랑 같이 O(1)이다.
• 구조 멘 앞이나 뒤에 원소를 추가/제거 하는 속도도 O(1)이다. 
• 임의의 위치에 원소를 추가/제거하는 것은 벡터보다 빠른 O(n)이다.

  전체적으로 벡터와 비슷하되 속도상으로 우위에 있다는 느낌이지만, 이러한 속도를 내기 위해 덱은 메모리를 희생한 구조이다. 벡터는 원소들이 메모리 상에 연속적으로 존재하지만 덱은 그렇지 않기 때문에, 각 원소들의 위치가 어딘지를 추가적으로 저장해두어야 한다.

 

 

---

  아무래도 알고리즘에서는 벡터를 잘 사용하는 것 같아서 벡터만 함수까지 다 정리를 해놨는데, 다른 구조들의 함수들도 언젠가 살펴보아야겠다. 다음에는 연관 컨테이너들을 보고 글 쓰는 걸로.

 

참고

• https://ko.wikipedia.org/wiki/%ED%91%9C%EC%A4%80_%ED%85%9C%ED%94%8C%EB%A6%BF_%EB%9D%BC%EC%9D%B4%EB%B8%8C%EB%9F%AC%EB%A6%AC#%EC%BB%A8%ED%85%8C%EC%9D%B4%EB%84%88

표준 템플릿 라이브러리 - 위키백과, 우리 모두의 백과사전

• https://www.cplusplus.com/reference/vector/vector/

vector - C++ Reference

• https://modoocode.com/223

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