STL - list

 

리스트는 STL의 표준 시퀀스 컨테이너이다. 

선형적 자료구조이며, 노드기반으로 구현되어있다.(이중연결리스트로 구현되어있다)

 

list는 벡터와 사용법이 유사하다.

다만, 뒤에서 삽입삭제가 가능한 벡터와는 달리, 앞에서도 연산이 가능하다.

 

노드기반이기 때문에 배열기반의 컨테이너에 비해 탐색이 불리하고, 삽입과 삭제에 유리하다 (시간적으로)

 

list는 노드기반이기때문에 인덱스를 통한 임의접근이 불가능하다. 즉, list[3] 이런 접근이 불가능하다.

그러므로 이터레이터에 대해 +=과 같은 연산이 불가능하다. 

 

임의 접근 반복자

배열 기반 컨테이너들이 가지는 반복자

ex) ++, --, [], +=, -=

 

2. 양방향 반복자

노드 기반 컨테이너들이 가지는 반복자 

ex) ++, --

 

iter + 3 // 불가. 이건 iter[3]이나 마찬가지다.

 

iter += 3 // 불가. iter로부터 3번째원소를 가리키려는 의도지만, 불가능하다. 

iter = iter+3 이나 마찬가지기 때문에.

 

list의 반복자는 양방향 반복자이므로, 단항 연산자 ++ 이나 --를 이용한다. 

(물론 이 연산자들은 오버로딩되어 있는 연산자다)

 

++iter // 다음 원소를 가리킨다.

 

--iter // 이전 원소를 가리킨다

 

중간 삽입, 삭제

 

벡터는 중간에 원소가 삽입될 경우, 그 이후의 원소들을 한칸씩 뒤로 민다.

이때문에 end의 위치가 변하고, 캐싱해놓은 end의 위치가 무효화 될 수 있다.

 

하지만 리스트는 노드기반이기 때문에 중간에 삽입해도 원소들을 밀지 않고, 무효화가 일어나지 않는다.

 

하지만 중간 삭제의 경우, 해당 반복자에 해당하는 위치에 있는 원소를 삭제하면 

그 반복자는 삭제된 원소를 가리키고 있으므로 무효화가 일어날 수 있다. 

(반복자 위치에 있는 원소가 아닌 다른 원소를 삭제하면 일어나지 않는다.)

 

터지는 경우

 

listInt.erase(++iter);

for (; iter != iter_end; ++iter)

    cout << *iter << endl;

 

안터지는 경우 (다른 원소 삭제)

 

auto iter2 = iter;

listInt.erase(++iter2);

for (; iter != iter_end; ++iter)

    cout << *iter << endl;

 

안터지는 경우 (다음 원소로 갱신)

iter = listInt.erase(iter);

for (; iter != iter_end; ++iter)

    cout << *iter << endl;

 

정렬

리스트는 노드기반이기 때문에 알고리즘 헤더의 sort함수를 이용해 정렬 할 수 없다.

따라서 리스트는 멤버함수로 sort함수를 가지고 있다. 

 

list.sort(조건자); 

 

이런식으로 사용한다.

 

list.sort(less<int>());

list.reverse();

 

이런식으로 내림차순정렬을 할 수도 있다.

 

참고삼아 필자가 직접 구현한 리스트를 올려본다.

 

### 이중연결리스트로 구현한 리스트 (이터레이터 포함)

