[자료구조] vector with C++ (2)

<본 카테고리는 "코딩 테스트를 위한 자료 구조와 알고리즘 with C++을 기반으로 작성하였습니다>

---

std::vector 구현

 

　이제부터 vector를 간단하게 구현해 보겠다. 우리의 목적은 크기가 유동적으로 조절되는 배열을 만드는 것이고, 용량은 1.5배씩 늘리도록 하겠다.

 

#include <iostream>
using namespace std;

template<class T>
class vector
{
	T* _data = nullptr; // 데이터의 주소값
	int _size = 0; // 크기
	int _capacity = 0; // 용량

　먼저 벡터에 담을 데이터의 주솟값과, 크기, 용량 변수를 초기화해준다.

 

public:
	vector() { } // 기본 생성자

	~vector() // 소멸자
	{
		if (_data) // 소멸자가 실행될 때 벡터 내에 데이터가 존재하면
			delete[] _data; // 할당 해제
	}

　기본 생성자를 만들어주고(기본 생성자가 없으면 객체 배열 초기화할 때 문제가 생긴다), 소멸자를 통해 객체가 소멸될 때 데이터가 존재하는지 확인하고 할당을 해제하게 해 준다.

 

	void reserve(const int& capacity) // capacity만큼 용량을 늘려주는 것
	{
		if (_capacity > capacity) // 기존의 용량이 입력받은 용량보다 크다면
			return; // 따로 처리해줄 게 없음
		_capacity = move(capacity);

		T* newData = new T[_capacity]; // 넓힌 크기의 배열 초기화

		for (int i = 0; i < _size; ++i)
			newData[i] = move(_data[i]); // 새로운 공간에 데이터를 밀어 넣음

		if (_data) // 데이터가 남아 있다면
			delete[] _data; // 할당 해제

		_data = newData; // 주솟값만 가리키게 
	}

　다음은 벡터 구현에서 가장 중요한 공간을 넓히는 작업이다. 사용자가 이미 확보된 공간보다 작은 용량을 입력하면 따로 처리해 줄 게 없으므로 종료한다. 그렇지 않다면 벡터의 멤버 변수인 _capacity의 양을 capacity로 바꿔주고, 넓힌 공간을 갖는 새로운 배열을 생성한다.  

　그 후, 기존에 있었던 데이터(이하 D)를 새로운 배열(ND)로 모두 옮겨주고, N을 할당 해제를 해준다. 마지막으로, N이 가리키고 있던 위치를 ND로 바꿔주면 작업이 완료된다.

 

	void push_back(const T& value) // 맨 뒤의 위치에 값 대입
	{
		if (_size == _capacity) // 용량과 크기가 같을 때
		{
			int newCapacity = static_cast<int>(_capacity * 1.5); // 1.5배 늘린 용량

			if (newCapacity == _capacity) // 예외: 용량이 0과 1일 때
				newCapacity++;

			reserve(newCapacity); // 공간 넓히기
		}

		_data[_size++] = value; // 맨 뒷자리에 데이터를 넣고, 크기 증가
	}

	void pop_back() // 맨 뒤의 위치의 값 pop
	{
		_size > 0 ? _data[_size--] = NULL : 0;
		// 크기가 0보다 클 때만 마지막 값 없애고, 사이즈 줄이기
	}

　그리고 데이터를 push할 때 쓰는 push_back()과 pop할 때 쓰는 pop_back()이다. 데이터를 푸시할 때 앞선 게시글에서 용량과 크기가 같을 때 용량을 1.5배 늘려준다고 하였다. 따라서 늘린 용량 newCapacity을 기존 용량에 1.5를 곱해주고, 미리 작성한 reserve()함수를 통해 공간을 넓혀준다. 이때 증가하는 폭이 1.5를 곱한 후 소수점을 버리므로 cast를 해주어야 한다.

　용량 작업이 끝난 후에는 맨 뒷자리에 데이터를 넣고, size를 늘려주면 된다.

 

　데이터를 팝할 때는 삼항 연산자를 이용해 _size가 0보다 크면 맨 마지막 위치의 데이터를 NULL로 처리하고, size를 줄여주고, 아닌 경우에는 0으로 리턴하게 작성하면 된다.

 

코드 총 합본

#include <iostream>
using namespace std;

template<class T>
class vector
{
	T* _data = nullptr; 
	int _size = 0; 
	int _capacity = 0; 

public:
	vector() { } 

	~vector() 
	{
		if (_data) 
			delete[] _data; 
	}

	void reserve(const int& capacity)
	{
		if (_capacity > capacity) 
			return; 
		_capacity = move(capacity);

		T* newData = new T[_capacity]; 

		for (int i = 0; i < _size; ++i)
			newData[i] = move(_data[i]); 

		if (_data) 
			delete[] _data; 

		_data = newData; 
	}

	void push_back(const T& value) 
	{
		if (_size == _capacity) 
		{
			int newCapacity = static_cast<int>(_capacity * 1.5); 

			if (newCapacity == _capacity) 
				newCapacity++;

			reserve(newCapacity); 
		}

		_data[_size++] = value; 
	}

	void pop_back()
	{
		_size > 0 ? _data[_size--] = NULL : 0;
	}
};

　[] 연산자와 clear 등을 구현한 모든 코드는 여기에 myVector.cpp 파일을 참고하자. 굉장히 러프하게 작성하였으므로 이런 식으로 구현하는구나, 정도로 참고하면 될 것 같다.

---

std::vector 할당자

　std::vector는 템플릿 매개변수에서 데이터 타입 다음에 할당자를 전달할 수 있다. 여기서 할당자(allocator)란 일반적인 힙 메모리 대신 메모리 풀(메모리를 할당할 때 빈 공간이 생기지 않게 채워주는 것)을 사용하여 메모리를 관리하는 인터페이스, 쉽게 생각하면 new 연산자처럼 메모리를 할당하는 것을 추상화하여 컨테이너의 메모리를 관리하는 것이다. 기본적으로 사용자가 직접 선언해주지 않는다면 표준 allocator를 사용하고, 그렇지 않으면 사용자가 만든 allocator를 사용할 수 있다. 

 

　그렇다면 allocator는 언제 사용하는 것일까? 그전에 new / delete 연산자에 대해 알아보자. new 연산자와 delete 연산자는 메모리를 수동으로 다루기 위해, 즉 동적 할당을 위해 사용한다는 것은 익히 알고 있을 것이다. 

 

vcruntime_new.h.&nbsp;new는 operator new를 호출하고 있고, delete는 operator delete를 호출하고 있다.

 

　동적 할당을 할 때 사용되는 new와 delete 연산자는 반드시 기본 생성자가 필요하고, 모든 요소를 초기화하는 과정을 거치게 된다. 따라서 할당하는 요소가 많으면 많을수록 컴퓨터가 소모하는 자원량이 많아지므로 비효율적이다. 

　하지만 allocator를 이용하면 new 연산자와 달리 의무적으로 값을 초기화할 필요가 없으므로 오버헤드(overhead)가 줄어든다. 그리고, delete와 달리 메모리를 다시 할당할 필요 없이 객체들을 소멸시킬 수 있다.

　즉, 컨테이너를 이용해 메모리를 세밀하게 다뤄야 할 때 allocator를 사용한다고 보면 된다.

---

요약

allocator
1. 정의: 메모리를 관리하는 인터페이스
2. 특징
- 메모리를 세밀하게 다룰 때 사용됨