Forwardlist 구현

• Forwardlist.h

#pragma once

#include <stddef.h>

class ForwardList
{
    // 연결 리스트에서 데이터를 저장하기 위한 타입
    // 즉, 연결 리스트는 데이터를 직접적으로 다루는 것이 아니라
    // Node라는 것으로 다룹니다.
    struct Node
    {
        Node(int data = 0, Node* next = nullptr);
        Node(const Node&) = delete;
        Node& operator=(const Node&) = delete;
        ~Node();

        int     Data = 0;       // 실제 데이터
        Node* Next = nullptr;   // 다음 원소
    };

public:
    // 데이터를 수정할 수 없는 반복자
    // const int*
    class const_iterator
    {
    public:
        const_iterator(Node* p = nullptr);
        ~const_iterator();

        const int& operator*() const;      // 역참조
        const int* operator->() const;     // 멤버 접근
        const_iterator& operator++();           // 전위 증가 연산자
        const_iterator      operator++(int);        // 후위 증가 연산자
        bool                operator==(const const_iterator& rhs) const;
        bool                operator!=(const const_iterator& rhs) const;
        bool                operator==(nullptr_t p) const;
        bool                operator!=(nullptr_t p) const;

    public:
        // 데이터 수정이 가능한 반복자
        // int*
        Node* _p = nullptr;
    };

    class iterator : public const_iterator
    {
    public:
        //using const_iterator::const_iterator;
        iterator(Node* p = nullptr);

        int& operator*() const;
        int* operator->() const;
        iterator& operator++();
        iterator        operator++(int);
    };

    // 기본 생성자
    ForwardList();

    // count만큼의 요소를 갖고 있는 컨테이너를 만드는 생성자
    explicit ForwardList(size_t count);

    // 복사 생성자.
    ForwardList(const ForwardList& other);

    // 할당 연산자
    ForwardList& operator=(const ForwardList& rhs);

    // 소멸자
    ~ForwardList();

    // 첫 번째 요소를 반환한다.
    int& front();
    const int& front() const;

    // 시작 전 요소를 가리키는 반복자를 반환한다.
    iterator            before_begin();
    const_iterator      before_begin() const;

    // 시작 요소를 가리키는 반복자를 반환한다.
    iterator            begin();
    const_iterator      begin() const;

    // 끝 다음 요소를 가리키는 반복자를 반환한다.
    iterator            end();
    const_iterator      end() const;

    // pos 다음에 value를 삽입한다.
    // 삽입된 요소를 가리키는 반복자를 반환한다.
    iterator            insert_after(const_iterator pos, int value);

    // pos 다음 요소를 삭제한다.
    // 삭제된 요소의 다음 요소를 가리키는 반복자를 반환한다.
    // 아무 요소도 없으면 end()를 반환한다.
    iterator            erase_after(const_iterator pos);

    // 시작 요소에 value를 삽입한다.
    void                push_front(int value);

    // 시작 요소를 제거한다.
    void                pop_front();

    // 컨테이너가 비었는지 판단한다.
    bool                empty() const;

    // 컨테이너를 비워버린다.
    void                clear();

    // value가 있는지 검사한다.
    bool                contains(int value) const;
private:
    // 더미 노드: 실제 데이터를 담지 않응. 오로지 구현의 편의성만을 위해서 존재
    Node* _head = new Node(); // before_begin()
    // 더미 노드
   // Node* _end = new Node(); // end() NULL 이 대체
};

• Forwardlist.cpp

#include "ForwardListNode.h"
#include <utility>

ForwardList::Node::Node(int data, Node* next)
	:Data(data), Next(next)
{

}

ForwardList::Node::~Node()
{
	Next = nullptr;
}

ForwardList::const_iterator::const_iterator(Node* p)
	:_p(p)
{

}

ForwardList::const_iterator::~const_iterator()
{
	_p = nullptr;
}

const int& ForwardList::const_iterator::operator*() const
{
	return _p->Data;
}

const int* ForwardList::const_iterator::operator->() const
{
	return &(_p->Data);
}

ForwardList::const_iterator&
	ForwardList::const_iterator::operator++()
{
	// ++p?
	_p = _p->Next;
	return *this;
}

ForwardList::const_iterator
	ForwardList::const_iterator::operator++(int)
{
	// p++
	// 1. p를 1 증가 시키고
	// 2. 이전 p를 반환
	const_iterator temp = *this;
	_p = _p->Next;
	return temp;
}

bool ForwardList::const_iterator::operator==(const const_iterator& rhs) const
{
	if (_p == rhs._p)
	{
		return true;
	}
	else
	{
		return false;
	}
}

