[STL] vector

STL과 Container

STL은 Standard Template Library이다

프로그래밍할 때 필요한 자료구조/알고리즘을

템플릿으로 제공하는 라이브러리이다

 

이런 라이브러리에서

자료구조와 관련된 데이터를 저장하는 객체를

컨테이너(Container)라고 부르며

대표적으로 vector, list, map, set 등이 있다

 

 

배열 vs. vector(동적배열)

vector는 동적배열이다

일반적인 배열은 선언 이후에 capacity를 변경 불가하다

동적배열은 선언 이후에 capacity가 자동으로 변경된다

 

 

vector 간단한 사용법

#include <iostream>
#include <vector>
using namespace std;

void main(void)
{
	vector<int> v;
	v.push_back(1);// 현재 size에서 다음 위치에 데이터 입력
	v.push_back(2);
	v.push_back(3);

	int size = v.size();
	for (int i = 0; i < size; i++)
	{
		cout << v[i] << endl;
	}

	cout << v.front() << endl;// 가장 앞 데이터 출력
	cout << v.back() << endl;// 가장 끝 데이터 출력
	v.pop_back();// 가장 끝 데이터 삭제

	size = v.size();
	for (int i = 0; i < size; i++)
	{
		cout << v[i] << endl;
	}
}

 

 

vector의 원리

여유분을 두고 메모리를 할당해서 사용하고 있다가

여유분이 꽉 차게되면, 메모리를 증설한다

증설하는 과정에서 기존 데이터는 그대로 새로 동적할당된 메모리에 복사를 한다

 

 

capacity와 size

capacity는 총 용량이고 여유분을 포함한 전체 크기를 의미한다

size는 capacity에서 실제로 데이터가 차지하고 있는 크기를 의미한다

 

capacity를 처음부터 알고 있거나 예측이 가능한 경우

v.reserve()를 통해 capacity를 지정해 줄 수 있다

 

또한, size를 지정해주고 싶다면

v.resize()를 통해 size를 지정해줄 수 있다

v.resize()의 경우 size를 늘려주지만 당연히 capacity도 늘어나며

size와 capacity가 동일한 크기로 증가한다

#include <iostream>
#include <vector>
using namespace std;

void main(void)
{
	//vector<int> v;
	//v.resize(10);
 
        // 선언할 때, 사이즈와 초기화를 동시에 가능하다
	vector<int> v(10, 0);// 10으로 resize하고 0으로 초기화
	vector<int> v2 = v;// 복사도 정상적으로 가능하다

	int size = v.size();
	for (int i = 0; i < size; i++)
	{
		cout << v[i] << endl;
	}

	cout << v.size() << " " << v.capacity() << endl;

	size = v2.size();
	for (int i = 0; i < size; i++)
	{
		cout << v2[i] << endl;
	}

	cout << v2.size() << " " << v2.capacity() << endl;
}

 

 

v.resize() 주의점

사이즈 재정의 후 push_back을 하게되면

그 사이즈의 다음번 째로 데이터가 들어가게 되기 때문에

반드시 유의해서 사용해야 한다

#include <iostream>
#include <vector>
using namespace std;

void main(void)
{
	vector<int> v;

	v.resize(100);// 사이즈 재정의
	//v.resize(100, 0);// 0으로 초기화하면서 사이즈 재정의
	
	v.push_back(1);// v[101]의 값으로 들어가게 됨
        // v[0] = 1;// 이런식으로 접근
        // v[i] = a;// for문을 사용한다면 이런식으로 접근
        
	const int size = v.size();
	for (int i = 0; i < size; i++)
	{
		cout << v[i] << endl;
	}
}

 

 

v.clear() 주의점

v.clear()는 size를 0으로 만들어주는 것이고

capacity는 이전 상태를 그대로 유지한다

따라서 굳이 capacity까지 0으로 만들어주려면 swap을 이용하면 된다

 

또한, v.clear()는 절대 for문 안에서 작성하면 안 되고

작성해야 한다면, clear 되는 즉시 break를 통해 for문을 빠져나와야 한다 

#include <iostream>
#include <vector>
using namespace std;

void main(void)
{
	vector<int> v;

	v.reserve(10);
	v.resize(10);

	v.clear();
	vector<int>().swap(v);// 이렇게 임시로 만든 벡터와 swap을 하면된다

	const int size = v.size();
	for (int i = 0; i < size; i++)
	{
		cout << v[i] << endl;
	}

	cout << v.size() << " " << v.capacity() << endl;
}

 

 

iterator(반복자)

iterator는 포인터와 유사한 개념이다

컨테이너의 데이터를 가리키고, 다음/이전 원소로 이동이 가능하다

 

정확하게는 iterator는 포인터와 Myproxy와 Mynextiter 클래스를 포함한다

Myproxy 클래스는 컨테이너의 데이터를 반복자에게 노출하고

반복자가 데이터를 참조하여 탐색할 수 있게 한다

Mynextiter 클래스는 컨테이너의 요소를 하나씩 순회할 수 있도록 하고

반복자가 다음 요소로 이동하고,

현재 위치의 요소를 가리키고 있는지 확인하는 등을 담당한다

#include <iostream>
#include <vector>
using namespace std;

void main(void)
{
	vector<int> v(10, 0);

	vector<int>::iterator it = v.begin();
	int* ptr = &v[0];

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

	it++;
	++it;
	ptr++;
	++ptr;

	it--;
	--it;
	ptr--;
	--ptr;

	it += 2;
	ptr += 2;
}

 

 

