[42서울] CPP Module 08 - STL

서론

당연히 STL 없이도 구현할 수 있지만 그걸 사용하는 것이 과제의 목적이므로 가능한 한 많이 사용하려고 노력할 것.

 

템플릿을 헤더 파일에 정의해도 되고 tpp파일에 정의해도 됨. 모든 경우에 tpp는 옵션, hpp는 필수 파일임

 

표준 템플릿 라이브러리(STL)는 컨테이너, 이터레이터, 함수 객체, 알고리즘을 나타내는 템플릿들의 집합…. 컨테이너는, 배열과 같이, 여러 개의 값을 저장할 수 있는 구성단위… 알고리즘은 배열을 소트 하거나 리스트에서 특정 값을 검색하는 것과 같은 특별한 작업들을 사용하기 위해 상용하는 방법… 이터레이터는 배열 안에서 포인터를 사용하여 위치를 옮기듯이, 컨테이너 안에서 위치를 옮길 수 있도록 도와주는 객체들이다. 즉, 이터레이터는 포인터의 일반화이다. - [C++ 기초 플러스 1241p. 성안당]

 

https://cplusplus.com/reference/stl/

Containers - C++ Reference

 

ex00

두 개의 인자를 받는 easyfind 함수를 만들어라(첫 번째 인자는 T, 두 번째 인자는 정수)

 

T가 정수형 컨테이너라고 가정하고 첫 번째 인자에서 두 번째 인자가 처음 발견되는 곳을 찾을 것

 

찾지 못하면 예외를 발생시켜도 되고 선택한 에러 값을 반환해서 처리해도 되는데, 표준 컨테이너가 어떻게 처리하는지를 보고 영감을 얻으면 좋다.

 

당연히 메인 문을 만들어서 테스트를 구현해서 제출해라

 

연관 컨테이너(Associative containers)는 처리하지 않아도 됨

 

 

template <typename T>
typename T::iterator easyfind(T& container, int value)
{
	typename T::iterator iter;

	iter = std::find(container.begin(), container.end(), value);
	if (iter == container.end()) 
	{
		throw std::runtime_error("value is not in this container");
	}
	return iter;
}

 

07 마지막에 array에 적용한 템플릿 함수를 컨테이너에서 사용할 수 있도록 만들어보는 과제이다.

 

연관 컨테이너는 처리하지 않아도 된다길래 궁금해서 해봤는데, set는 입출력이 조금 다를 뿐 크게 문제는 없었는데 map의 경우 따로 처리해줘야 할 것이 많아서 그냥 간단하게 만들어보라는 과제로 이해하였다.

 

표준 컨테이너가 find를 어떻게 처리하는지를 보니 iter를 container.end()로 지정하는 것으로 처리하고 있었다. end는 컨테이너 자료의 마지막의 다음 주소로, for문 등에서 편하게 사용하기 위해 마지막 주소가 아닌 그다음 주소를 가리키는 것으로 되어있는데, 그렇다면 굳이 이미 있는 함수를 다시 만들라는 의미는 아닌 것 같아서 (Don't reinvent the wheel) exception를 throw 하는 함수를 만들었다.

 

물론 당연히 find는 이터레이터의 시작과 끝을 지정해줘야 하고, 이 easyfind는 컨테이너 전체를 좀 더 쉽게 찾는 함수라고 생각하고 만들면 그냥 find의 반환과 동일하게 처리해도 되는 선택의 영역이라고 생각한다.

 

 

int main(void)
{
	std::vector<int> v;
	std::deque<int> d;
	std::list<int> l;

	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
		d.push_back(i);
		l.push_back(i);
	}

	try
	{
		std::cout << *(easyfind(v, 5)) << " is at " << std::distance(v.begin(), easyfind(v, 5)) << std::endl;
	}
	catch(const std::exception& e)
	{
		std::cerr << e.what() << '\n';
	}
	try
	{
		std::cout << *(easyfind(d, 0)) << " is at " << std::distance(d.begin(), easyfind(d, 5)) << std::endl;
	}
	catch(const std::exception& e)
	{
		std::cerr << e.what() << '\n';
	}
	try
	{
		std::cout << *(easyfind(l, 10)) << " is at " << std::distance(l.begin(), easyfind(l, 5)) << std::endl;
	}
	catch(const std::exception& e)
	{
		std::cerr << e.what() << '\n';
	}

	return (0);
}

 

0~9의 정수를 각각의 컨테이너에 넣은 다음 해당 값을 찾아보고 있으면 해당 값과 시작과의 거리를 출력하도록 만들었다. 값을 출력하기 위해 *를 붙인 걸 보고 처음에는 역시 이터레이터는 포인터였군…이라고 생각했는데 나중에 보니 포인터와 동일하게 * 이 들어왔을 때 값을 출력하도록 해당 객체의 클래스에 규정되어있었다.

 