```cpp
#include "stdafx.h"

template<typename T>
class MyList
{

private:
	template<typename T>
	struct NODE
	{
		T m_data;
		NODE* m_tNxt;
		NODE* m_tBfr;

		NODE()
			:m_tNxt(nullptr), m_tBfr(nullptr){}

	};

private:
	template<typename T>
	class MyListIterator
	{
	private:
		NODE<T>* m_tCurr;
	public:
		MyListIterator(NODE<T>* _tHead = nullptr) { m_tCurr = _tHead; }
		friend MyList;

	public:

		T& operator* ()
		{	
			return m_tCurr->m_data;
		}

		MyListIterator<T>& operator++ ()
		{
			m_tCurr = m_tCurr->m_tNxt;
			return *this;
		}

		MyListIterator<T>& operator-- ()
		{
			m_tCurr = m_tCurr->m_tBfr;
			return *this;
		}

		MyListIterator<T> operator++ (int)
		{
			MyListIterator<T> tmp = *this;
			operator++();
			return tmp;
		}

		bool operator== (MyListIterator<T>& _iter)
		{
			return m_tCurr == _iter.m_tCurr;
		}
		bool operator!= (MyListIterator<T>& _iter)
		{
			return m_tCurr != _iter.m_tCurr;
		}

	};

public:
	typedef MyListIterator<T> iterator;
	iterator begin() { return iterator(m_tHead.m_tNxt); }
	iterator end() { return iterator(); }
	

public:
	~MyList() { Release(); }
public:
	void initalize()
	{
		m_tHead.m_tNxt = nullptr;

	};

	void Release()
	{
		//뭔가 있으면 지워라.
		while (0 == Is_Empty())
		{
			Remove(0);
		}
	}

public:

	void Insert(int _iPos, T _data)
	{

		NODE<T>* newNode = new NODE<T>;
		newNode->m_data = _data;

		NODE<T>* before = Get_Node(_iPos - 1);
		if (before)
			Insert_Next(before, newNode);
		else
			delete newNode;

	};

	void Insert(iterator _iter, T _data)
	{
		NODE<T>* newNode = new NODE<T>;
		newNode->m_data = _data;
		Insert_Next(_iter.m_tCurr, newNode);
	}

	iterator& remove(iterator _iter)
	{
		iterator tmp = ++_iter;
		Remove_Curr(*_iter);
		return tmp;
	}

	void Remove(int _iPos)
	{
		if (Is_Empty() || _iPos <= -1)
			return;

		NODE<T>* curr = Get_Node(_iPos);
		if (nullptr != curr)
		{
			Remove_Curr(curr);

		}

	};

	T Get_Data(int _iPos)
	{
		NODE<T>* node = Get_Node(_iPos);
		if (nullptr != node)
			return node->m_data;
		else
			return NULL;
	}

	bool Is_Empty()
	{
		return (nullptr == m_tHead.m_tNxt);
	};

	int Size()
	{
		NODE<T>* n = m_tHead.m_tNxt;
		int iCnt = 0;
		while (nullptr != n)
		{
			n = n->m_tNxt;
			++iCnt;
		}
		return iCnt;
	}

	void Dump_List()
	{
		NODE<T>* n = m_tHead.m_tNxt;

		while (nullptr != n)
		{
			cout << n->m_data << endl;
			n = n->m_tNxt;
		}
	}

private:
	NODE<T>* Get_Node(int _iPos)
	{
		NODE<T>* n = &m_tHead;
		int iCnt = -1;
		while (nullptr != n && iCnt < _iPos)
		{
			n = n->m_tNxt;
			++iCnt;
		}
		return n;
	}

	void Insert_Next(NODE<T>* _before, NODE<T>* _node)
	{
		if (nullptr != _node)
		{
			NODE<T>* originNxt = _before->m_tNxt;

			_before->m_tNxt = _node;

			if (nullptr != originNxt) originNxt->m_tBfr = _node;

			_node->m_tNxt = originNxt;
			_node->m_tBfr = _before;

		}
	}

	void Remove_Curr(NODE<T>* _curr)
	{
		if (nullptr != _curr)
		{
			NODE<T>* originNxt = _curr->m_tNxt;
			NODE<T>* originBfr = _curr->m_tBfr;

			originBfr->m_tNxt = originNxt;
			if(nullptr != originNxt) originNxt->m_tBfr = originBfr;

			delete _curr;
		}

	}

private:
	NODE<T> m_tHead;

};

void main()
{

	MyList<int> mylist;

	mylist.Insert(0, 0);
	mylist.Insert(1, 1);
	mylist.Insert(2, 2);
	

	MyList<int>::iterator iter_begin = mylist.begin();
	MyList<int>::iterator iter_end = mylist.end();
	cout << *(iter_begin++) << endl;
	cout << *iter_begin << endl;

	cout << "====================================================" << endl;
	iter_begin = mylist.begin();
	mylist.Insert(iter_begin, 999);

	for (;iter_begin != iter_end; ++iter_begin)
	{
		cout << *iter_begin << endl;
	}
	

	

	
	

}