(C++)Vector / Deque

시퀀스 컨테이너인 Vector와 Deque에 대해 차이점 위주로 알아보도록 하자.

 

공통점

둘은 정말 비슷한 컨테이너라 할 수 있다. 원소 추가, 삭제, 조회 , 연산 모두 같은 방식으로 호출하고 사용된다. 

 

- erase

원소를 삭제할때 erase를 호출하며 배개변수로 반복자포인터 하나가 들어갈 수도 있고 두개가 들어가서 한번에 여러 범위의 원소를 지울 수 있다. 주의 해야 할 점은 반복자 순회에서 해당 위치의 원소 삭제 후 해당 포인터가 삭제되므로 순회할때 예외적으로 처리 해줘야 한다.

 

아래는 해당 코드이다.

int main()
{
	vector<int> vec;
	vec.push_back(1);
	vec.push_back(4);
	vec.push_back(1);
	vec.push_back(1);
	vec.push_back(1);
	for (vector<int>::iterator it = vec.begin(); it != vec.end();)
	{
		if (*it == 4)
		{
			it = vec.erase(it);
		}
		else
			it++;
		
	}
	for (vector<int>::iterator it = vec.begin(); it != vec.end(); it++)
	{
		cout << *it << endl;

	}
	
}

   erase는 삭제된 다음 it을 리턴하는데 무조건 해당 리턴된 값을 가지고 다음 반복을 시행해야 하기에 위에 처럼 순회해야 한다.

 

차이점

vector와 deque는 메모리 할당에서 차이를 보인다.

 

vector의 메모리 할당

벡터에서는 위의 그림과 같이 size외에 capacity라는게 존재한다. 컴파일러 마다 다르지만 보통 이전 메모리크기의 1/2이 추가로 capacity에 붙은 메모리를 재할당하고 이전의 원소를 복사한다. 하지만 C++11 부터 MoveSementics의 도입으로 인해 객체들을 복사하는 비용을 현저히 줄였다. 

 

반면 deque는 다르다.

deque 메모리 할당

위와 같이 deque는 여러개의 메모리 청크를 가지고 있으며 만약 해당 청크가 꽉차면 다음 메모리 청크에 삽입한다. 그리고 청크들은 map을 통해 관리한다. vector와 다르게 복사하고 재할당하는 과정이 없어서 효율적이다.

 

또한 vector는 구조상 front에 push하고 pop하는 연산이 복잡한데 비하여 deque는 간단히 할 수 있다. Insert시에도 해당 Insert하는 위치에서 가까운 쪽의 원소들을 선택하여 밀어낼수있다.  

 

vector는 deque에 비해 그나마 끝에 삽입, 삭제하는 속도가 더 빠르다고 하지만 지금 까지 종합해본 결과 확실히 deque가 vector의 상호 보완적으로 나온 느낌이 강한것 같다.