ForestBird

생성자와 소멸자는 이전에 포스팅한 벡터와 동일합니다.

PushBack()

스택은 당연히 뒤에 값을 추가하는건데 굳이 Back이라는 단어를 사용한 이유는 명확성 때문에 사용했습니다.

	//마지막 위치에 원소를 추가합니다
	void PushBack(const Data& data)
	{
		//컨테이너에 비어있는 자리가 있는지 확인
		if (this->my_size == this->my_capacity)
		{
			//빈자리 없음. 재할당을 시도합니다
			this->Reserve(this->my_capacity + this->additive_capacity);
		}

		//추가합니다
		this->my_base[this->my_size++] = data;
	}

1. 스택에 빈자리 체크

2. 추가

Reserve()에 대해선 여기를 봐주세요

https://forestbird0.tistory.com/38

스택도 벡터처럼 내부적으로 '동적 배열'을 사용하기 때문에 벡터와 크게 차이가 없습니다. 구현이 더 쉬운편에 속하죠.

언제든 마지막 위치에 원소를 추가하기 때문에 순서가 꼬이는 걱정도 하지 않아도 됩니다.

PopBack()

Top()

	Data& PopBack()
	{
		this->CheckValidIndex(this->my_size - 1);
		return this->my_base[this->my_size-- - 1];
	}

	Data& Top()
	{
		this->CheckValidIndex(this->my_size - 1);
		return this->my_base[this->my_size - 1];
	}

정말 간단하죠?

1. 인덱스 유효성 검사

2. 값 반환.

그저 둘 함수의 차이가 있다면, PopBack()은 반환하면서 원소를 삭제합니다. 삭제라고 표현했지만 원소자체가 삭제되지는 않고, 스택 원소개수 카운팅을 1개 줄입니다. 그러면 다음에 PushBack()으로 원소를 채우면 기존 원소값을 덮어씌워버리게 됩니다.

Top()은 마지막 원소를 반환만 할 뿐 삭제하진 않습니다.

스택 구현은 어렵지 않습니다. 구현자체에 목적을 두지 말고

내부적으로 '동적 배열'이 어떻게 활용되는지를 봐야 합니다. 

https://github.com/ForestBird1/MyContainer

스택은 LIFO(Last-in First-Out)규칙을 가지고 있어서 스택원소를 반환할 때 마지막에 들어온 데이터를 반환하게 됩니다.

마치 차곡차곡 쌓인 무언가와 비슷합니다. 가장 먼저들어간 물체는 제일 밑에 있어서 가장 마지막에 꺼내야하죠. 그리고 당연히 중간에 있는 원소를 가져올 수도 없습니다.

이런 방법은 함수를 호출할 때와 동일합니다.

함수가 호출되면 스택메모리영역에 쌓이게 되고 모든 함수의 호출이 완료되었으면 마지막(가장 최근)에 호출했던 함수부터 차례대로 반환하게 됩니다.

스택은 LIFO규칙만 생각하고 만들면 굉장히 쉽게 구현할 수 있습니다.

벡터처럼 모든원소에 접근할 필요가 없고, 반복자도 필요없습니다.

물론 필요에 의해서 구현할 수는 있지만, 필수는 아닙니다.

1. PushBack()

원소를 추가할 때 사용되는 유일한 함수입니다.

2. PopBack()

마지막으로 추가된 원소를 반환하고 삭제합니다.

3. Num()

스택의 원소개수입니다. 원소가 0개라면 1,2번 함수를 호출하면 런타임에러를 발생하기 때문에

해당 함수로 원소개수를 체크해야할 상황이 생깁니다.

이 정도의 함수면 스택을 구현할 수 있습니다. 빡 조이면 3번을 빼고 1번과 2번함수만으로 구현할 수 있죠.

그러나 편의성을 위해서 몇개 더 구현하겠습니다.

4. Top()

마지막으로 추가된 원소를 반환하지만, 원소를 삭제하지 않습니다.

5. IsEmpty()

스택이 비어있으면 true, 1개 이상의 원소가 있으면 false를 반환합니다

예제코드에서는 5번함수가 구현되어있지 않습니다. 한번 직접 구현해보세요.

template <typename Data>
class Container_Master
{
protected:
	Data* my_base = nullptr;
	size_t my_capacity = 0;
	size_t my_size = 0;

	//캐퍼시티를 늘릴 때 지정된 값이 없다면 해당 값만큼 늘립니다
	const size_t additive_capacity = 32;
public:
	//컨테이너의 공간을 새로 생성합니다
	void Reserve(size_t capacity)
	{
		//기존 캐퍼시티가 더 크다면 재할당을 하지 않습니다
		if (my_capacity >= capacity)
			return;

		Data* temp = new Data[capacity];
		my_capacity = capacity;

		//컨테이너에 원소가 있다면 새로 할당한 주소로 옮겨줍니다
		if (my_size >= 1)
		{
			for (size_t i = 0; i < my_size; i++)
			{
				temp[i] = my_base[i];
			}
			delete[] my_base;

		}

		my_base = temp;
	}

