[C++] list iterator, inline

아래 링크 클릭 시 해당 본문으로 이동

list iterator

• 전체 코드

inline

---

list iterator

• 연결 리스트(std::list)에서 요소를 순회(탐색)하거나 삽입/삭제할 때 사용하는 iterator이다.

list iterator 특징

• 포인터처럼 동작한다.

리스트의 요소를 가리키고 `*` 연산자로 값을 가져올 수 있다.

• 양방향으로 이동이 가능하다.

`++`는 다음 요소로, `--`는 이전 요소로 이동할 수 있다.

• 리스트 요소를 삭제하면 해당 요소를 가리키는 iterator는 더 이상 유효하지 않으므로, 삭제 후 반드시 다시 설정해야 한다.

`insert()`

벡터는 연속적인 메모리 구조이기 때문에 중간에 끼워 넣으려면 뒤에 데이터들이 하나씩 밀려나야 돼서 비효율적이다.

때문에 벡터에는 insert 기능이 없었다.

반면, 리스트는 노드 단위로 연결되어있고 넣고 싶은 데이터를 중간에 끼워 넣어도 데이터의 개수와 무관하게 항상 규칙적이고 동일한 동작을 취한다.

---

CList.h

#pragma once

#include <assert.h>

template<typename T>
struct tListNode
{
	T data;
	// 선언한 것의 내부에 있기 때문에 tListNode에 <T>를 적지 않아도 되지만, 명확성을 위해 적어주는 것이 좋다.
	tListNode<T>* pPrev;  // 이전 노드 주소
	tListNode<T>* pNext;  // 다음 노드 주소

	// 기본 생성자
	tListNode()
		: data()
		, pPrev(nullptr)
		, pNext(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>를 붙여줘야 한다.
	tListNode<T>* m_pHead; // 시작 노드 주소
	tListNode<T>* m_pTail;
	int m_iCount;  // 리스트 안에 있는 데이터 개수

public:
	void push_back(const T& _data);
	void push_front(const T& _data);
	int size() { return m_iCount; }  // 리스트 안의 데이터 개수

public:
	class iterator;
	iterator begin();
	iterator end();
	iterator erase(iterator& _iter);  // iterator가 가리키는 부분 제거
	iterator insert(const iterator& _iter, const T& _data);  // iterator가 지칭하는 부분의 왼쪽에 값이 삽입되고 iterator는 원래 가르키던 값을 가리킨다.
	// iterator가 가리키는 곳의 왼쪽에 노드를 새로 만들어서 값을 넣는다.

public:
	CList();
	~CList();

	class iterator
	{
	private:
		// 리스트에 데이터를 중간에 끼워넣고 싶을 때 넣을 위치의 노드 주소를 알면 된다.
		CList<T>* m_pList;  // 리스트 자체 주소
			// 리스트 내부라서 CList<T>를 CList라고 적어도 된다.
		tListNode<T>* m_pNode;  // 리스트 안에 넣어진 데이터들 중 현재 가리키고 있는 노드 자체 주소
			// null인 경우 end iterator로 간주한다.
		bool m_bValid;  // 유효성 체크

	public:
		// 가리키고 있는 대상으로 역참조해서 직접적으로 수정도 할 수 있기 때문에 반환 타입은 T&이다.
		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;

			return *this;
		}
		
		// ++ 후위
		iterator operator ++(int)
		{
			iterator copyiter(*this);

			++(*this);

			return copyiter;
		}

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

			m_pNode = m_pNode->pPrev;

			return *this;
		}

		// -- 후위
		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(_pList)
			, m_pNode(_pNode)
			, m_bValid(false)
		{
			// 예외 처리를 따지려면 복잡하지만 지금은 간단하게 작성했다.
			if (nullptr != _pList && nullptr != _pNode)
			{
				m_bValid = true;
			}
		}

		// 가리키던 역할이니까, 원본을 삭제하면 안 되므로 소멸자가(iterator가 없어질 때) 할 일은 없다.
		~iterator()
		{

		}

		friend class CList;
	};
};

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

	// 처음 입력된 데이터라면
	if (nullptr == m_pHead)
		// 헤드 포인터가 null이면 데이터가 처음이다.
	{
		m_pHead = pNewNode;
		m_pTail = pNewNode;
	}
	else
	{
		m_pTail->pNext = pNewNode;
		pNewNode->pPrev = m_pTail;

		// 리스트가 마지막 노드의 주소값을 새로 입력된 노드로 갱신한다.
		m_pTail = pNewNode;  // 현재 가장 마지막 노드를 생성시킨 노드로 갱신시킨다.
	}

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

