cpp STL vector편

STL(Standard Template Library)

프로그래밍을 할 때 필요한 자료구조/알고리즘을 템플릿으로 제공하는 라이브러리이다.

 

컨테이너(Container)

STL의 구성품 중 하나. 데이터를 저장하는 객체이며, 이를 자료구조(Data Structure)라 한다. 즉, 자료구조는 데이터를 저장하는 방식이다. 이제부터 알아볼 vector는 시퀀스 컨테이너( Sequence Container )의 한 종류다. 시퀀스 컨테이너는란 데이터가 삽입 순서대로 나열되는 형태를 지니는 자료구조다. vector, list, deque가 시퀀스 컨테이너에 속한다.

 

 

Vector

vector는 면접에서도 자주 등장하는 개념이다. vector가 동작하는 원리를 아는 것이 좋다.

vector는 동적 배열이다. 배열의 단점인 크기를 수정할 수 없다는 점을 보완한 것이 동적 배열이다.

그렇다면 동적 배열의 크기가 유동적으로 변경 가능한 이유는 2가지가 있다.

1. 여유분을 두고 메모리를 할당한다.
2. 여유분까지 메모리를 사용했으면, 메모리를 증설한다.

메모리를 증설하는 방법은 기존에 있던 영역을 없애고 새로운 영역을 만드는 방식이다.

#include <vector>

vector<int> v;	// 템플릿 형식
vector<int> vec(100, 0);	// vec은 size가 100이고, 100개의 데이터를 0으로 세팅

for (int i = 0; i < 1000; i++)
{
	v.push_back(100);
	cout << v.size() << " " << v.capacity() << endl;
}

v.clear();

#include <vector> 잊지 말자!

vector는 템플릿 형식으로 생성할 수 있다. vector는 다양한 함수를 지원하는데 push_back은 vector에 data를 추가하는 것이고, size는 vector에 저장된 data의 크기를 나타낸다. capacity는 여유분을 포함한 총 용량의 수를 나타낸다. clear는 vector의 data를 삭제하는 역할이다. 

 

여기서 자세히 살펴봐야 할 함수는 size와 capacity가 있다.

 

앞서 여유분 또는 증설을 통해 메모리를 확보한다고 했다. 그렇다면 여유분과 증설의 크기는 어느정도가 적당할까?

위 코드의 for문을 돌려보면 size는 1개씩 늘어나지만 capacity는 1.5배(컴파일러마다 다르다) 정도 늘어나는 것을 알 수 있다. 이때 메모리 할당은 컴파일러가 결정하지만 우리가 직접 정할 수도 있다.

vector<int> v2;
v2.reserve(1000);	// 미리 capacity를 세팅
v2.resize(1000);	// 미리 size를 세팅

이렇게 세팅을 미리하면 좀 더 효율적인 코드를 작성한 것이다.

이는 증설하기 전에 있던 기존의 데이터를 어떻게 처리하는지를 살펴보면 알 수 있다.

기존에 할당된 메모리를 모두 사용하면 증설을 하면서 기존에 있던 데이터를 모두 새로운 메모리에 복붙한다.

즉, 증설할 때마다 데이터를 복붙하는 과정이 발생한다. 이런 과정을 줄이기 위해 capacity의 용량을 미리 할당하는 것이다.

 

vector<int> v(10);

for (vector<int>::size_type i = 0; i < v.size(); i++)
	v[i] = i;

vector로 반복문을 사용하고 싶으면 위처럼 해야 한다. v.size()는 unsigned int를 리턴하기 때문에 i가 type을 맞춰줘야 한다. 

 

vector의 중요한 특징

면접 단골 질문!!

원소가 하나의 메모리 블록에 연속하게 저장된다. 이러한 특징은 vector의 원소를 삽입/삭제할 때 큰 영향을 미친다.

1. 중간 삽입/삭제
2. 처음/끝 삽입/삭제
3. 임의 접근(Random Access)

위 3가지 경우를 두고 vector를 살펴보자.

vector의 메모리 중간에 원소를 삽입/삭제할 경우 매우 비효율적인 과정을 거쳐야 한다. 몇 백개의 데이터가 vector에 존재할 때 10번째 메모리에 원소를 삽입한다면, 기존에 존재하던 10번째 원소부터 마지막 원소까지 한 칸씩 뒤로 밀려야 한다. 삭제 또한 마찬가지다. 이와 같은 원리로 처음에 삽입/삭제하는 과정도 매우 비효율적이다.

