[C++] list iterator

 

지난 시간까지 학습한 vector 이터레이터에 이어서 list에 사용할 이터레이터를 구현해본다.

 

#pragma once

template<typename T>
struct tListNode // C++쪽 기준으로는 구조체와 클래스는 거의 유사하다고 볼 수 있다.
				 // 노드도 클래스로 선언해도 상관없지만 여기서는
				 // 기능이 그렇게 많지 않을 때, 단순히 데이터를 묶어 놓고 그 데이터를 저장하는
				 // 정도의 목적만 있어서 그렇게 많은 기능을 지원하지 않을 때는 구조체 키워드를 써본다.
{
	T             data;
	tListNode<T>* pNext;
	tListNode<T>* pPrev;

	// C++에서는 구조체와 클래스가 똑같기 때문에 구조체도 생성자를 만들 수 있다.
	tListNode()                                                           // 인자값이 없는 경우 생성
		: data()
		, pNext(nullptr)
		, pPrev(nullptr)
	{
	}

	tListNode(const T& _data, tListNode<T>* _pPrev, tListNode<T>* _pNext) // 인자값을 넣은 경우 생성
		: data(_data)
		, pPrev(_pPrev)
		, pNext(_pNext)
	{

	}
};

template<typename T>
class CList
{
private:
	tListNode<T>* m_pHead;     // 포인터 타입으로 주소의 시작 경로를 알고 있는 변수가 필요하다.
	tListNode<T>* m_pTail;     // 양방향 리스트이므로 Tail 값을 알고 있는 변수가 필요하다.
	int           m_iCount;    // 데이터 개수를 카운팅할 변수가 필요하다.

public:
	void push_back(const T& _data);  // 타입 T값이 미정 상태이기 때문에, 복사 비용을 줄이기 위해
	void push_front(const T& _data); // 레퍼런스로 받아 원본 자체는 수정하지 않는 참조를 받아와서
									 // 우리쪽 노드 단위로 데이터를 받아 온 것을 관리한다.
	int size() { return m_iCount; }

public:
	class iterator;
	iterator begin();
	iterator end();
	iterator erase(iterator _iter);
	iterator insert(const iterator& _iter, const T& _data);
	
public:
	CList();
	~CList();

	class iterator
	{
	private:
		CList<T>* m_pList;  // 해당 노드가 어떤 리스트의 소유인지 알기 위해 
								// 리스트 그 자체를 받아온다

		tListNode<T>  m_pNode;  // 구체적으로 리스트 안에 넣어진 데이터 중
								// 내가 현재 가르키고 있는 데이터에 
								// 해당하는 그 노드 자체를 알고 있는다.
								// 만약 이 값이 null일 경우, end iterator로 간주한다.

		bool          m_bValid; // 해당 노드의 유효성을 체크한다


	public:
		T& operator* ()
		{
			return m_pNode->data;
		}

		bool operator ==(const iterator& _otheriter)
		{
			if(m_pList == _otheriter.m_pList && m_pNode == _otheriter.m_pNode)
			{
				return true;
			}

			return false;
		}

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

		iterator& operator ++()
		{
			// end에서 ++ 한 경우
			if (nullptr == m_pNode || !m_bValid)
			{
				assert(nullptr);
			}

			m_pNode = m_pNode->pNext;
		
		}

		iterator& operator ++(int)
		{
			iterator copyiter(*this);

			++(*this);

			return copyiter;
		}



	public:
		iterator()
			: m_pList(nullptr)
			, m_pNode(nullptr)
			, m_bValid(false)
		{}

		iterator(CList<T> _pList, tListNode<T>* _pNode)
			: m_pList(nullptr)
			, m_pNode(nullptr)
			, m_bValid(false)
		{
			if (nullptr != _pList && nullptr != _pNode)
			{
				m_bValid = true;
			}
		}

		~iterator()
		{

		}

		friend class CList;

	};
};

template<typename T>
void CList<T>::push_back(const T& _data)
{
	tListNode<T>* pNewNode = new tListNode<T>; (_data, nullptr, nullptr);

	// 처음 입력된 데이터라면 Head와 Tail을 자기 자신으로 채운다
	if (nullptr == m_pHead)
	{
		m_pHead = pNewNode;
		m_pTail = pNewNode;
	}

	else
	{
		// 데이터가 1개 이상에서 입력된 경우
		// 현재 가장 마지막 데이터(tail) 를 저장하고 있는 노드와
		// 새로 생성된 노드가 서로 가리키게 한다.
		m_pTail->pNext = pNewNode;
		pNewNode->pPrev = m_pTail;

		// List가 마지막 노드의 주소값을 새로 입력된 노드로 갱신한다.
		m_pTail = pNewNode;

	}

	// 데이터 개수 증가
	++m_iCount;

}

template<typename T>
void CList<T>::push_front(const T& _data)
{
	// 새로 생성된 노드의 다음을 현재 헤드노드의 주소값으로 채움
	tListNode<T>* pNewNode = new tListNode<T>(_data, nullptr, m_pHead);

	// 현재 헤드노드의 이전노드 주소값을 새로 생성된 노드의 주소로 채움
	m_pHead->pPrev = pNewNode;

	// 리스트가 새로 생성된 노드의 주소를 새로운 헤드주소로 갱신한다.
	m_pHead = pNewNode;

	// 데이터 개수 증가
	++m_iCount;

}


template<typename T>
CList<T>::CList()
	: m_pHead(nullptr)
	, m_pTail(nullptr)
	, m_iCount(0)
{

}

template<typename T>
CList<T>::~CList()
{
	tListNode<T>* pDeletNode = m_pHead;

	while (pDeletNode)
	{
		tListNode<T>* pNext = pDeletNode->pNext;
		delete(pDeletNode);
		pDeletNode = pNext;
	}
}

template<typename T>
inline CList<T>::~iterator()
{
}


template<typename T>
inline typename CList<T>::iterator CList<T>::begin()
{
	return iterator(this, m_pHead);
}

template<typename T>
inline typename CList<T>::iterator CList<T>::end()
{
	return iterator(this, nullptr);
}

template<typename T>
inline typename CList<T>::iterator CList<T>::insert(const iterator& _iter, const T& _data)
{
	if (end() == _iter)
	{
		assert(nullptr);
	}

	// 리스트에 추가되는 데이터를 저장 할 Node 생성
	tListNode<T>* pNode = new tListNode<T>(_data, nullptr, nullptr);

	if (_iter.m_pNode == m_pHead)
	{
		_iter.m_pNode->pPrev = pNode;
		pNode->pNext = _iter.m_pNode;

		m_pHead->pNode;
	}

	else
	{
		// iterator가 가리키고 있는 노드의 이전으로 가서
		// 다음 노드 주소 파트를 새로 생성한 노드로 지정
		_iter.m_pNode->pPrev->pNext = pNode;
		pNode->pPrev = _iter.m_pNode->pPrev;

		// iterator가 가리키고 있는 노드의 이전을 새로운 노드로 지정
		// 새로운 노드의 pNext를 iterator가 가리키고 있는 노드로 지정
		_iter.m_pNode->pPrev = pNode;
		pNode->pNext = _iter.m_pNode;
	}

	++m_iCount;

	return iterator(this, pNode); // 리스트를 알려주고, 생성된 노드 주소를 알려준다.
}