List 클래스 템플릿 (4)

기능 구현할떄 고려할것

• 처음으로 기능을 구현할때는 막막하지만 그걸 어떻게 접근할지 생각을 하고 흐름이 보이면 적는다.
• 주어진 항목의 리스트를 작성하고 코드를 짜면 좋다.(클래스 템플릿 (3)에서 의사코드)
• 업무 스타트 할떄 하는일들을 순차적으로 적어서하면 좋다.

erase함수 구현

template<typename T>
typename List<T>::iterator List<T>::erase(iterator _targetIter)
{
	assert(_targetIter.m_Owner == this);

	if (_targetIter.m_TargetNode == m_pHead)
	{
		m_pHead = _targetIter.m_TargetNode->pNext;

		if (m_pHead == nullptr)
		{
			m_pTail = nullptr;
		}
		else
		{
			m_pHead->pPrev = nullptr;
		}
	}
	else if (targetIter.m_TargetNode == m_pTail)
	{
		m_pTail = targetIter.m_TargetNode->pPrev;

		m_pTail->pNext = nullptr;
	}
	else
	{
		_targetIter.m_TargetNode->pPrev->pNext = _targetIter.m_TargetNode->pNext;

		_targetIter.m_TargetNode->pNext->pPrev = _targetIter.m_TargetNode->pPrev;
	}
	iterator nextiter(this, _targetIter.m_TargetNode->pNext);
	delete _targetIter.m_TargetNode;
    
	--m_CurCount;
    
	return nextiter();
}

• 실제 구현은 이런식으로 해야한다. 코드 분해

 assert(_tarfetIter.m_Owner == this);

• 예외사항을 처리한것으로 iterator 해당 리스트가 소유한 데이터를 가리키는 상태인지 확인

if(_targetIter.m_TargetNode == m_pHead)

• _targetIter 가 가리키고 잇는 노드(삭제할 노드)면 if문이 들어가게한다

m_pHead = _targetIter.m_TargetNode->pNext;

• 예외상항(삭제할 노드가 Head 인 경우)를 처리하고 두번쨰 노드를 새로운 헤드로 지정한다.

if(m_pHead == nullptr)
{
	m_pTail = nullptr;
}

• 리스트 안에 데이터가 1개였다면, (삭제할 노드가 처음이자 마지막 노드였다.)
  • 데이터가 1개였다면 Tail도 nullptr이다.

		else
		{
			m_pHead->pPrev = nullptr;
		}

• 새롭게 지정된 헤드노드의 이전을 nullptr 로 바꾼다(삭제될 노드를 가리키고 있기 떄문에)

	else if (targetIter.m_TargetNode == m_pTail)
	{
		m_pTail = targetIter.m_TargetNode->pPrev;	// 1

		m_pTail->pNext = nullptr;					// 2
	}

• 1번은 삭제할 노드의 이전을 새로운 Tail 로 지정
• 2번은 새로 지정된 Tail 노드의 Next 를 null 로 바꾼다.
• 데이터가 하나일떄 예외사항은 이미 위 if구문에서 이미 체크를 하고 넘어왔다.

	else
	{
		_targetIter.m_TargetNode->pPrev->pNext = _targetIter.m_TargetNode->pNext;// 1

		_targetIter.m_TargetNode->pNext->pPrev = _targetIter.m_TargetNode->pPrev;// 2
	}

• 삭제할 노드가 Head 도 아니고 Tail 도 아니다(중간이다.)
• 1번은 삭제할 노드 이전 노드의 Next 를 삭제할 노드 Next 로 교체한다.
• 2번은 삭제할 노드 다음 노드의 Prev 를 삭제할 노드 Prev 로 교체한다.

	iterator nextiter(this, _targetIter.m_TargetNode->pNext);

• 삭제된 노드의 다음을 가리키는 iterator을 만든다.

	delete _targetIter.m_TargetNode;

• _targetIter가 가리키고 있는 노드를 delete(동적할당 해제)

	--m_CurCount;

• 데이터 카운트 감소.

erase 테스트

	iter = CharList.begin();
    
	++iter;
	CharList.erase(iter);

• Warrior -> Thief -> Archer -> Wizzard인 상태에서 ++iter한거를 erase하는 상황
  
  • W->A->Wi로 정상작동한다.

	iter = CharList.begin();
    
    ++iter;
	++iter;
	++iter;
	CharList.erase(iter);

• ++로 맴버함수오버로딩되서 증감연산자처럼된 ++을 3번해서 iter는 마지막을 가리키는 상태이므로
  
  • W -> T -> A 로 정상작동한다.

	iter = CharList.begin();
    
	int size = CharList.size();
	for (int i = 0; i < size; ++i)
	{
		CharList.erase(CharList.begin());
	}

