[자료구조 in C++] 동적 배열(Vector)

자료구조에서 Vector 란?

자료구조에서 "벡터"(Vector)는 동적 배열을 의미하는데, 이는 고정된 크기를 가진 일반적인 배열과 달리 크기가 동적으로 변할 수 있는 배열이다.

 

이전 글에서 언급했던 array와 비슷한 개념이지만, 크기가 고정되어 있고, 메모리 할당 방법을 변경할 수 없는 array의 문제를 해결할 수 있다. 

 

즉, vector의 경우,  원소가 추가되고 제거됨에 따라 동적으로 크기가 조정되고, 연속적으로 메모리를 할당할 수 있다.

 

 

Vector 선언 방법

#include <iostream>
#include <vector>

int main()
{
	std::vector<int> vec; //크기 0인 벡터 선언
    
    std::vector<int> vec = {1,2,3,4,5};  //지정한 초기값으로 이루어진 크기가 5인 벡터 선언
    
    std::vector<int> vec(10);  //크기가 10인 벡터 선언
    
    std::vector<int> vec(10,5);  //크기가 10이고 모든 원소가 5인 벡터 선언
}

 

 

push_back(), insert()

벡터에 새로운 원소를 추가하려면 push_back() 또는 insert()를 사용한다.

 

- push_back(): 벡터의 맨 마지막에 원소를 추가

- insert(): 삽입할 위치를 나타내는 인자를 첫번째 인자로 받음으로써 원하는 위치에 원소 추가

 

push_back(val):
	if size < capacity:	//새 원소를 추가할 공간이 있는 경우
    	-마지막 원소 다음에 val 저장
        -벡터 크기를 1만큼 증가
        -return;
        
    if vector is already full:	//할당된 메모리 공간이 가득 찬 경우
    	-2*size 크기의 메모리를 새로 할당
        -새로 할당한 메모리로 기존 원소를 전부 복사/이동
        -데이터 포인터를 새로 할당한 메모리 주소로 지정
        -마지막 원소 다음에 val을 저장하고, 벡터 크기를 1만큼 증가

 

• 원소 삽입 시 뒤쪽에 남아있는 공간이 있다면, 시간은 $O(1)$만큼 걸린다.
• 공간이 충분하지 않다면 모든 원소 복사/이동, $O(n)$의 시간 소요
• 보통은 용량이 부족하 경우 두 배로 늘리기 때문에 꽉 찬 경우, 원소 한 두 개만 삽입하는 일은 거의 없다고 봐도 된다. 

따라서 보통의 경우 시간 복잡도가 $O(1)$에 가깝게 되므로, push_back()은 매우 빠르게 동작한다.

하지만, insert()의 경우, 지정한 반복자 위치 다음의 원소들을 모두 이동하는 작업이 필요하므로 $O(n)$의 시간이 걸린다.

 

vec.insert(int.begin(), 0);

std::vector<int> vec;	//비어 있는 벡터 생성

vec.push_back(1);	//맨 뒤에 1 추가: {1}

vec.push_back(2);	//맨 뒤에 2 추가: {1,2}

vec.insert(vec.begin(), 0);	//맨 앞에 0 추가: {0,1,2}

vec.insert(find(vec.begin(), vec.end(), 1), 4); //1 앞에 4추가: {0,4,1,2}

 

 

emplace(), emplace_back(), pop_back(), erase()

push_back은 컨테이너에 요소를 추가할 때, 해당 요소의 복사본을 만들어서 추가한다. 이는 복사 생성자를 호출하여 객체를 먼저 생성한 다음, 이 객체를 컨테이너에 복사하는 과정을 포함한다.

 

반면, emplace() 또는 emplace_back()을 사용하면,

1. 효율성: 컨테이너의 메모리 위치에 직접 객체를 구성함으로써 복사나 이동을 방지하고, 이로 인해 발생할 수 있는 성능 저하를 줄인다.
2. 객체 생성의 직접성:  객체를 생성할 때 생성자에 전달되는 인자를 직접 받는다. 이는 컨테이너가 객체의 생성자를 직접 호출하여, 임시 객체의 생성 없이 원하는 객체를 컨테이너에 바로 추가할 수 있게 한다

 

원소를 지울 때는, pop_back()와 erase() 함수를 제공한다.

 

-pop_back() 함수는 맨 마지막 원소를 제거하며, 벡터 크기는 1만큼 준다.

 

-erase() 함수는 두 가지 형태로 오버로딩 되어있다.

     ⓛ : 반복자 하나를 인자로 받아 해당 위치 원소를 제거

     ② : 시작과 끝을 나타내는 반복자를 받아 시작부터 끝 바로 앞 원소까지 제거

 

<예제 코드>

std::vector<int> vec = {0,1,2,3,4,5,6,7,8,9}

vec.pop_back(); //맨 마지막 원소 하나를 제거: {0,1,2,3,4,5,6,7,8}

vec.erase(vec.begin()); //맨 처음 원소를 제거: {1,2,3,4,5,6,7,8}

vec.erase(vec.begin() + 1, vec.begin() + 4) // 1~3번째 원소 제거: {1,5,6,7,8}

 

 

몇 가지 유용한 멤버 함수

함수명	설명
clear()	모든 원소를 제거하여 완전히 비어 있는 벡터를 만든다
reserve(capacity)	벡터에서 사용할 용량 지정. (if: 매개변수 > 매개변수 만큼 메모리 추가 할당,  else: 아무런 동작 x)
shrink_to_fit()	여분의 메모리 공간 해체하는 용도. 벡터의 용량이 벡터의 크기와 같아짐

 

 

참고 문헌

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ " target="_blank" rel="noopener" data-mce-href="http:// 코딩 테스트를 위한 자료 구조와 알고리즘 with C++ ">http:// 코딩 테스트를 위한 자료 구조와 알고리즘 with C++

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ - 예스24