[C++] vector 내부에 iterator 클래스 구현 (+ 연산자 오버로딩, 복사 생성자)

vector 내부에 iterator 클래스 만드는데, 클래스 템플릿이기 때문에 내부에 있는 iterator도 템플릿이 된다.

iterator는 데이터의 시작 주소와 가리키고 있는 데이터가 시작 주소로부터 몇 번째인지 알아야 한다.

즉, iterator는 데이터의 시작 주소와 인덱스(시작 주소로부터 몇 칸 떨어져 있는지)만 알면 된다.

  ex) 3번째를 가리키는 경우, 시작 주소와 인덱스 2의 주소만 알면 된다.

또한 자료형도 알아야 하는데, 템플릿이기 때문에 데이터의 시작 주소 타입은 `T*`이다.

 

▷ 코드

CArr.h

#pragma once

#include <assert.h>

// 클래스 템플릿
template<typename T>
// T는 가변 배열에 저장될 데이터 타입이다.
class CArr  // CArr로 vector를 만들어도 CArr과 iterator 클래스는 별개의 자료형이기 때문에 이 클래스 크기는 총 16byte 자료형이다.
// 객체는 `CArr::iterator`로 만들면 된다.
{
private:
	T* m_pData;  // 8byte (64bit이기 때문에)  // 일단 템플릿 부분을 지우거나 주석 처리 후 <Ctrl + R + R>로 전체적으로 해당 이름을 바꾸자.
	int m_iCount;  // 현재 들어와있는 데이터 개수
	int m_iMaxCount;  // 최대 개수

public:
	void push_back(const T& _Data);  // 데이터 추가

	void resize(int _iResizeCount);  // 재할당 => 몇 칸으로 늘릴 것인지를 _iResizeCount로 받는다.
	// 데이터 타입과 무관한 가변 배열의 개수이기 때문에 int가 맞다.
	T* data() { return m_pData; }  // 시작 주소 반환
	int size() { return m_iCount; }  // 데이터 개수
	int capacity() { return m_iMaxCount; }  // 현재 기준으로 허용 범위
	T& operator[] (int idx);

	class iterator;
	iterator begin();  // (아래 쪽에 정의했다.)
	iterator end();  // (아래 쪽에 정의했다.)

public:
	CArr();  // 생성자
	~CArr();  // 소멸자

	// 이너 클래스를 포함하고 있는 클래스의 private 멤버에 접근 가능
	class iterator
	{
	private:
		// 그래서 벡터를 똑같이 구현하려면 아래와 같이 멤버들이 있어야 한다.
		CArr* m_pArr;  // iterator가 가리킬 데이터를 관리하는 가변 배열 주소
		T* m_pData;  // 데이터들의 시작 주소 => 이 역시 벡터가 알고 있다.
		int m_iIdx;  // 가리키는 데이터의 인덱스  // 만약 iterator가 다음이나 이전을 가리키라고 하면 인덱스를 ++이나 --시키면 된다.
	// 벡터 안에 데이터를 넣다가 꽉 채우게 되면 새로운 곳으로 메모리가 재할당된다.
	// iterator가 첫 번째 데이터를 가리키고 있는데 인덱스 0인 것이 의미가 없어질 수도 있다.
	// iterator가 첫 번째 데이터가 있는 줄 알고 접근하거나 iterator를 통해서 데이터를 덮어쓰려는 경우
		// 이미 삭제된 곳에 데이터를 쓰려고 할 것이다.
	// iterator 입장에서는 올바른건지 아닌지 알 수가 없다.
	// 새로 할당된 곳의 주소를 알려면 iterator는 벡터를 알아야 한다.
		// 벡터가 원래 꽉 찬 메모리와 새로 할당된 메모리의 주소도 갖고 있기 때문이다.
	// 공간이 다른 곳으로 바꼈는지는 벡터의 멤버와 iterator가 알고 있던 주소가 같은지 비교하면 알 수 있다.
	// 처음부터 CArr 객체 자체를 알고 있으면 된다.

	// 만약 iterator가 벡터의 인덱스 3을 항상 가리킨다는 것이 보장되어있다면 아무리 메모리 공간이 바껴도 상관이 없기 때문에 데이터의 시작 주소(T* m_pData;)가 필요가 없게 된다.
	// 그런데 iterator가 원래 주소랑 벡터가 관리하고 있는 주소가 다른 것을 따질거라면(문제로 삼을 거라면) iterator가 따로 관리해줘야 된다.
		// 내가 만들어보고 있는 벡터는 이렇지만 실제 벡터는 바로 윗줄을 문제로 삼고 있다.

	public:
		// ----- 역참조 operator ----- //
		T& operator * ()
		// 반환 타입이 그냥 T라면 수정할 수 없다.
		// T&여야 수정이 가능하다.
		{
			// 데이터의 시작 주소와 배열 쪽의 시작 주소가 같은지
				// 만약 같지 않다면 경고
			// 1. iterator가 알고 있는 주소와 가변 배열이 알고 있는 주소가 달라진 경우
				// 공간 확장으로 주소가 달라진 경우
			// 또는
			// 2. iterator가 end iterator인 경우
			if (m_pArr->m_pData != m_pData || -1 == m_iIdx)
			{
				assert(nullptr);
			}
			// 시작 주소(포인터)로부터 인덱스(위치)
			return m_pData[m_iIdx];  // 여기서 []는 operator가 아니라 기본 문법이다. (포인터 연산)
		}

		// 연달아서 ++을 할 수 있다.
            //int k = 0;
			//++(++k);  // k를 하나 증가시키고 또 하나를 증가시킨다.
        	// 이 부분 생각하면서 전위 연산자 구현하기
		// ----- 전위 연산자 ----- //
		iterator& operator ++()  // 반환 타입이 iterator 본인이여야 증가시킨 iterator 본인을 다시 증가시키는 등의 작업을 할 수 있다.
		{
		// 예외 처리
			// 2. end iterator인 경우
				// 이 경우 더 이상 증가할 수 없다.		
			// 3. iterator가 알고 있는 주소와 가변 배열이 알고 있는 주소가 달라진 경우
				// 공간 확장으로 주소가 달라진 경우
			if (m_pArr->m_pData != m_pData || -1 == m_iIdx)
			{
				assert(nullptr);
			}

			// 1. iterator가 마지막 데이터를 가리키고 있는 경우
			// --> end iterator가 된다.
				// 예외 처리는 맞지만 오류가 발생하는 상황은 아니다.
			// 어떻게 작성해야 될지 모를 때 iterator의 멤버 확인해보기
			// iterator 클래스의 근본적인 역할 : 가변 배열(m_pArr)이 관리하고 있는 데이터들을 가리킨다.
			if (m_pArr->size() - 1 == m_iIdx)
			{
				m_iIdx = -1;
			}
			else
			{
				++m_iIdx;
			}

			//++m_iIdx;  // 주소로부터 떨어져있는 곳을 지칭하는 인덱스를 증가시킨다.
			return *this;
		}
		
		iterator& operator --()
		{
			if (m_pArr->m_pData != m_pData || -1 == m_iIdx)
			{
				assert(nullptr);
			}

			if (m_pArr->size() - 1 == m_iIdx)
			{
				m_iIdx = -1;
			}
			else
			{
				--m_iIdx;
			}

			return *this;
		}

		// ----- 후위 연산자 ----- //
			// 전위 연산자와 호출 시점은 동일하기 때문에 구현을 다르게 해줘야 한다.
			// 가장 마지막에 호출되기 때문에 호출된 후의 반환타입이 중요하다.
			// ※ 실제로 호출 시점은 가장 나중은 아니고 다른 멤버 함수처럼 해당 기호가 보이면 즉시 호출된다.
			// 전위 연산자처럼 본인을 반환시키면(iterator&) 다음 대상을 가리키게 증가해버린다.
				// 때문에 절대 후위 연산자처럼 동작할 수 없다.
			// 래퍼런스가 아니라 ***복사본***을 줘야 한다.
				// 참조가 아니라 또 다른 복사본이기 때문에 반환 타입은 사라진다.
		iterator operator ++(int)  // 인자로 적은 int는 아무 의미가 없고 받아올 변수명도 적을 필요 없다.
		// int를 기반으로 컴파일러는 해당 함수를 후위 연산자로 인식한다.
		// 일종의 fake를 준 것이다.
		{
			// 복사 생성자가 호출된다.
			iterator copy_iter = *this;  // 지역 변수로 iterator를 만든다.
			// 지역 변수로 만들어진 iterator인 copy_iter는 후위 연산자를 호출한 객체와 값이 똑같아진다.

			// 구현한 전위 연산자 활용
			++(*this);  // 후위 연산자를 호출시킨 객체는 다음 요소를 가리킨다.

			return copy_iter;  // 다음 대상으로 증가하지 않은 객체를 반환한다.
								// 증가하기 이전에 복사받은 것을 반환한다.
		}

		iterator operator --(int) 
		{
			iterator copy_iter = *this;

			--(*this);

			return copy_iter;
		}
		
        // ----- 비교 연산자 ==, != ----- //
			// 반환 타입이 true 또는 false이기 때문에 bool 타입
		bool operator ==(const iterator& _otheriter)
		{
			if (m_pData == _otheriter.m_pData && m_iIdx == _otheriter.m_iIdx)
			{
				return true;
			}

			return false;
		}

		bool operator !=(const iterator& _otheriter)
		{
			return !(*this == _otheriter);
		}

	public:
		// 생성자
		iterator()
			: m_pArr(nullptr)
			, m_pData(nullptr)
			, m_iIdx(-1)  // 아무것도 가리키지 않는다는 의미로 -1을 사용했다.
		{

		}

		// 생성자 오버로딩
		iterator(CArr* _pArr, T* _pData, int _iIdx)
			: m_pArr(_pArr)
			, m_pData(_pData)
			, m_iIdx(_iIdx)
		{

		}

		// 소멸자
		~iterator()
		{

		}
	};

};

