c++ 기초 - 벡터 (vector)

STL?

Standard Template Library의 약자로 미리 구현된 자료구조와 알고리즘들을 템플릿으로 제공하는 라이브러리이다.
STL은 크게 알고리즘, 컨테이너, 함수자, 반복자(iterator)로 구성되어 있다.

컨테이너 (Container)

데이터를 저장하는 객체(class template)를 의미한다. 데이터를 효과적으로 저장하기 위한 자료구조를 제공해준다.

시퀀스 컨테이너 (Sequence Container) 

요소가 삽입된 순서를 유지해주는 컨테이너이다. (즉, 요소들이 들어온 순서대로 나열되어 있는 형태이다.)
대표적으로 array, vector, list, deque이 있다. 오늘은 그 중 vector를 다뤄보고자 한다.

벡터 (vector)

벡터는 자동적으로 메모리가 할당되는 배열이다. 동적 배열이며 기존 배열처럼 크기가 고정되지 않고 유동적으로 크기가 변하는 배열이다.
 

선언
1) 헤더 파일 및 네임스페이스 정의

#include<vector>
using namespace std; // 편리성 위해 사용

 
2) 다양한 방식의 선언 및 초기화

1. 빈 벡터
vector<자료형> 벡터이름;

2. 지정한 크기에 모든 요소 0으로 초기화된 벡터 생성
vector<자료형> 벡터이름(크기);

3. 지정한 크기에 모든 요소 기본값으로 초기화된 벡터 생성
vector<자료형> 벡터이름(크기, 기본값);

4. 복사할 벡터와 동일한 크기와 데이터를 가지는 벡터 생성
vector<자료형> 벡터이름(복사할벡터이름)

동작 원리

벡터는 동적 "배열"이기 때문에 데이터는 연속적으로 존재한다.
 
우선 원리를 알아보기전 벡터의 대표적인 특징인 size와 capacity에 대해 살펴보자. 벡터의 size는 실제로 벡터에 들어있는 요소들의 개수를 나타낸다. capacity의 경우 현재 vector가 사용할 수 있는 메모리 공간의 크기를 나타낸다. 즉 size + 남은 공간이라고 생각하면 된다.

 
 
벡터가 만들어지면 처음에 사용할 수 있는 메모리 공간이 있고, 이 공간을 다 채우게 되면(size == capacity) 더 큰 메모리 공간을 잡아서 기존의 데이터를 복사해 옮기는 식으로 동작한다.

 

데이터를 하나 늘릴때마다 매번 공간을 할당 받고 기존의 데이터들을 복사해가는 것은 상당히 비효율적이다. 따라서 다음 배열 공간 크기를 할당 받을 때는 기존의 capacity에 비례해서 늘어나게 된다. (컴파일러별로 capacity를 몇 배씩 늘리는지 차이가 있다.)

❓ malloc으로 뒤에 영역 더 할당 받으면 안되는지?

다른 곳에서 이미 해당 자리 사용하고 있을 수 있다. 따라서, 메모리 공간에서 다른 위치로 그냥 전체를 복사해 옮기게 된다. (단, 복사해야할 양이 많다면 복사하는데 비용이 많이 든다. 그래서 크게 두는 것이 확실한 경우 여유분을 충분히 둬야 복사해서 옮기는 일이 적게 일어난다.) 

중간 삽입 /삭제 👎

벡터의 요소들은 메모리 공간에 연속적으로 저장된다. 중간에 요소를 삽입하기 위해서는 넣고자 하는 위치 뒤의 공간을 모두 한 칸씩 뒤로 이동 후 빈 공간을 만들어 넣어준다. 뒤의 공간에 요소들이 많이 있다면 상당히 비효율적인 작업이다.
 
중간의 요소를 삭제하는 것도 유사하다. 요소들이 연속되어야 하므로 뺀 자리를 채우고자 뒤의 요소들을 모두 한 칸씩 앞으로 이동시켜줘야 한다. 따라서 벡터에서는 중간 삽입과 삭제가 비효율적인 작업이다.

❓️ 데이터는 왜 연속되어야 하는가?
데이터를 찾는 입장에서 생각해보자. 데이터가 연속되어 있어야 자료형 크기를 기반으로 산술 연산을 통해 쉽게 특정 위치의 데이터에
접근할 수 있게 된다. 즉, 편리한 접근을 위해서라 볼 수 있다.

처음 삽입/삭제 👎 & 끝 삽입/삭제 👍