int size() { return m_CurCount; }

• 사이즈를 사용하기위해 size함수를 구현
• 사이즈의 크기만큼 for문을 돌아서 다 삭제한다.
  • 증발띠

	for (int i = 0; i < CharList.size(); ++i)

• for문 조건 체크에서 이렇게하는순간 돌면서 비교하는 값이 4로 고정된게 아니라 4-3-2-1로 계속줄어서 초기의 크기를 임시 지역변수에 담아서 썻다.

	iter = CharList.begin();
    
	iter = CharList.end();
	 
	--iter;

		assert(m_Owner && m_TargetNode);

• 이렇게 --전위연산 맴버오버로딩할떄 어서트 조건문을 저렇게 걸어버리면 예외처리가 되면 안되는데 예외처리가 되버린다.

		iterator& operator --()
		{
			assert(m_Owner /*&& m_TargetNode*/);
			assert(m_Owner->m_pHead != m_TargetNode); // iterator 가 begin 이다.

			if (nullptr == m_TargetNode)
			{
				m_TargetNode = m_Owner->m_pTail;
			}
			else
			{
				m_TargetNode = m_TargetNode->pPrev;
			}

			return *this;
		}

• 처음 assert에서 m_TargetNode이 end iterator 이면 nullptr이기 떄문에 뺴버린다.
• 두번쨰 assert는 iterator가 begin 일떄 --하면 안되니까 assert걸어 버린다.
• if문은 현재 iterator가 end상태일떄 -- 함수가 호출된 경우 마지막 노드를 가리키게 한다.
  • m_TargetNode를 m_Owner의 m_pTail값으로 바꾼다.
• else문은 현재 가리키고 잇는 노드의 이전 노드를 가리키게 한다.

강의코드

mian.cpp

#include <iostream>

#include <vector>
using std::vector;

#include <list>
using std::list;

#include "List.h"

struct CharInfo
{
	wchar_t szName[20];
	int		HP;
	int		MP;
	int		SP;

	int		MaxHP;
	int		MaxMP;
	int		MaxSP;

public:
	void SetInfo(const wchar_t* _strName, int _HP, int _MP, int _SP)
	{
		wcscpy_s(szName, _strName);
		HP = MaxHP = _HP;
		MP = MaxMP = _MP;
		SP = MaxSP = _SP;
	}

	CharInfo()
		: HP(0), MP(0), SP(0)
		, MaxHP(0), MaxMP(0), MaxSP(0)
	{}

	CharInfo(const wchar_t* _strName, int _HP, int _MP, int _SP)
		: HP(0), MP(0), SP(0)
		, MaxHP(0), MaxMP(0), MaxSP(0)
	{
		SetInfo(_strName, _HP, _MP, _SP);
	}

	~CharInfo()
	{}

};

List<CharInfo> charlist;
//list<CharInfo> stdcharlist;

int main()
{
	int a = 10;
	++(++(++a));

	//CharInfo(L"Warrior", 100, 30, 50) - 임시객체, 이름없는 지역변수
	charlist.push_back(CharInfo(L"Warrior", 100, 30, 50));
	charlist.push_back(CharInfo(L"Archer", 80, 50, 40));
	charlist.push_back(CharInfo(L"Wizzard", 50, 100, 20));

	List<CharInfo>::iterator listiter;

	listiter = charlist.begin();
	const CharInfo& info = *listiter;

	// 자기자신을 반환하게 만들었기 때문에, 다시 ++ 함수를 재 호출 가능
	++(++(++listiter));

	// 후위 연산자
	int i = 0;
	int i2 = ++i;

	List<CharInfo>::iterator listiter2;
	listiter = charlist.begin();
	listiter2 = listiter++;


	// insert 함수 테스트
	List<CharInfo> CharList;
	CharList.push_back(CharInfo(L"Warrior", 100, 30, 50));
	CharList.push_back(CharInfo(L"Archer", 80, 50, 40));
	CharList.push_back(CharInfo(L"Wizzard", 50, 100, 20));

	// Warrior 를 가리킴
	List<CharInfo>::iterator iter = CharList.begin();

	// Warrior 에 Theif 를 insert 함( 카운트 4, iter 는 Thief 를 가리킴)
	// iter = CharList.insert(iter, CharInfo(L"Thief", 60, 30, 100));

	// Archer 가리킴
	// 카운트 4, iter 는 Thief 를 가리킴, W -> T -> A -> Wi
	++iter;
	iter = CharList.insert(iter, CharInfo(L"Thief", 60, 30, 100));

	// erase 테스트
	// Warrior -> Thief -> Archer -> Wizzard
	iter = CharList.begin();

	/*int size = CharList.size();
	for (int i = 0; i < size; ++i)
	{
		CharList.erase(CharList.begin());
	}*/

	iter = CharList.end();
	--iter;
    
    return 0;
 }