template<typename T>
void CList<T>::push_front(const T& _data)
// 노드를 하나 생성시켜서 리스트가 생성시킨 노드를 헤드로 가리키고, 생성시킨 노드는 원래 헤드였던 노드를 가리킨다.
{
	// 생성시킨 노드는 이전이 존재하면 안 된다. => _pPrev는 null
	// 생성시킨 노드는 원래 헤드의 주소값을 가르켜야 한다. => _pNext는 m_pHead
		// 새로 생성된 노드의 다음을 현재 헤드 노드의 주소값으로 채운다.
	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>* pDeleteNode = m_pHead;  // 첫 번째 노드를 받아온다.

	while (pDeleteNode)
	{
		// 다음 노드의 다음 꺼를 기억해두고 지우는 것을 반복한다.
		tListNode<T>* pNext = pDeleteNode->pNext;  // 삭제할 노드(pDeleteNode)의 다음 노드(pNextNode)를 pNext에 넣는다.
		delete(pDeleteNode);  // 해당 메모리 해제
		pDeleteNode = pNext;  // 삭제할 노드를 다음 노드로 갱신시킨다.
	}
}

template<typename T>
inline typename CList<T>::iterator CList<T>::begin()
{
	// this => iterator가 리스트 자체를 알아야 된다.
		// this는 현재 begin() 함수를 호출한 CList이다.
	// m_pHead => 시작 노드를 알아야 한다.
	return iterator(this, m_pHead);
}
// iterator가 가리키고 있는 것이 없다면 end iterator로 보게 할 것이다.
// iterator가 가리키고 있는 노드 포인터(m_pNode)가 nullptr일 때 end iterator로 보면 된다.
// 데이터가 하나도 없을 때 begin()을 요청하면 end iterator가 반환되는 꼴이다.

// iterator에 ++을 했을 때
	// 다음 노드의 주소를 다시 m_pNode에 받아오면 iterator도 다음 노드를 알게 된다.