이터레이터는 포인터의 일반화이다. 실제로 이터레이터는 포인터일 수도 있다. 또는 내용 참조와 증가와 같은 포인터를 닮은 연산들이 정의되어 있는 객체일 수도 있다. - [C++ 기초 플러스 1244p. 성안당]

 

처음에 몇 번째 인덱스에 있는지를 확인하기 위해 distance를 사용하지 않고 현재 이터레이터에서 begin을 빼는 식으로 구현했는데, 나중에 보니 이게 내가 의도한 대로 동작하는 컨테이너가 있고 아닌 컨테이너가 있었다. 그래서 다시 찾아보니 해당 함수를 알게 되어서 그걸 이용하여 구현하였다.

 

 

https://blog.naver.com/ya3344/221360287260

STL 컨테이너 종류와 특징

https://m.blog.naver.com/ktm0122/20167641378

[Effective C++] 항목 42. typename의 두 가지 의미를 제대로 파악하자.

https://eehoeskrap.tistory.com/263

[C++] 반복자 (Iterator)

https://lecor.tistory.com/77

[C++] map 출력하기

https://www.techiedelight.com/ko/find-index-of-an-element-in-array-cpp/

C++ 배열에서 요소의 인덱스 찾기

 

 

ex01

숫자 N을 받아서 N개의 정수를 저장할 수 있는 Span 클래스를 만들어라. N은 부호 없는 int 변수이며 유일한 매개변수이다.

 

이 클래스에는 숫자 하나를 Span에 추가하는 addNumber함수가 있다. 이미 있는 숫자를 넣는다면 exception을 던져라

 

shortestSpan과 longestSpan을 구현하여 저장된 숫자 중 가장 짧은 범위(즉 거리)와 긴 범위를 찾아서 반환하도록 하며, 저장된 숫자가 없거나 하나만 있다면 범위를 찾을 수 없으니 당연히 예외를 발생시켜야 한다.

 

메인 문은 주어지지만 최소 10000개의 숫자를 사용해서 테스트해야 한다.

 

마지막으로 다양한 iterator를 사용해서 Span을 채울 수 있게 하면 좋다. 수천 개의 숫자를 addNumber 하는 것은 화가 나니까 멤버 함수로 많은 숫자를 한 번에 넣을 수 있는 기능을 구현해라

 

잘 모르겠으면 컨테이너를 살펴봐야 하며 일부 멤버 함수는 iterator를 사용해야 한다.

 

int main()
{
Span sp = Span(5);
sp.addNumber(6);
sp.addNumber(3);
sp.addNumber(17);
sp.addNumber(9);
sp.addNumber(11);
std::cout << sp.shortestSpan() << std::endl;
std::cout << sp.longestSpan() << std::endl;
return 0;
}

$> ./ex01
2
14
$>

 

std::size_t Span::longestSpan() const
{
	if (v.size() <= 2)
	{
		throw std::logic_error("vector size is not over 2");
	}
	return (*std::max_element(v.begin(), v.end()) - *std::min_element(v.begin(), v.end()) );
}

std::size_t Span::shortestSpan() const
{
	if (v.size() <= 2)
	{
		throw std::logic_error("vector size is not over 2");
	}
	long ret = LONG_MAX;
	int prev;
	std::vector<int> tmp = v;

	std::sort(tmp.begin(), tmp.end());
	for (std::vector<int>::iterator iter = tmp.begin(); iter != tmp.end(); iter++) 
	{
		if (iter == tmp.begin()) 
		{
			prev = *iter;
		}
		else 
		{
			if (ret > *iter - prev) 
			{
				ret = *iter - prev;
			}
			prev = *iter;
		}
	}
	return static_cast<std::size_t>(ret);
}

하나의 ex에 하루 이상의 시간이 걸린 몇 안 되는 과제였다.

 

쉽게 풀면 쉽고 어렵게 풀면 어려운데, 뭐가 쉬운지를 찾는 과정이 생각보다 복잡했다. 그냥 처음 생각대로 했으면 더 빨랐겠지만 뭔가를 덜 배웠을 것 같긴 하다.

 

클래스의 다른 내용들은 별로 어렵지 않으니 생략하고, longestSpan도 별로 어렵지 않다. max_element 함수와 min_element 함수를 사용해서 벡터 내의 가장 큰 값에서 가장 작은 값을 빼면 그게 longestSpan이다.

 

shortestSpan 은 조금 까다로운데, 이런저런 방법을 고민해보다가 평가를 위해 코드로 봤을 때 가장 깔끔한 방법을 선택했다. 벡터를 복사한 다음 그 백터를 sort 하여 가장 작은 값에서 가장 큰 값으로 순서대로 나열한다. 그런 다음 이전 값과 다음 값을 하나씩 보면서 기존의 ret와 비교하여 더 적은 쪽을 저장하게 했다.

 