List.h

#pragma once

#include <assert.h>

template<typename T>
struct Node
{
	T			Data;
	Node<T>* pNext;
	Node<T>* pPrev;

	Node()
		: Data()
		, pNext(nullptr)
		, pPrev(nullptr)
	{}

	Node(const T& _Data, Node<T>* _Next, Node<T>* _Prev)
		: Data(_Data)
		, pNext(_Next)
		, pPrev(_Prev)
	{}
};

template<typename T>
class List
{
private:
	Node<T>* m_pHead;
	Node<T>* m_pTail;
	int			m_CurCount;

public:
	void push_back(const T& _Data);
	void push_front(const T& _Data);
	int size() { return m_CurCount; }

	class iterator;

	iterator begin() { return iterator(this, m_pHead); }
	iterator end() { return iterator(this, nullptr); }


	// _targetIter 가 가리키는곳에 _Data 를 저장시키고, 새로 저장한 데이터를 가리키는 iterator 를 반환해준다.
	iterator insert(iterator _targetIter, const T& _Data);

	// _targetIter 가 가리키는 데이터를 삭제하고, 삭제한 다음을 가리키는 iterator 를 반환
	iterator erase(iterator _targetIter);


public:
	List()
		: m_pHead(nullptr)
		, m_pTail(nullptr)
		, m_CurCount(0)
	{}

	~List()
	{
		Node<T>* pNode = m_pHead;

		while (pNode)
		{
			Node<T>* pNext = pNode->pNext;
			delete pNode;
			pNode = pNext;
		}
	}

public:
	class iterator
	{
	private:
		List<T>* m_Owner;
		Node<T>* m_TargetNode;

	public:
		T& operator *()
		{
			// Owner(List) 가 설정되어있지 않으면, 정상적인 iterator 가 아니다.
			// Owner 가 설정되어 있어도, m_TargetNode 가 nullptr 이면 End Iterator 이기 때문에
			// 마지막의 다음을 가리키는 상태의 iterator 에게 * 로 접근기능을 쓰면 에러
			assert(m_Owner && m_TargetNode);
			return m_TargetNode->Data;
		}

		// 1. ++, -- 반환타입 문제
		// 2. ++, -- 후위연산자 문제
		iterator& operator ++()
		{
			// enditerator 에서 ++ 하는 경우
			assert(m_Owner && m_TargetNode);
			m_TargetNode = m_TargetNode->pNext;

			return *this;
		}

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

			++(*this);

			return copyiter;
		}

		iterator& operator --()
		{
			assert(m_Owner);
			assert(m_Owner->m_pHead != m_TargetNode); // iterator 가 begin 이다.

			if (nullptr == m_TargetNode)
			{
				// 현재 iterator 가 end 상태인데 -- 함수가 호출된 경우
				// 마지막 노드를 가리키게 한다.
				m_TargetNode = m_Owner->m_pTail;
			}
			else
			{
				// 현재 가리키고 있는 노드의 이전 노드를 가리키게 한다.
				m_TargetNode = m_TargetNode->pPrev;
			}

			return *this;
		}

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

			++(*this);

			return copyiter;
		}

		bool operator == (const iterator& _otheriter)
		{
			if (m_Owner == _otheriter.m_Owner && m_TargetNode == _otheriter.m_TargetNode)
				return true;
			else
				return false;
		}

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

	public:
		iterator()
			: m_Owner(nullptr)
			, m_TargetNode(nullptr)
		{}

		iterator(List<T>* _Owner, Node<T>* _TargetNode)
			: m_Owner(_Owner)
			, m_TargetNode(_TargetNode)
		{}

		~iterator()
		{}

		friend class List<T>;
	};
};

template<typename T>
void List<T>::push_back(const T& _Data)
{
	Node<T>* pNewNode = new Node<T>(_Data, nullptr, nullptr);

	if (0 == m_CurCount) //nullptr == m_pHead)
	{
		m_pHead = pNewNode;
		m_pTail = pNewNode;
	}
	else
	{
		m_pTail->pNext = pNewNode;
		pNewNode->pPrev = m_pTail;
		m_pTail = pNewNode;
	}

	++m_CurCount;
}