bool ForwardList::const_iterator::operator!=(const const_iterator& rhs) const
{
	return !(*this == rhs); // 보통 같지 않다 구현할 떄 다 요렇게 함
}

bool ForwardList::const_iterator::operator==(nullptr_t p) const
{
	if (_p == nullptr)
	{
		return true;
	}
	else
	{
		return false;
	}
	// C++ 11 부터 나왔고, NULL의 모호함 때문에 나왔다.
	// NULL 정수로서의 0도 되고, 포인터로서의 NULL도 되기 때문에
}

bool ForwardList::const_iterator::operator!=(nullptr_t p) const
{
	return !(*this == nullptr);
}

ForwardList::iterator::iterator(Node* p)
	: const_iterator(p)
{

}

int& ForwardList::iterator::operator*() const
{
	return (int&)const_iterator::operator*();
}

int* ForwardList::iterator::operator->() const
{
	return (int*)const_iterator::operator->();
}

ForwardList::iterator&
	ForwardList::iterator::operator++()
{
	const_iterator::operator++();
	return *this;
}

ForwardList::iterator
ForwardList::iterator::operator++(int)
{
	iterator temp = *this;
	const_iterator::operator++();
	return temp;
}

ForwardList::ForwardList()
{
	// _head -> []
	// _end -> []
	// [] -> []
	//_head->Next = _end;

	//	begin() == end()
	//	_head->Next == nullptr
	//	_head = new node(0, nullptr);
}

ForwardList::ForwardList(size_t count)
	: ForwardList()
{
	for (size_t i = 0; i < count; i++)
	{
		push_front(0);
	}
}

ForwardList::ForwardList(const ForwardList& other)
	:ForwardList()
{
	iterator inserted = before_begin();
	for (const_iterator iter = other.begin(); iter != other.end(); ++iter)
	{
		inserted = insert_after(inserted, *iter);
	}
}

ForwardList& ForwardList::operator=(const ForwardList& rhs)
{
	if (&rhs != this)
	{
		ForwardList temp(rhs);
		std::swap(_head, temp._head);
	}
	return *this;
}

ForwardList::~ForwardList()
{
	clear();

	delete _head;
	_head = nullptr;
}

int& ForwardList::front()
{
	return *begin();
}

const int& ForwardList::front() const
{
	return *begin();
}

ForwardList::iterator ForwardList::before_begin()
{

	return _head;
}

ForwardList::const_iterator ForwardList::before_begin() const
{
	return _head;
}

ForwardList::iterator ForwardList::begin()
{
	return _head->Next;
}

ForwardList::const_iterator ForwardList::begin() const
{
	return _head->Next;
}

ForwardList::iterator ForwardList::end()
{
	return nullptr;
}

ForwardList::const_iterator ForwardList::end() const
{
	return nullptr;
}

ForwardList::iterator ForwardList::insert_after(const_iterator pos, int value)
{
	// [] -> [] -> [] -> []
	//       pos   Next
	//         value
	Node* newNode = new Node(value);
	Node* where = pos._p;

	newNode->Next = where->Next;
	where->Next = newNode;

	return newNode;

}

ForwardList::iterator ForwardList::erase_after(const_iterator pos)
{
	// [] -> [] -> [] -> [*]
	//       pos  removed  Next
	// 예외처리

	Node* where = pos._p;
	Node* removed = where->Next;

	where->Next = removed->Next;
	// [] -> [] -> [*]
	//		where
	// [] removed

	delete removed;

	return where->Next;
}

void ForwardList::push_front(int value)
{
	insert_after(before_begin(), value);
}

void ForwardList::pop_front()
{
	erase_after(before_begin());
}

bool ForwardList::empty() const
{
	if (_head->Next == nullptr) // if(begin() == nullptr)
	{
		return true;
	}
	else
	{
		return false;
	}
}

void ForwardList::clear()
{
	while (false == empty())
	{
		pop_front();
	}
}

bool ForwardList::contains(int value) const
{
	for (const_iterator iter = begin(); iter != end(); ++iter)
	{
		if (*iter == value)
		{
			return true;
		}
	}
	return false;
}

Main.cpp

#include <iostream>
#include "ForwardListNode.h"
#include <forward_list>
using namespace std;

int main()
{
	std::forward_list<int> flist;
	ForwardList mylist;

	flist.push_front(1); // [1]
	mylist.push_front(1); // [1]

	if (flist.front() == mylist.front())
	{
		std::cout << "같음";
	}

	forward_list<int>::iterator iter = flist.begin();
	ForwardList::iterator liter = mylist.begin();

	mylist.insert_after(mylist.begin(), 3); // [1] [] [3] 
	liter++;

	cout << *liter << "\\n";

	std::cout << "myflist 첫번째 값: " << mylist.front() << "\\n";

	mylist.clear();

	if (mylist.empty())
	{
		cout << "mylist는 비었음." << "\\n";
	}

	for (int i = 0; i < 10; i++)
	{
		mylist.push_front(i);
	}
	
	cout << "\\n" << "테스트: ";
	for (liter = mylist.begin(); liter != mylist.end(); ++liter)
	{
		cout << "[" <<  * liter << "]" << " ";
	}

	mylist.erase_after(mylist.begin());
	
}