// 마지막 노드에서 iterator에 ++을 했을 때
	// 마지막 노드의 다음 노드 주소 파트가 nullptr라는 것을 m_pNode에 받으면 된다.
	// 마지막의 다음으로 가는 순간 자연스럽게 end iterator가 된다.
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)
// 추가 인자로 넣어줄 데이터도 T 타입으로 받아온다. (노드 안에 들어갈 실질적인 데이터)
{
	// 예외 처리
	// iterator가 end iterator면 안 되니까..
	if (end() == _iter)
	{
		assert(nullptr);
	}
	
	// 리스트에 추가되는 데이터를 저장할 노드 생성
	tListNode<T>* pNode = new tListNode<T>(_data, nullptr, nullptr);
		// 데이터 파트, 방금 추가됐기 때문에 왼쪽과 오른쪽은 nullptr로 받는다.

	// iterator가 가르키는 노드가 헤드 노드인 경우
	// 앞뒤로 끼어들게 없으니까 insert하면 헤드 노드가 뒤로 밀리고 앞쪽으로 삽입되어야 한다.
	if (_iter.m_pNode == m_pHead)
	{
		_iter.m_pNode->pPrev = pNode;  // 현재 헤드 노드의 Prev 파트가 새로운 노드가 된다.
		pNode->pNext = _iter.m_pNode;  // 해당 노드의 Next 파트는 현재 헤드 포인터에 연결해준다.
		m_pHead = pNode;  // 리스트가 삽입된 노드를 헤드 노드로 지정한다.
	}
	// iterator가 가르키는 노드가 헤드 노드가 아닌 경우
	else
	{
		// iterator가 가르키고 있는 노드의 Prev 부분 즉, 이전 노드의 Next는 새로 추가한 노드의 Prev와 양방향으로 연결
		// iterator가 가르키고 있는 노드의 Prev는 새로 추가한 노드의 Next 부분과 양방향으로 연결
		
		// iterator가 가르키고 있는 노드의 이전으로 가서 다음 노드 주소 파트를 새로 생성한 노드로 지정한다.
		_iter.m_pNode->pPrev->pNext = pNode;
		pNode->pPrev = _iter.m_pNode->pPrev;


		// iterator가 가리키고 있는 노드에 Prev 파트를 새로운 노드로 지정한다.

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

	// 카운트 증가
	++m_iCount;

	return iterator();
}

 

main.cpp

▷ 예시 1 (`*`으로 값 변경하기)

#include <iostream>
#include "CList.h"
#include <list>

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

int main()
{
	CList<int> mylist;

	mylist.push_back(100);
	mylist.push_back(200);
	mylist.push_back(300);

	CList<int>::iterator listiter = mylist.begin();
	//int l = *listiter;  // 100
	// 반환 타입이 T&이기 때문에 수정도 가능하다.
	*listiter = 150;  // 100 -> 150

	cout << "==================" << endl;
	cout << "list iterator test" << endl;
	cout << "==================" << endl;
	for (listiter = mylist.begin(); listiter != mylist.end(); ++listiter)
	{
		cout << *listiter << endl;
	}
    
	return 0;
}

▽ 출력 결과

==================
list iterator test
==================
150
200
300

 

▷ 예시 2 (직접 구현한 리스트가 아닌 실제 리스트의 insert의 반환 타입이 iterator인지 확인)

#include <iostream>
#include "CList.h"
#include <list>

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

int main()
{
	list<int> intlist;

	intlist.push_back(100);
	intlist.push_back(300);

	// iterator를 만들고 begin을 가리키게 한다.
	list<int>::iterator it = intlist.begin();

	// 200 끼워넣기
		// insert를 하면 지칭하는 값의 왼쪽에 삽입되기 때문에 300을 가리키고 넣어줘야 한다.
	it = intlist.insert(++it, 200);
	// 반환된 iterator는 방금 추가한 200을 가리킨다.

	// 헤드 노드의 앞에 50 넣기
	it = intlist.begin();
	it = intlist.insert(it, 50);

	for (it = intlist.begin(); it != intlist.end(); ++it)
	{
		cout << *it << endl;
	}

	return 0;
}

▽ 출력 결과

50
100
200
300

---

※ 주의!

분명 코드에 문제가 없는 것 같은데 실행하면 오류가 발생할 때, 생성자와 소멸자 부분 체크하기

본인의 경우 소멸자 부분에 아무것도 작성하지 않더라도 정의를 했어야 했는데 `;`으로 마감 지어놓고 어디가 문제인지 몇 분 동안 찾았다..

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

		}

		iterator(CList<T>* _pList, tListNode<T>* _pNode)
			: m_pList(_pList)
			, m_pNode(_pNode)
			, m_bValid(false)
		{
			// 예외 처리를 따지려면 복잡하지만 지금은 간단하게 작성했다.
			if (nullptr != _pList && nullptr != _pNode)
			{
				m_bValid = true;
			}
		}

		~iterator();  // 문제의 소멸자 부분!!

		friend class CList;

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

		}

		iterator(CList<T>* _pList, tListNode<T>* _pNode)
			: m_pList(_pList)
			, m_pNode(_pNode)
			, m_bValid(false)
		{
			// 예외 처리를 따지려면 복잡하지만 지금은 간단하게 작성했다.
			if (nullptr != _pList && nullptr != _pNode)
			{
				m_bValid = true;
			}
		}

		~iterator()
        {
        	// 아무것도 작성하지 않더라도 정의는 해놓기
        }

		friend class CList;

---

inline

• 구현한 함수에 대해 컴파일러가 판단해서 최적화시킨다.

최적화란?

• 함수 호출 오버헤드를 줄이기 위해 함수 호출 시점에서 함수 호출을 함수의 실제 코드로 대체하도록 컴파일러에게 요청한다.

함수 호출하고 종료하면 스택이 할당되고 해제되는 것은 전부 비용에 해당한다.

컴파일러에게 함수 호출 위치에 기능을 그대로 붙여넣어서 함수 호출 비용이 생기지 않게 요청한다.

• 클래스를 헤더에 구현하는 경우 컴파일러는 inline 처리하겠다는 것으로 받아들인다.

컴파일러가 inline 처리하는 경우

• 코드 내용이 짧지만 자주 호출되는 경우

ex) begin(), end(), 값 반환하는 함수(T* data() {return m_pData;}), get(), set() 등

그 외 함수들은 cpp에 구현해서 통상적인 함수의 호출 방식을 따른다.

컴파일러가 inline 처리하지 않는 경우

• 함수가 너무 큰 경우, 또는 반복문이나 재귀처럼 복잡한 구조를 포함하고 있는 경우

호출하는 곳에 코드를 적는 식이므로 내용이 긴 함수를 자주 호출할 때 inline 처리를 하는 것은 비효율적이다.

그렇게 되면 최종 빌드되는 코드의 양도 너무 많아진다.

따라서 inline 처리를 했지만 컴파일러가 무조건 다 inline 처리해주지는 않는다.