template<typename T>
inline void List<T>::push_front(const T& _Data)
{
	Node<T>* pNewNode = new Node<T>(_Data, m_pHead, nullptr);

	if (nullptr != m_pHead)
	{
		m_pHead->pPrev = pNewNode;
	}
	else
	{
		m_pTail = pNewNode;
	}

	m_pHead = pNewNode;
	++m_CurCount;
}


// 반환타입이 이너클래스인 경우 앞에 typename 을 붙여주어야 한다.
template<typename T>
typename List<T>::iterator List<T>::insert(iterator _targetIter, const T& _Data)
{
	// iterator 가 해당 리스트가 소유한 데이터를 가리키는 상태인지 확인
	assert(_targetIter.m_Owner == this);

	// insert 위치가 맨 처음이라면, push_front 로 처리한다.
	if (m_pHead == _targetIter.m_TargetNode)
	{
		// insert 위치를 맨 앞으로 지정했기 때문에 push_front 와 동일한 효과이다.
		push_front(_Data);

		// push_front 가 끝나고 나면 m_pHead 에 새로운 데이터를 저장하는 노드의 주소가 들어있다.
		return iterator(this, m_pHead);
	}
	else
	{
		// 1. 입력되는 데이터를 저장하는 노드를 만든다.
		// 2. 새로 생성된 노드가 _targetIter 가 가리키는 노드를 다음으로 가리킨다.
		// 3. 새로 생성된 노드가 _targetIter 가 가리키는 노드의 이전을, 이전으로 가리킨다.		
		Node<T>* pNewNode = new Node<T>(_Data, _targetIter.m_TargetNode, _targetIter.m_TargetNode->pPrev);

		// 4. _targetIter 의 이전 노드로 가서, 그 노드가 새로 생성된 노드를 Next 로 지정하게 한다.
		_targetIter.m_TargetNode->pPrev->pNext = pNewNode;

		// 5. _targetIter 가 가리키는 노드의 이전을 새로 생성된 노드로 지정한다.
		_targetIter.m_TargetNode->pPrev = pNewNode;

		// 6. 데이터 카운트 증가
		++m_CurCount;

		// 7. 새로운 노드를 가리키는 iterator 를 만들어서 반환
		return iterator(this, pNewNode);
	}
}

template<typename T>
typename List<T>::iterator List<T>::erase(iterator _targetIter)
{
	// iterator 가 해당 리스트가 소유한 데이터를 가리키는 상태인지 확인
	assert(_targetIter.m_Owner == this);


	// _targetIter 가 가리키고 있는 노드(삭제할 노드)		
	if (_targetIter.m_TargetNode == m_pHead)
	{
		// 예외상황(삭제할 노드가 Head 인 경우)
		// 두번째 노드를 새로운 헤드로 지정
		m_pHead = _targetIter.m_TargetNode->pNext;

		if (m_pHead == nullptr)
		{
			// 리스트안에 데이터가 1개였다면,(삭제할 노드가 처음이자 마지막 노드였다)
			m_pTail = nullptr;
		}
		else
		{
			// 새롭게 지정된 헤드노드의 이전을 nullptr 로 바꾼다(삭제될 노드를 가리키고 있기 때문에)
			m_pHead->pPrev = nullptr;
		}
	}
	else if (_targetIter.m_TargetNode == m_pTail)
	{
		// 삭제할 노드의 이전을 새로운 Tail 로 지정
		m_pTail = _targetIter.m_TargetNode->pPrev;

		// 새로 지정된 Tail 노드의 Next 를 null 로 바꿈
		m_pTail->pNext = nullptr;
	}

	// 삭제할 노드가 Head 도 아니고 Tail 도 아니다(중간이다)
	else
	{
		// 삭제할 노드 이전노드의 Next 를 삭제할 노드 Next 로 교체
		_targetIter.m_TargetNode->pPrev->pNext = _targetIter.m_TargetNode->pNext;

		// 삭제할 노드 다음 노드의 Prev 를 삭제할 노드 Prev 로 교체
		_targetIter.m_TargetNode->pNext->pPrev = _targetIter.m_TargetNode->pPrev;
	}

	// 삭제된 노드의 다음을 가리키는 iterator 를 만든다.
	iterator nextiter(this, _targetIter.m_TargetNode->pNext);

	// _targetIter 가 가리키고 있는 노드를 delete(동적할당 해제)
	delete _targetIter.m_TargetNode;

	// 데이터 카운트 감소
	--m_CurCount;

	return nextiter;
}

1차 24.01.03
2차 24.01.04
3차 24.01.05
4차 24.01.09
5차 24.01.10