// 생성자
template<typename T>
CArr<T>::CArr()  // CArr 클래스의 T 버전 안에 구현되어있는 생성자를 지칭한다.
	: m_pData(nullptr)
	, m_iCount(0)
	, m_iMaxCount(2)
{
	m_pData = new T[2];
}

// 소멸자
template<typename T>
CArr<T>::~CArr()
{
	delete[] m_pData;
}

template<typename T>
void CArr<T>::push_back(const T& _Data)
{
	int i = 0;

	if (m_iMaxCount <= m_iCount)
	{
		// 재할당
		resize(m_iMaxCount * 2);
	}

	// 데이터 추가
	m_pData[m_iCount++] = _Data;
}

template<typename T>
void CArr<T>::resize(int _iResizeCount)
{
	if (m_iMaxCount >= _iResizeCount)
	{
		assert(nullptr);
	}

	// 1. resize시킬 개수만큼 동적 할당한다.
	T* pNew = new T[_iResizeCount];

	// 2. 기존 공간에 있던 데이터들을 새로 할당한 공간으로 복사시킨다.
	for (int i = 0; i < m_iCount; ++i)
	{
		pNew[i] = m_pData[i];
	}

	// 3. 기존 공간은 메모리 해제
	delete[] m_pData;

	// 4. 배열이 새로 할당된 공간을 가리키게 한다.
	m_pData = pNew;

	// 5. iMaxCount 변경점 적용
	m_iMaxCount = _iResizeCount;
}