v.begin()과 v.end()

v.begin()은 벡터의 첫 번째 시작주소를 가지고 있다

v.end()는 벡터의 size번째 다음 부분을 가리키고 있다 (마지막 데이터가 아니다!)

v.begin()

v.end() - size와 capacity가 동일한 경우

v.end() - size와 capacity가 동일하지 않은 경우

v.begin()과 v.end()의 활용

#include <iostream>
#include <vector>
using namespace std;

void main(void)
{
	vector<int> v(10, 1);

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

	cout << v.size() << " " << v.capacity() << endl;
}

 

++it vs ++it

iterator 내부 증감연산자를 살펴보면

전위 연산자와 후위 연산자의 차이는

전위 연산자의 경우는 계산하고 바로 포인터를 뱉어주지만

후위 연산자의 경우는 _Tmp(임시 공간)을 만들어서 복사하고 계산하고 포인터를 뱉어준다

 

이처럼 후위 연산자가 연산을 조금더 하기 때문에

전위 연산자가 성능에서 아주 미세하게 이득이다

 

 

왜 iterator?

iterator는 벡터뿐 아니라 다른 컨테이너에서도 공통적으로 사용 가능한 개념이다

따라서 stl을 사용할 때, iterator를 써서 다양하고 쉽게 활용 가능하다

 

const iterator와 reverse iterator

#include <iostream>
#include <vector>
using namespace std;

void main(void)
{
	vector<int> v(10, 1);

	for (int i = 0; i < v.size(); i++)
	{
		v[i] = i;
	}

	// const int* 형으로 받는 iterator
	vector<int>::const_iterator cit = v.cbegin();
	//*cit = 10;// 값 수정 불가능

	// 반대로 순회하는 iterator
	for (vector<int>::reverse_iterator rit = v.rbegin(); rit != v.rend(); ++rit)
	{
		cout << *(rit) << endl;
	}

}

 

 

vector의 효율

1) 중간 삽입/삭제

중간 삽입/삭제 둘 다 Bad

 

vector는 연속적인 배열이기 때문에

중간 삽입/삭제를 하려면 해당 중간 데이터를 기준으로 뒤에 있는 모든 데이터를

복사해서 앞당겨야 하기 때문에

매우 효율이 좋지 않다

 

어쩔 수 없이 사용해야 한다면

v.insert와 v.erase를 사용하면 된다

 

 

주의점 1. iterator의 위치

사용할 때는 iterator가 어디를 가리키는지가 중요하다

insert는 추가된 데이터의 위치를 가리킨다
erase는 삭제되고 뒤에 있는 데이터가 앞당겨진 위치를 가리킨다

 

또한, erase의 구간을 정해주는 함수에서는

ex. v.erase(v.begin() + 2, v.begin() +5);

시작 위치(v.begin() + 2)부터 끝 위치(v.begin() +5)까지가 아닌,

시작 위치(v.begin() + 2)부터 끝의 전 위치(v.begin() +4)라는 것을 유의해야 한다

그리고 iterator는 삭제되는 그 처음의 위치(v.begin() + 2)를 가리킨다

#include <iostream>
#include <vector>
using namespace std;

void main(void)
{
	vector<int> v(10);

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


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


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

	vector<int>::iterator eraseIt2 = v.erase(v.begin() + 2, v.begin() +5);

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

}

위의 결과

 

 

주의점 2. v.erase 사용 시

v.erase()를 사용하면

iterator가 날아가버린다는 점과

erase를 한 iterator는 다음 데이터를 가리킨다는 점을 유의해야 한다

 

따라서,

for문에서 특정 데이터를 삭제하려면

v.erase()를 하고 iterator에 erase를 한 iterator를 받아줘야 하고

erase를 한 iterator는 이미 ++it(다음 데이터를 가리키고 있으니)를 한 상태이니

++it 부분을 else문으로 빼줘야 한다

#include <iostream>
#include <vector>
using namespace std;

void main(void)
{
	vector<int> v(10);

	for (int i = 0; i < v.size(); i++)
	{
		v[i] = i;
	}

	// 모든 데이터를 순회하면서, 3이라는 데이터를 일괄 삭제하고 싶다면,
	for (vector<int>::iterator it = v.begin(); it != v.end(); )
	{
		if (*it == 3)
		{
			it = v.erase(it);// iterator가 날라가 버리니 erase의 iterator를 받아주고 있다
        }
		else
		{
			++it;// erase가 되면, iterator는 다음 데이터를 가리키기 때문에
                        // ++it를 해준 것과 같다
                        // 따라서,
                        // erase를 했다면 ++it를 해주지 않기 위해서 
                        // 이렇게 else문에서 ++it를 해주고 있다 
		}  
	}

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

 

 

2) 처음/끝 삽입/삭제
처음의 삽입/삭제는 Bad (처음의 삽입/삭제는 기능이 존재하지도 않음)

끝의 삽입/삭제는 Good

 

처음의 삽입/삭제는 중간 삽입/삭제와 마찬가지로 매우 효율이 좋지 않다

끝의 삽입/삭제는 쉽게 가능하다

 

 

3) 임의 접근

임의 접근은 Good

원하는 데이터를 v[2] = 3;처럼 쉽게 접근이 가능하다