[C++] 직접 만들어보는 std::list 라이브러리

직접 만들어보는 std::list 라이브러리

선행

* 이 코드는 STL에 list를 모방한 것이다.

  Node, List, Iterator에 대한 개념이 필요하다.

[C++] STL - Standard Template Library

 

 

코드

#include <iostream>
#include <vector>
using namespace std;

template<typename T>
class Node {
public:
	Node() : _prev(nullptr), _next(nullptr), _data(T()) {

	}
	Node(const T& value) : _prev(nullptr), _next(nullptr), _data(value) {
		
	}

	// Node안에 다른 Node를 가리키는 포인터가 존재
	Node* _prev;
	Node* _next;
	T _data;
};

template<typename T>
class Iterator {
public:
	Iterator() : _node(nullptr) { }
	Iterator(Node<T>* node) : _node(node) { }

	// 전위 증가
	Iterator& operator++() {
		_node = _node->_next;
		return *this;
	}
	// 후위 증가
	Iterator operator++(int) {
		Iterator<T> temp = *this;
		_node = _node->_next;
		return temp;
	}
	// 전위 감소
	Iterator& operator--() {
		_node = _node->_prev;
		return *this;
	}
	// 후위 감소
	Iterator operator--(int) {
		Iterator<T> temp = *this;
		_node = _node->_prev;
		return temp;
	}

	T& operator*() { return _node->_data; }

	bool operator==(const Iterator& other) { return _node == other._node; }

	bool operator!=(const Iterator& other) { return _node != other._node; }


public:
	Node<T>* _node;
};

template<typename T>
class List {
public:
	List() : _size(0) {
		// 유효한 Node가 없을 때, 
		// _head와 _tail이 nullptr을 가리키면
		// 매번 null 체크를 해주어야한다.
		// 차라리 빈 Node를 만들어주자
		_head = new Node<T>();
		_tail = new Node<T>();
		_head->_next = _tail;
		_tail->_prev = _head;
	}

	~List() {
		while (_size > 0) {
			pop_back();
		}
		delete _head;
		delete _tail;
	}

	void push_back(const T& value) { addNode(_tail, value); }

	void pop_back() { removeNode(_tail->_prev); }

private:
	// [head] <-> ... <-> [before] <-> ... <-> [end]
	// [head] <-> ... <-> [new Node] <-> [before] <-> ... <-> [end]
	Node<T>* addNode(Node<T>* before, const T& value) {
		Node<T>* newNode = new Node<T>(value);
		Node<T>* prevNode = before->_prev;

		prevNode->_next = newNode;
		before->_prev = newNode;
		newNode->_next = before;
		newNode->_prev = prevNode;
		_size++;
		return newNode;
	}

	// [head] <-> ... <-> [node] <-> ... <-> [end]
	// [head] <-> ... <-> ... <-> [end]
	Node<T>* removeNode(Node<T>* node) {
		Node<T>* prevNode = node->_prev;
		Node<T>* nextNode = node->_next;

		prevNode->_next = nextNode;
		nextNode->_prev = prevNode;
		delete node;
		_size--;
		return nextNode;
	}

	int size() { return _size; }

public:
	using iterator = Iterator<T>;
	Iterator<T> begin() { return Iterator<T> (_head->_next); }
	Iterator<T> end() { return Iterator<T> (_tail); }

	Iterator<T> insert(Iterator<T> it, const T& value) {
		Node<T>* node = addNode(it._node, value);
		return Iterator<T> (node);
	}

	Iterator<T> erase(Iterator<T> it) {
		Node<T>* node = removeNode(it._node);
		return Iterator<T> (node);
	}

private:
	Node<T>* _head;
	Node<T>* _tail;
	int _size;
};

int main(){
	List<int> li;

	for (int i = 0; i < 10; i++) {
		li.push_back(i);
	}

	List<int>::iterator it = li.begin();
	for (; it != li.end(); it++) {
		cout << *it << endl;
	}
}

* Node, Iterator, List 클래스를 구현하였다.

 

* 전위 연산자와 후위 연산자 오버로딩의 차이는

  매개변수에 int 유무이다.

 

* Iterator 템플릿 별칭 사용을 위해 using 키워드를 사용

 

 

 

 

 

 

 

 

 

 

귀여운 그림은 낡은 창고님이 그리셨습니다.