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

// list (연결 리스트)
// - list의 동작 원리
// - 중간 삽입/삭제
// - 처음/끝 삽입/삭제
// - 임의 접근

template<typename T>
class Node
{
public:
	Node() : _next(nullptr), _prev(nullptr), _data(T()) {}
	Node(const T& value) : _next(nullptr), _prev(nullptr), _data(value) {}
public:
	Node*	_next;
	Node*	_prev;
	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& right)
	{
		return _node == right._node;
	}

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

public:
	Node<T>* _node;
};

template<typename T>
class List
{
public:
	List() : _size(0)
	{
		_header = new Node<T>();
		_header->_next = _header;
		_header->_prev = _header;
	}

	~List()
	{
		while (_size > 0)
			pop_back();

		delete _header;
	}

	void push_back(const T& value)
	{
		AddNode(_header, value);
	}

	void pop_back()
	{
		RemoveNode(_header->_prev);
	}

	int size() const { return _size; }

private:
	Node<T>* AddNode(Node<T>* before, const T& value)
	{
		Node<T>* node = new Node<T>(value);

		Node<T>* prevNode = before->_prev;
		prevNode->_next = node;
		node->_prev = prevNode;

		node->_next = before;
		before->_prev = node;
		
		_size++;

		return node;
	}

	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;
	}

public:
	typedef Iterator<T> iterator;
	iterator begin() { return iterator(_header->_next); }
	iterator end() { return iterator(_header); }
	iterator insert(iterator it, const T& value)
	{
		Node<T>* node = AddNode(it._node, value);
		return iterator(node);
	}
	iterator erase(iterator it)
	{
		Node<T>* node = RemoveNode(it._node);
		return iterator(node);
	}


private:
	Node<T>* _header;
	int _size;
};

int main()
{
	List<int> li;
	List<int>::iterator eraseIt;

	for (int i = 0; i < 10; i++)
	{
		if (i == 5)
			eraseIt = li.insert(li.end(), i);
		else
			li.push_back(i);
	}

	li.pop_back();

	li.erase(eraseIt);

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

	return 0;
}

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

template<typename T>
class Iterator
{
public:
	Iterator() : _ptr(nullptr) {}
	Iterator(T* ptr) : _ptr(ptr) {}

	Iterator& operator++()
	{
		_ptr++;
		return *this;
	}

	Iterator operator++(int)
	{
		Iterator temp = *this;
		_ptr++;
		return temp;
	}

	Iterator& operator--()
	{
		_ptr--;
		return *this;
	}

	Iterator operator--(int)
	{
		Iterator temp = *this;
		_ptr--;
		return temp;
	}

	Iterator operator+(const int count)
	{
		Iterator temp = *this;
		temp._ptr += count;
		return temp;
	}

	Iterator operator-(const int count)
	{
		Iterator temp = *this;
		temp._ptr -= count;
		return temp;
	}

	bool operator==(const Iterator& right) { return _ptr == right._ptr;  }
	bool operator!=(const Iterator& right) { return _ptr != right._ptr;  }

	T& operator*() { return *_ptr; }

public:
	T* _ptr;
};

template<typename T>
class Vector
{
public:
	Vector() : _data(nullptr), _size(0), _capacity(0) {}
	~Vector()
	{
		if (_data != nullptr)
			delete[] _data;
	}

	void push_back(const T& val)
	{
		if (_size == _capacity)
		{
			int newCapacity = static_cast<int>(_capacity * 1.5f);
			if (newCapacity == _capacity) newCapacity++;

			reserve(newCapacity);
		}

		_data[_size] = val;
		_size++;
	}

	void reserve(const int capacity)
	{
		_capacity = capacity;
		T* newData = new T[_capacity];

		for (int i = 0; i < _size; i++)
			newData[i] = _data[i];

		if (_data != nullptr)
			delete[] _data;

		_data = newData;
	}

	T& operator[](const int pos)
	{
		return _data[pos];
	}

	int size() const { return _size; }
	int capacity() const { return _capacity; }

public:
	typedef Iterator<T> iterator;

	iterator begin() { return iterator(&_data[0]); }
	iterator end() { return begin() + _size; }

private:
	T* _data;
	int _size;
	int _capacity;
};

// vector (동적 배열)
// - vecotr의 동작 원리
// - 중간 삽입/삭제
// - 처음/끝 삽입/삭제
// - 임의 접근

int main()
{
	Vector<int> v;

	v.reserve(100);

	for (int i = 0; i < 100; i++)
	{
		v.push_back(i);
		cout << v.size() << " " << v.capacity() << endl;
	}

	for (int i = 0; i < v.size(); i++)
	{
		cout << v[i] << endl;
	}
	
	cout << "------------------" << endl;

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

	return 0;
}

clear를 구현하는 경우 데이터를 지울 필요 없이 그냥 size만 0으로 재설정 하면 된다.