처음의 경우 중간 삽입 삭제와 동일하게 동작하기에 처음에 요소를 삽입하고 삭제하는 것은 비효율 적이다. 
반면, 끝에 요소를 삽입하고 삭제하는 과정은 따로 다른 데이터를 이동시킬 필요가 없기 때문에 효율적으로 동작한다. (따라서, vector 기능에는 push_back과 pop_back 같이 뒤에서 하는 연산들이 존재하는 것이다.)

임의 접근 👍

모든 데이터들이 연속적으로 위치하고 있기 때문에 임의 접근이 가능하다.
즉, i번째 데이터를 찾는 경우 배열에서 시작 주소에서 요소 크기 * 찾을 위치로 바로 원하는 메모리 공간을 찾아낼 수 있다. (인덱스로 바로 접근 가능!) 

자주 사용되는 멤버 함수

벡터 요소 가져오기

• front(): 제일 앞 요소
• back(): 제일 뒤 요소
• v[i]: i번째 요소

벡터 요소 추가 및 제거 (마지막)

• push_back(값): 벡터의 마지막에 값 추가
• pop_back(): 벡터의 마지막 요소 제거

using namespace std;
#include <vector>
int main()
{
    vector v;
    v.push_back(1);
}

• insert(위치, 값): 벡터에서 정한 위치에 값 추가 
• erase(위치): 위치에 있는 값 제거
• erase(시작 위치, 끝 위치): 설정한 범위의 요소들 제거 (마지막은 포함 x)

// 중간 추가
// 기존 배열: 0, 1, 2, 3, 4
v.insert(v.begin() + 2, 5); // 0 1 5 2 3 4

// 중간 삭제
v.erase(v.begin() + 2); // 0 1 2 3 4

// 범위로 삭제
v.erase(v.begin() + 2, v.begin() + 4); // 0, 1, 4

 
벡터의 용량과 크기

• capacity(): vector에 할당된 메모리 공간 크기
• size(): vector에 실제로 들어있는 데이터 개수

const int size = v.size(); // vector에 든 실제 데이터 개수
const int capacity = v.capacity(); // vector에서 현재 사용할 수 있는 전체 메모리 공간

• reserve(용량): vector의 capacity를 용량으로 설정한다. (주로 값이 자주 추가될 벡터라면 처음부터 capacity를 설정해 불필요한 메모리 재할당을 방지할 수 있다.)

reserve의 경우 현재 vector capacity > 바꿀 capacity일 때만 동작한다. 

v.reserve(1000); // 용량 1000으로! (처음부터 설정할 수도 있다.)

• resize(count): 벡터의 크기를 count로 변경한다. 

1. 기존 size < count라면 기본 생성자를 호출해 기본값들로 채워 크기를 count까지 늘린다. 
2. 기존 size > count라면 기존 벡터에서 가지고 있던 값 중 초과된 위치에 있는 것들을 제거한다. (원소 개수 줄이기)

v.resize(1000);

 생성자에서 처음부터 size를 설정하는 것도 가능하다. 그에 맞춰 capacity도 자동으로 늘어난다.

vector v(1000, 0); // 크기, 초기값

 
정리하면, reserve는 벡터의 capacity를 변경하고 resize는 벡터의 size를 변경한다. (resize는 벡터 size 늘어나면서 메모리 재할당을 요구한다!)

• clear(): 모든 요소 제거 (size = 0, capacity = 유지)

v.clear(); // size는 0으로, capacity는 줄어들지 않음!

• swap(벡터이름): 두 벡터끼리 서로 교환한다.

주로 vector 메모리 해제를 위해 사용한다. 앞서 clear를 호출하면 size는 0으로 만들 수 있었지만 capacity는 그대로였다. 즉, 메모리에 계속 남아있게 되는데 capacity도 0으로 만들어 메모리에서 제거할 때 주로 swap 함수를 사용하게 된다.
임시로 벡터를 생성한 후 (size, capacity = 0) capacity를 0으로 만들고자 하는 벡터와 swap 시킨다. 그럼 기존에 있던 벡터가 내용물이 바뀌어 capacity가 0이 되고, 해당 줄이 실행된 이후 임시로 만들어진 벡터도 소멸되며 메모리에서 해제된다. 

vector<int>().swap(v); //원래 v는 swap해서 빈 상태로 변하게 된다.

 
 

구현

다음 포스트에서 vector를 구현한 내용을 확인할 수 있다.
2024.02.18 - [c++/자료구조 & 알고리즘] - c++ - 동적 배열 구현 (vector 구현)

c++ - 동적 배열 구현 (vector 구현)