template<typename T>
T& CArr<T>::operator[](int idx)
{
	// m_pInt가 가리키고 있는 인덱스 첫 번째 데이터를 반환한다.
	return m_pData[idx];
}

template<typename T>
typename CArr<T>::iterator CArr<T>::begin()
{
	// 벡터 안에 데이터를 한 번도 넣은 적이 없다면?
	// 시작(begin())이 곧 end()이다.
	// 지칭하고 있는 주소(m_pData)로부터 인덱스 값이 -1(내 맘대로 정함.)이면 iterator를 end iterator 상태로 볼 것이다.
	if (0 == m_iCount)
		return iterator(this, m_pData, -1);
		// 데이터가 없는 경우
			// begin() == end()
	else
		return iterator(this, m_pData, 0);
}

template<typename T>
typename CArr<T>::iterator CArr<T>::end()
{
	// 끝의 다음을 가리키는 iterator를 만들어서 반환해준다.
	return iterator(this, m_pData, -1);
}

 

main.cpp

#include <iostream>

#include "CArr.h"

#include <vector>
#include <list>

using std::cout;
using std::endl;

using std::vector;
using std::list;

class CTest
{
// 임시로 private에서 public으로 변경했다.
//private:
public:
	int m_i;

public:
	CTest& operator =(const CTest& _other)
	{
		m_i = _other.m_i;
		return *this;
	}

public:
	// 기본 생성자
	CTest()
		: m_i(0)
	{

	}

	// 복사 생성자
		// 직접 만들어주지 않아도 자동으로 만들어진다.
		// 생성자이니까 반환 타입 없고 클래스명이랑 동일하다.
		// 이니셜라이저로 초기화 문법도 사용할 수 있다.
	CTest(const CTest& _other)
		: m_i(_other.m_i)  // 복사의 원형(_other)이 되는 것을 받아와서 그 값을 초기값으로 사용한다.
	{

	}
};