하지만 메모리 끝에서 삽입/삭제가 일어나면 이러한 비효율적인 과정 없이 바로 적용할 수 있기 때문에 상관없다.

v.push_back();
v.pop_back();

vector에 back만 있고 push_front, pop_front가 없는 이유다!

 

임의 접근이란 몇 번째 데이터는 어디에 있는지 찾는 것을 나타낸다.

v[10] == 3;

연속된 메모리 블록을 이용하기 때문에 임의 접근이 가능하다.

 

비효율적이지만 중간 삽입/삭제를 이용할 수도 있다.

vector<int>::iterator insertIt = v.insert(v.begin() + 10, 5);
vector<int>::iterator eraseIt = v.erase(v.begin() + 10);

10번째 인덱스에 데이터 5를 삽입하거나 10번째 인덱스에 존재하는 데이터를 삭제할 때 사용한다. 이때 각 함수는 삽입/삭제한 위치를 리턴한다.

 

 

iterator(반복자)

컨테이너마다 반복자를 가지고 있다. 이는 포인터와 유사한 개념이다.

iterator는 컨테이너의 원소(데이터)를 가리키고, 다음/이전 데이터로 이동할 수 있다.

vector<int>::iterator it;
int* ptr;

iterator는 vector<T>(vector는 컨테이너) 내에 정의된 iterator라는 타입이다. 이때 using iterator로 정의했으며 여기서 using은 typedef와 비슷한 개념이다. 이를 나타내기 위해 :: 을 이용한다. iterator는 다양한 pointer 동작을 오버로딩하기 때문에 포인터처럼 사용할 수 있다. 

 

참고로 클래스 내에 다른 클래스 이름을 정의하는 이유는 설계상 유용하기 때문이다. 

예를 들면, Player 클래스에 using Pet = Cat으로 Cat 클래스의 별칭을 설정한다고 하자. Knight::Pet pet은 Cat pet과 같은 의미로 사용할 수 있다. 이는 코드를 수정할 때 정말 유용하다. 나중에 Cat이 아니라 Dog로 수정해야 할 때, using Pet = Dog로만 수정하면 다른 코드를 건드리지 않아도 된다.

 

it = v.begin();
ptr = &v[0];

cout << (*it) << endl;
cout << (*ptr) << endl;

시작 주소를 가리킬 때를 보면, 포인터와 iterator는 표현의 방식만 다를 뿐 비슷한 개념임을 알 수 있다.

 

vector<int>::iterator itEnd = v.end();

위 코드는 vector<int> v의 마지막 주소를 가리키는 것처럼 보이지만, 전혀 그렇지 않다. itEnd가 어떤 메모리를 가리키고 있는지 보면, itEnd는 v의 유효메모리 다음을 가리키고 있다는 것을 알 수 있다.

[ v의 유효메모리  ] [ end가 가리키는 주소 ]

즉, itEnd는 쓰레기 값이 들어있는 메모리를 가리킨다. 따라서 itEnd에 접근해서 메모리 관련 작업을 해서는 안된다. 그저 끝을 판단하는 용도로 이용하자.

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

유효하지 않는 주소값이 나올때까지 반복한다. 이때 ++it를 사용하는게 조금 더 빠르다. it++하면 복사하는 과정이 추가되기 때문이다.

 

iterator는 vector보다 복잡한데 사용하는 이유가 뭘까?

iterator는 vector뿐 아니라 다른 컨테이너에도 공통적으로 존재하기 때문에 사용하는 것이다. 즉, 다른 컨테이너(자료구조)와 함께 사용할 수 있기에 범용성이 넓다.

 

기타

vector<int>::const_iterator cit = v.cbegin();

for (vector<int>::reverse_iterator it = v.rbegin(); it != v.rend(); ++it)
{
	cout << (*it) << endl;
}

const_iterator는 const int*와 같은 기능이다. 즉, read만 가능하다.

reverse_iterator는 역방향 반복자다. 

 

 

 

출처

https://www.inflearn.com/course/%EC%96%B8%EB%A6%AC%EC%96%BC-3d-mmorpg-1/dashboard

[C++과 언리얼로 만드는 MMORPG 게임 개발 시리즈] Part1: C++ 프로그래밍 입문 - 인프런 | 강의