https://codingdog.tistory.com/entry/c-vector-reserve-vs-resize- 미리-공간을-만들어-놓고-쓰면-안-될까요

c++ vector reserve vs resize : 미리 공간을 만들어 놓고 쓰면 안 될까요?

https://www.techiedelight.com/ko/find-min-or-max-value-in-a-vector-in-cpp/

C++에서 벡터의 최소값 또는 최대값 찾기

 

https://cplusplus.com/reference/algorithm/max_element/?kw=max_element

max_element - C++ Reference

https://godog.tistory.com/entry/C-vector-%EC%83%9D%EC%84%B1-%EB%B0%8F-%EC%82%BD%EC%9E%85-%EC%82%AD%EC%A0%9C

C++ vector 생성 및 삽입, 삭제

 

ex02

std::stack 컨테이너는 좋지만, iterable 하지 않는 유일한 컨테이너이다.

 

이 부당함을 해결하기 위해 stack을 분해하여 우리가 원하는 기능을 넣어서 iterable 하게 만들자

 

stack을 상속받는 MutantStack 클래스를 만든 다음 iterator 기능을 추가해야 한다.

 

int main()
{
MutantStack<int> mstack;
mstack.push(5);
mstack.push(17);
std::cout << mstack.top() << std::endl;
mstack.pop();
std::cout << mstack.size() << std::endl;
mstack.push(3);
mstack.push(5);
mstack.push(737);
//[...]
mstack.push(0);
MutantStack<int>::iterator it = mstack.begin();
MutantStack<int>::iterator ite = mstack.end();
++it;
--it;
while (it != ite)
{
std::cout << *it << std::endl;
++it;
}
std::stack<int> s(mstack);
return 0;
}

 

이 테스트의 동작이 std::list와 동일해야 하며, 일부 함수를 바꿔서 테스트해야 할 수도 있다.

 

stack은 Adaptor Container 이므로 컨테이너 클래스가 지정되지 않은 채 인스턴스화 되면 deque를 가져와서 만든다. 따라서 deque의 iterator을 종류별로 구현하고, 각 iterator의 기능들을 구현하면 된다.

 

template <typename T>
class MutantStack : public std::stack<T>
{
 public:
	MutantStack(void) {};
	MutantStack(const MutantStack& obj) {*this = obj;};
	MutantStack& operator=(const MutantStack& obj) {*this = obj; return (*this);}
	~MutantStack(void) {};
	
	typedef typename MutantStack<T>::stack::container_type::iterator iterator;
	iterator begin(void) {return this->c.begin();}
	iterator end(void) {return this->c.end();}

	typedef typename MutantStack<T>::stack::container_type::reverse_iterator reverse_iterator;
	reverse_iterator rbegin(void) {return this->c.rbegin();}
	reverse_iterator rend(void) {return this->c.rend();}

	typedef typename MutantStack<T>::stack::container_type::const_iterator const_iterator;
	const_iterator cbegin(void) {return this->c.cbegin();}
	const_iterator cend(void) {return this->c.cend();}

	typedef typename MutantStack<T>::stack::container_type::const_reverse_iterator const_reverse_iterator;
	const_iterator crbegin(void) {return this->c.crbegin();}
	const_iterator crend(void) {return this->c.crend();}
};

 

int main()
{
{
MutantStack<int> mstack;
mstack.push(5);
mstack.push(17);
std::cout << mstack.top() << std::endl;
mstack.pop();
std::cout << mstack.size() << std::endl;
mstack.push(3);
mstack.push(5);
mstack.push(737);
mstack.push(0);
MutantStack<int>::iterator it = mstack.begin();
MutantStack<int>::iterator ite = mstack.end();
++it;
--it;
while (it != ite)
{
std::cout << *it << std::endl;
++it;
}
std::stack<int> s(mstack);
}

std::cout << "------------------------------\n";

{
std::list<int> list;
list.push_back(5);
list.push_back(17);
std::cout << list.back() << std::endl;
list.pop_back();
std::cout << list.size() << std::endl;
list.push_back(3);
list.push_back(5);
list.push_back(737);
list.push_back(0);
std::list<int>::iterator it = list.begin();
std::list<int>::iterator ite = list.end();
++it;
--it;
while (it != ite)
{
std::cout << *it << std::endl;
++it;
}
std::list<int> s(list);
}

return 0;
}

 

과제에도 적혀있듯이 list와 stack은 함수 이름들이 다르다. 해당 부분만 주의해서 메인 문을 만들면 동일한 출력이 나오는 걸 확인할 수 있다.