	//배열의 원소를 삭제하지않고
	//사이즈를 0으로 만듭니다
	//Clear()함수후에 원소룰 추가하면 기존에 있던 원소를 덮어씌웁니다
	void Clear()
	{
		my_size = 0;
	}

	//컨테이너의 원소개수입니다
	size_t Num()
	{
		return my_size;
	}

	//컨테이너의 캐퍼시티개수입니다
	size_t Max()
	{
		return my_capacity;
	}
	
	//인덱스 유효성검사를 합니다
	//유효하지 않으면 throw
	bool CheckValidIndex(const size_t index)
	{
		if ((index >= 0) && (index < this->my_size))
		{
			return true;
		}
		else
		{
			throw printf("범위를 벗어난 인덱스를 사용하였습니다. 접근하려는 인덱스: %d, 배열크기: %d", index, this->Num());
		}
	}
};

#include "Container_Master.h"

template <typename Data>
class MyStack : public Container_Master<Data>
{

};

이전에 포스팅했던 벡터와 중복되는 함수는 부모클래스에서 다룹니다.

내부적으론 벡터와 동일하게 '동적 배열'을 사용합니다.

다만 중간삽입, 삭제가 없이 마지막위치에서 삭제, 삽입을 하기 때문에 당연히 모든 원소가 메모리에서 인접해 있고, 원소의 순서가 보장되어 있습니다.

https://github.com/ForestBird1/MyContainer

이터레이터는 '원소를 순서대로 접근하는 반복 오브젝트' 정도로 이해하면 되겠다.

'순서'는 거꾸로 혹은 임의의 방식으로 돌아갈 수 있다.

우리는 가장 기본적인 '처음부터 마지막'순서의 이터레이터만 구현해보자

template <typename Data>
class MyVector : public Container_Master<Data>
{

public:

	class iterator
	{
	private:
		Data* pos = nullptr;
	public:
		iterator(Data* pos = 0)
		{
			this->pos = pos;
		}
		Data& operator* ()const
		{
			return *pos;
		}

		bool operator!=(const iterator& iter)const
		{
			return pos != iter.pos;
		}
		bool operator==(const iterator& iter)const
		{
			return pos == iter.pos;
		}

		//전위
		iterator& operator++()
		{
			++pos;
			return (*this);
		}
	};
    
public:
    	iterator begin()
	{
		iterator iter(this->my_base);
		return iter;
	}
	iterator end()
	{
		iterator iter(this->my_base + this->my_size);
		return iter;
	}
};

나는 벡터클래스 내부에 이터레이터클래스를 생성했다.

따로 이터레이터클래스를 만들어도 되는데 이터레이터는 이정도만 구현해도 될거같아서 그랬다.

코드에서 나오지만 이터레이터는 '원소를 가리키는 포인터'정도로 이해하면 된다.

포인터는 +1을 하면 포인터의 크기만큼 메모리상에서 이동하게 되는데

포인터의 크기는 곧 주소의 크기고 32비트 환경에서는 4바이트, 64비트 환경에서는 8바이트의 사이즈를 가지게 된다.

빈공간없이 붙어있는 벡터의 경우

begin()를 보면 벡터 내부의 배열을 이터레이터생성자로 넘기면

배열의 첫 부분을 가리키는 포인터를 이터레이터가 가지게 된다.

거기서 ++iter를 하게 된다면, 이터레이터 내부의 포인터도 ++pos을 하게 되고,

포인터의 크기만큼 이동하게 되므로 당연히 다음 포인터를 가리키게 되고

그 결과 이터레이터는 다음 원소를 가리키게 된다.

이런 방식이라고 보면된다.

이터레이터로 루프돌리는 방법은

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

for (auto it : vector)
{
	cout << (it) << endl;
}

MyVector<int>::iterator를 직접 선언해서 사용해도 되지만 상당히 귀찮기 때문에

c++11이후로 변경된 'auto'키워드를 사용하서 간편하게 다뤄도 된다

range-based for loop방식을 사용하면 더 간편하게 사용할 수 있다.

이 방법도 c++11에서 생긴 방법이다

이제 거의 모든 기능을 구현했지만 하나의 기능을 아직 구현하지 않았다.

그것은 벡터의 원소에 빠르게 접근하기 위한 operator[]

	Data& operator[] (const size_t index)
	{
		//인덱스가 유효하면 인덱스 위치에 보관한 자료를 반환하세요.
		this->CheckValidIndex(index);

		//데이터를 반환합니다
		//반환 형식이 참조 형식임을 주의하세요.
		return this->my_base[index];
	}

어렵지 않다. 벡터에 []을 사용하면 내부에서 배열에 []을 사용해서 원소를 가져오는 방법이다.

인덱스가 유효한지 검사하는 함수만 추가되었을 뿐이다.

이렇게 벡터의 기본적인 함수를 구현했다.

예제코드에 있지만 여기선 설명하지 않은 함수가 있다. 어려운 코드가 아니니 금방 이해하실 수 있다.

https://github.com/ForestBird1/MyContainer