List 구현하기

• List.h

#include <algorithm>

// int를 template<typename T> 로 바꾸면 댄다 템플릿 할라면

class List
{
public:
    struct Node
    {
        Node(int data = 0, Node* prev = nullptr, Node* next = nullptr);
        Node(const Node&) = delete;
        Node& operator=(const Node&) = delete;
        ~Node() = default;

        int     Data = 0;
        Node* Next = nullptr;
        Node* Prev = nullptr;
    };

public:
    class const_iterator
    {
    public:
        const_iterator(Node* p = nullptr);
        ~const_iterator();

        const int& operator*() const;
        const int* operator->() const;

        const_iterator& operator++();
        const_iterator      operator++(int);
        const_iterator& operator--();
        const_iterator      operator--(int);

        bool                operator==(const const_iterator& rhs) const;
        bool                operator!=(const const_iterator& rhs) const;
        bool                operator==(nullptr_t p) const;
        bool                operator!=(nullptr_t p) const;

    public:
        Node* _p = nullptr; // 데이터 수행이 가능한 반복자
    };

    class iterator : public const_iterator
    {
    public:
        using const_iterator::const_iterator;

        int&             operator*() const;
        int*             operator->() const;

        iterator&        operator++();
        iterator         operator++(int);
        iterator&        operator--();
        iterator         operator--(int);
    };

    // 기본 생성자
    List(); // = default;

    // count만큼의 요소를 갖고 있는 컨테이너를 만드는 생성자
    explicit List(size_t count);

    // 복사 생성자.
    List(const List& other);

    // 할당 연산자
    List& operator=(const List& rhs);

    // 소멸자
    ~List();

    // 첫 번째 요소를 반환한다.
    int& front();
    const int& front() const;

    // 마지막 요소를 반환한다.
    int& back();
    const int& back() const;

    // 시작 요소를 가리키는 반복자를 반환한다.
    // 리스트가 비어있다면 end()와 같다.
    iterator            begin();
    const_iterator      begin() const;

    // 끝 다음 요소를 가리키는 반복자를 반환한다.
    iterator            end();
    const_iterator      end() const;

    // pos 이전에 value를 삽입한다.
    // 삽입된 요소를 가리키는 반복자를 반환한다.
    iterator            insert(iterator pos, int value);

    // pos 를 삭제한다.
    // 삭제된 요소의 다음 요소를 가리키는 반복자를 반환한다.
    // 아무 요소도 없으면 end()를 반환한다.
    iterator            erase(iterator pos);

    // 시작에 value를 삽입한다.
    void            push_front(int value);

    // 끝에 value를 삽입한다.
    void            push_back(int value);

    // 시작 요소를 제거한다.
    void            pop_front();

    // 끝 요소를 제거한다.
    void            pop_back();

    // 컨테이너가 비었는지 판단한다.
    bool            empty() const;

    // 리스트 안에 있는 요소의 개수를 반환한다.
    size_t          size() const;

    // 컨테이너를 비워버린다.
    void            clear();

    // 해당 value가 있는지 체크한다.
    bool            contains(int value) const;
private:
    Node*  _end      = new Node();    // 더미 노드; end()
    //Node*  _begin     = _end;         // 헷갈리면 _head를 begin으로 바꿔도 된다.
    size_t _size     = 0;
};

• List.cpp

#include "List.h"
using namespace std;

List::Node::Node(int data, Node* prev, Node* next)
	: Data(data), Prev(prev), Next(next)
{

}

List::const_iterator::const_iterator(Node* p)
	: _p(p)
{

}

List::const_iterator::~const_iterator()
{
	_p = nullptr;
}

const int& List::const_iterator::operator*() const
{
	return _p->Data;
}

const int* List::const_iterator::operator->() const
{
	return &(_p->Data);
}

List::const_iterator& List::const_iterator::operator++()
{
	_p = _p->Next;
	return *this;
}

List::const_iterator List::const_iterator::operator++(int)
{
	iterator temp = _p;
	_p = _p->Next;

	return temp;
}

List::const_iterator& List::const_iterator::operator--()
{
	_p = _p->Prev;
	return *this;
}

List::const_iterator List::const_iterator::operator--(int)
{
	iterator temp = _p;
	_p = _p->Prev;

	return temp;
}

