[C++] STL - vector

STL이란?

C++에서 STL이란 Standard Template Library의 약자로 표준 템플릿 라이브러리를 의미한다.

C++에는 많은 표준 라이브러리들이 있지만 보통 STL을 말할때는 다음 세개의 라이브러리들을 의미한다.

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

 

그 중 컨테이너는 크게 두 가지 종류로 나눌 수 있다.

먼저 배열과 같이 객체들을 순차적으로 보관하는 시퀀스 컨테이너가 있고

key를 통해 대응되는 값을 찾아주는 연관 컨테이너가 있다.

 

시퀀스 컨테이너에는 다음과 같이 3개가 존재한다.

• vector
• list
• deque

 

오늘 포스팅에서는 일반적으로 가장 많이 사용되는 vector에 대해 정리할 것이다.

---

vector

벡터의 경우 가변길이 배열이라고 생각하면 쉽다.

vector를 생성하면 메모리의 heap 영역에 생성되며 동적할당된다.

 

※ vector의 초기화 방법

vector<자료형> 변수명	벡터 생성
vector<자료형> 변수명(크기)	벡터 생성 후 해당 크기를 할당(모든 요소 0으로 초기화)
vector<자료형> 변수명 = {변수1, 변수2, ...}	벡터 생성 후 오른쪽 변수 값으로 초기화
vector<자료형> 변수명[] = {,}	벡터 배열 선언 및 초기화(열은 고정, 행은 가변)
vector<vector<자료형>> 변수명	2차원 벡터 생성(열과 행 모두 가변)

 

벡터에는 원소들이 메모리 상에서 실제로 순차적으로 저장되어 있으며

따라서 임의의 위치에 있는 원소에 O(1)의 시간복잡도로 매우 빠르게 접근할 수 있다.

또한 맨 뒤에 새로운 원소를 추가하거나 제거하는 것 역시 O(1)에 수행한다.

 

벡터의 임의의 원소에 접근하는 방법은 배열처럼 []을 이용하거나 at 함수를 사용한다.

또한 맨 뒤에 원소를 추가할 때는 push_back, 제거할 때는 pop_back 함수를 사용한다.

 

하지만 벡터에도 단점은 존재한다.

맨 뒤에 원소를 추가하거나 제거하는 것은 빠르지만, 임의의 위치에 원소를 추가하거나 제거하는 것은

O(n)의 시간복잡도가 소요된다. 왜냐하면 원소 추가, 제거 이후 원소들을 한 칸 씩 이동시키는 과정이 필요하기 때문이다.

	방법	시간복잡도
임의의 위치 원소 접근	[], at()	O(1)
맨 뒤에 원소 추가 / 제거	push_back(), pop_back()	O(1)
임의의 위치 원소 추가 / 제거	insert(), erase()	O(n)

 

vector의 반복자

벡터의 경우 []을 이용해서 배열처럼 임의의 위치에 접근이 가능하지만, 반복자를 사용해서도 같은 작업을 수행할 수 있다.

반복자는 컨테이너에 iterator 멤버 타입으로 정의되어 있으며 다음과 같은 함수로 반복자를 얻을 수 있다.

begin()	벡터 시작점의 주소값 반환
end()	벡터 끝지점 + 1의 주소값 반환
rbegin()	벡터의 끝지점을 시작점으로 반환
rend()	벡터의 시작 - 1 지점을 끝 지점으로 반환

#include <iostream>
#include <vector>

int main(){
    std::vector<int> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);

    for(std::vector<int>::iterator itr = v.begin(); itr != v.end(); itr++){
        std::cout << *itr << std::endl;
    }

    std::vector<int>::iterator itr = v.begin() + 2;
    std::cout << "3번째 원소 : " << *itr << std::endl;
}

vector의 반복자 타입은 위처럼 std::vector<>::iterator로 정의되어있다. 

또한 반복자를 포인터처럼 사용하여 *을 통해 itr가 가리키는 원소를 볼 수 있고

+ 연산자를 통해 그 만큼 떨어져 있는 원소를 가리키게 할 수 도 있다. 

 

※ 그 외 vector 메소드들

front()	벡터의 첫 번째 요소 접근
back()	벡터의 마지막 요소 접근
clear()	벡터의 모든 요소를 지움
empty()	벡터가 빈 공간이면 true, 아니면 false
size()	벡터의 크기 반환

---

참고 : https://modoocode.com/223