C++ - Module 08

Templated containers, iterators, algorithms

Day-specific rules

You will notice that in this particular subject, a lot of the problems you are asked to solve can be solved by NOT using standard containers and NOT using standard algorithms.
However, using those is precisely the goal, and if you do not make every effort to use standard containers and algorithms wherever it’s appropriate, you WILL get a very bad grade, however functional your work may be. Please don’t be so lazy.

여러분은 이 특정 주제에서 여러분이 풀어야 할 많은 문제들이 표준 컨테이너를 사용하지 않고 표준 알고리즘을 사용하지 않고 풀 수 있다는 것을 알게 될 것입니다.
그러나, 이러한것들을 사용하는것을 목표로 합니다. 그리고 만약 너가 스택다드 콘테이너와 알고리즘을 적절한곳에 사용하려고 노력하지 않으면 , 너는 안좋은 평가를 받을거다, 기능적으로 작동해도, 제발 게으르지마.

Exercise 00: Easy find

Turn-in directory : ex00/
Files to turn in : easyfind.hpp main.cpp
Forbidden functions : None

An easy one to start off on the right foot...
시작에서 쉬운문제부터 해보자...

Make a template function called easyfind, templated on a type T, that takes a T and an int.
easyfind라고 불리는 템플릿함수를 만들어라. 템플릿 타입은 T이다. 그 함수는 T와 int형을 가진다.

Assume the T is a container of int, and find the first occurrence of the second parameter in the first parameter.
T가 int의 컨테이너라고 가정하고, 첫번째 매게변수에서 두번째 매게변수를 찾습니다.

If it can’t be found, handle the error either using an exception or using an error return value. Take ideas from how standard containers work.
찾을 수 없으면 예외를 사용하거나 오류 반환 값을 사용하여 오류를 처리합니다. 표준 컨테이너의 작동 방식에서 아이디어를 얻으십시오.

Of course, you will provide a main function that tests it thoroughly.
물론, 당신은 main 함수에서 이것들을 테스트하는 코드를 제공해야한다.

이걸 해결하기 위해 해야하는건 우선 컨테이너를 만들어야한다.
컨테이너는 같은 타입의 자료형을 관리하기 쉽게 모아서 관리하는걸 컨테이너라 한다.

표준 컨테이너 : array, deque, forward_list, list, map, queue, set, stack, unordered_map, unordered_set, vector

과제를 읽어보니 int형 배열을 만들고 거기서 찾을수 없으면 예외가 나는 표준 템플릿이면 될거 같다.

폐기....

표준 array를 읽어보고 똑같이 만들어보자.

template < class T, size_t N > class array;

array는 고정 크기 시퀀스 컨테이너입니다. 만들고 나면 늘리거나 줄일 수 없어요.
arrya은 메모리에 할당 할때 index0 옆에 index1이 있고 이런식으로 모든 index주소들이 다 붙어있습니다. (엄격한 선형 시퀀스로 정렬)

다른 표준 컨테이너와 달리 배열은 고정된 크기를 가지며 할당자를 통해 요소 할당을 관리하지 않습니다. 고정 크기의 요소 배열을 캡슐화하는 집계 유형입니다. 따라서 동적으로 확장하거나 축소할 수 없습니다.(할당자를 통해 할당을하지 않는다고 해서 흠.. 굳이 new안써도 될까? 라고 고민했다.)

크기가 0인 배열은 유효하지만 역참조되어서는 안 됩니다. (new Array(0) 은 되지만, *Array or Array[0]하면 안된다.)

표준 라이브러리의 다른 컨테이너와 달리 두 개의 배열 컨테이너를 바꾸는 것은 범위의 모든 요소를 ​​개별적으로 바꾸는 선형 작업이며 일반적으로 상당히 덜 효율적인 작업입니다.

Exercise 01: Span

Turn-in directory : ex01/
Files to turn in : span.cpp span.hpp main.cpp
Forbidden functions : None

Make a class in which you can store N ints. N will be an unsigned int, and will be passed to the constructor as its only parameter.
N개의 정수를 저장할 수 있는 클래스를 만드십시오. N은 unsigned int이고 유일한 매개변수로 생성자에 전달됩니다.

This class will have a function to store a single number (addNumber), that will be used to fill it.
이 클래스는 하나의 넘버를 저장하는 함수를 가진다.

. Attempting to add a new number if there are already N of them stored in the
object is an error and should result in an exception.
새로운 숫자를 더 할때 만약 N개의 저장소에 이미 있다면 그것은 에러다. 그리고 결과로 exception을 뱉는다.

You will now make two functions, shortestSpan and longestSpan, that will find
out respectively the shortest and longest span between all the numbers contained in the object, and return it. If there are no numbers stored, or only one, there is no span to
find, and you will throw an exception

shortestSpan and longestSpan을 만들어, 그것은 그것은 모든 넘버스 사이에서 각각의 작은 차이값과 큰 차이값을 찾는다. 그리고 리턴한다.
만약 숫자저장값이 없거나, 또는 오직 하나만 있으면 스팬을 찾을수 없으므로 throw 예외처리를 해야한다.

Below is a (way too short) example of a test main and its associated output. Of course, your main will be way more thorough than this. You have to test at the very
least with 10000 numbers. More would be a good thing. It would also be very good if you could add numbers by passing a range of iterators, which would avoid the annoyance of making thousands of calls to addNumber...
아래 테스트는 너무 잛습니다. 물론 너의 메인은 이것모다 더 많이 테스트 해봐야한다. 너는 최소 10000개의 넘버가지고 테스트해봐. 더 많으면 좋아.
반복자의 범위를 전달하여 숫자를 추가할 수 있다면 좋을 것입니다. addNumber를 수천 번 호출하는 번거로움을 피할 수 있습니다.

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

$> ./ex01
2
14
$>

Exercise 02: Mutated abomination

Turn-in directory : ex02/
Files to turn in : mutantstack.cpp mutantstack.hpp main.cpp
Forbidden functions : None

Now that the appetizers are done, let’s do some disgusting stuff.

에피타이져가 완성되었으니 역겨운걸 해보자!???

The std::stack container is VERY cool, but it’s one of the only STL containers that is NOT iterable. That’s too bad. But why be okay with it, when we can simply play God and just butcher it to add some stuff we like?

스텍 컨테이너 매우멋져, 그러나 그것은 반복할수 없는 유일한 Stl컨테이너중 하나입니다. 그것은 나쁘다. 하지만 우리가 마치 신의 장난처럼 몇가지만 추가해준다면 괜찮을 것임.

You will splice this ability into the std::stack container, to repair this grave injustice.
이 능력을 std::stack 컨테이너에 접목시켜 이 심각한 부정을 해결할 수 있습니다.

Make a MutantStack class, that will be implemented in terms of a std::stack, and offer all of its member functions, only it will also offer an iterator.
std::stack 관점에서 구현될 MutantStack 클래스를 만드십시오. 그리고 모든 스택의 모든 기능을 제공합니다, 또한 iterator도 제공합니다.

Below is an example of code, the output of which should be the same as if we replaced the MutantStack with, for example, and std::list. You will of course provide tests for
all of this in your main function.
다음은 예를 들어 MutantStack을 및 std::list로 대체한 것과 같은 출력이 되어야 하는 코드의 예입니다.

당신은 물론 테스트를 제공합니다
이 모든 것이 주 기능에 있습니다.

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