bool List::const_iterator::operator==(const const_iterator& rhs) const
{
	if (_p == rhs._p)
	{
		return true;
	}
	else
	{
		return false;
	}
}

bool List::const_iterator::operator!=(const const_iterator& rhs) const
{
	return !(*this == rhs);
}

bool List::const_iterator::operator==(nullptr_t p) const
{
	return (int&)const_iterator::operator*();
}

bool List::const_iterator::operator!=(nullptr_t p) const
{
	return !(*this == nullptr);
}

int& List::iterator::operator*() const
{
	return (int&)const_iterator::operator*();
}

int* List::iterator::operator->() const
{
	return (int*)const_iterator::operator->();
}

List::iterator&
List::iterator::operator++()
{
	const_iterator::operator++();
	return *this;
}

List::iterator
List::iterator::operator++(int)
{
	iterator temp = *this;
	const_iterator::operator++();
	return temp;
}

List::iterator&
List::iterator::operator--()
{
	const_iterator::operator--();
	return *this;
}

List::iterator
List::iterator::operator--(int)
{
	iterator temp = *this;
	const_iterator::operator--();
	return temp;
}

List::List()
{
	_end->Next = _end;
	_end->Prev = _end;
}

List::List(size_t count)
	:List()
{
	for (size_t i = 0; i < count; i++)
	{
		push_front(0);
	}
}

List::List(const List& other)
	:List()
{
	iterator inserted = --begin();
	for (const_iterator iter = other.begin(); iter != other.end(); ++iter)
	{
		inserted = insert(inserted, *iter);
	}
}

List& List::operator=(const List& rhs)
{
	if (this != &rhs)
	{
		List temp(rhs);
		//swap(_end, temp._end);
		//swap(_begin, temp._begin);
		//swap(_size, temp._size);
		std::swap(_end->Next, temp._end->Next);
	}

	return *this;
}

List::~List()
{
	clear();

	/*delete _end;
	_end = nullptr;*/
	//_begin = nullptr;
}

int& List::front()
{
	return *begin();
}

const int& List::front() const
{
	return *begin();
}

int& List::back()
{
	return *(--end());
}

const int& List::back() const
{
	return *(--end());
}

List::iterator List::begin()
{
	return iterator(_end->Next);
}

List::const_iterator List::begin() const
{
	return const_iterator(_end->Next);
}

List::iterator List::end()
{
	return iterator(_end);
}

List::const_iterator List::end() const
{
	return const_iterator(_end);
}

List::iterator List::insert(iterator pos, int value)
{
	Node* nextNode = pos._p;
	Node* prevNode = pos._p->Prev;
	Node* newNode = new Node(value, prevNode, nextNode);

	/*newNode->Prev = prevNode;
	newNode->Next = nextNode;*/
	prevNode->Next = newNode;
	nextNode->Prev = newNode;

	++_size;

	return newNode;
}

List::iterator List::erase(List::iterator pos)
{
	Node* removed = pos._p;
	Node* removedPrev = removed->Prev;
	Node* removedNext = removed->Next;

	removedPrev->Next = removedNext;
	removedNext->Prev = removedPrev;

	delete removed;
	
	--_size;
	
	return removedNext;

}

void List::push_front(int value)
{
	insert(begin(), value);
}

void List::push_back(int value)
{
	insert(end(), value);
}

void List::pop_front()
{
	erase(begin());
}

void List::pop_back()
{
	/*iterator iter = end();
	--iter;
	erase(iter);*/
	erase(_end->Prev);
}

bool List::empty() const
{
	if (_size == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}

size_t List::size() const
{
	return _size;
}

void List::clear()
{
	while (empty() == false)
	{
		pop_front();
	}
}

bool List::contains(int value) const
{
	for (const_iterator iter = begin(); iter != end(); ++iter)
	{
		if (*iter == value)
		{
			return true;
		}
	}
	return false;
}

• Main.cpp

#include <iostream>
#include <list>
#include "List.h"
using namespace std;

int main()
{
	List mylist;
	std::list<int> flist;

	/*mylist.push_front(1);
	flist.push_front(1);*/

	
	
	auto iter = mylist.begin();
	cout << "현재 mylist 첫번째 값: " << *iter << "\\n";

	for (int i = 0; i < 10; i++)
	{
		mylist.push_front(i);
		// [1] [1] [2] ... [8] [9] 
		flist.push_front(1);
	}
	if (flist.front() == mylist.front())
	{
		cout << "같음\\n";
	}
	for (iter = mylist.begin(); iter != mylist.end(); ++iter)
	{
		cout << "[" << *iter << "]" << " ";
	}
}