int main()
{
	// 내가 만든 vector
	CArr<int> myvector;

	myvector.push_back(10);
	myvector.push_back(20);
	myvector.push_back(30);

	CArr<int>::iterator myiter = myvector.begin();
	
	// ++, -- (전위, 후위), --, ==, !=
	for (; myiter != myvector.end(); ++myiter)
	{
		cout << *myiter << endl;
	}

	myiter = myvector.begin();

	//int iData = *(++myiter);  // 20
	int iData = *(myiter++);  // 10이 나온 다음에 myiter가 20으로 증가한다.
		// 실제로 ++는 전위 연산자처럼 먼저 호출된다.
		// myiter는 다음 요소를 이미 가리키고 있다.
			// ++(*this);로 전위 연산자를 호출시켰기 때문이다.
		// 후위 연산자 함수가 종료되고 리턴된 것은 증가하기 이전 상태의 복사본이다.

	// 특별한 이유가 아니라면 후위보단 전위 연산자를 이용하기
		// 후위 연산자 => 쓸데없는 객체 생성 및 삭제 비용이 발생한다.
			// 지역 변수 객체 만든다. => 복사 (생성 1) -> 이를 리턴한다.
				// 원본(copy_iter)을 지역 변수로 받는다.
			// 반환 타입이 래퍼런스가 아닌 일반 타입이기 때문에 copy_iter는 함수가 종료되면 삭제된다. (삭제 1)
				// 반환 타입으로써 존재하는 전달자 객체가 또 만들어진다. (생성 2)
				// copy_iter를 다시 전달해주는 전달용 객체가 myiter로 돌려준다.
				// 이 객체도 결국은 사라진다. (삭제 2)
		// 즉, 무의미한 객체 생성 및 삭제가 각각 2번씩 발생하여 비효율적이다.

	// <기본 생성자 만들기 전> 복사 생성자를 만들었는데 아래에서 오류가 발생한 이유? (면접 단골 질문)
	//CTest t1, t2;
	//t1 = t2;
	// 복사 생성자는 어차피 자동으로 구현되는데 직접 구현했다.
	// 이는 생성자 오버로딩이므로 생성자가 한 종류라도 생긴 것이다.
	// 그럼 컴파일러는 기본 생성자를 만들어주지 않는다.
	// 즉, 생성자를 하나라도 만들면 C++ 컴파일러는 기본 생성자를 만들어주지 않는다.
	// 위의 t1, t2의 경우 아무것도 적지 않았기 때문에 기본 생성자를 호출하는데 컴파일러가기본 생성자를 만들어주지 않았기 때문에 오류가 발생한 것이다.
	// 때문에 문제가 발생하지 않게 하려면 기본 생성자도 직접 만들어야 한다.

	// 그럼 다른 생성자를 만들고 기본 생성자를 만들지 않았어도 기본 생성자를 만들어주면 되는거 아닌가?
		// 나중에 기본 생성자를 만들고 싶지 않은 경우도 있다. (기본 생성자를 호출하고 싶지 않은 경우)

	// t2 객체를 만들 때 t1을 기반으로 만들고 싶다.
	// 객체 생성하면 기본 생성자로 t2.m_i에 0가 들어간다.
	// 다시 대입 연산자를 이용해서 t1에 있는 m_i값을 t2로 옮긴다.
	// 즉, 2번 나눠서 작업하는 꼴이다.
	CTest t1;
	t1.m_i = 100;
	
	//CTest t2;
	//t2 = t1;
	// 이럴 때 복사 생성자를 이용하면 된다.
	CTest t2(t1);  // t2 생성자를 호출하는데 t1 인자를 받는다.
	// **객체 생성과 대입을 동시에 한다.** (복사 생성자 => 면접 단골 내용)

	//CTest t3 = t1;
	// 겉으로는 대입 연산자를 호출한 것처럼 보인다.
	// 대입 연산자가 발생한다. => t3 객체가 이미 만들어질 때 기본 생성자를 호출했다.
	// t3 객체가 이미 만들어져있어야 대입을 받을 수 있다.
	// 객체가 만들어질 때 무조건 생성자가 호출된다.
	// CTest 객체인 t3가 만들어졌다는 것이 생성자가 호출됐다는 의미이다.
	// 그리고나서 t1을 t3에 대입한다.
	// 구문 자체는 객체를 생성하는 동시에 대입한다.
	// 즉, 복사 생성자로 한 번에 처리할 수 있다.
	// 객체 생성과 대입이 동시에 일어나므로 컴파일러가 알아서 복사 생성자로 바꿔준다.
	CTest t3(t1);

	return 0;