[42Seoul] CPP08 STL

이 모듈에서는 표준 컨테이너와 표준 알고리즘 없이도 연습 문제를 해결할 수 있습니다.
단, 이 모듈을 사용하는 것이 정확히 본 모듈의 목표입니다. STL을 사용할 수 있습니다. 예, 컨테이너(벡터/리스트/맵/등)와 알고리즘(헤더 <알고리즘>에 정의)을 사용할 수 있습니다. 게다가, 당신은 가능한 한 그것들을 많이 사용해야 합니다. 따라서, 적절한 곳에 적용하기 위해 최선을 다하세요.
코드가 예상대로 작동하더라도 그렇지 않으면 매우 나쁜 점수를 받게 됩니다

헤더 파일에서 템플릿을 평소처럼 정의할 수 있습니다. 어떤 경우에도 헤더 파일은 필수입니다.

---

C++ STL(표준 템플릿 라이브러리)은 벡터, 목록, 대기열 및 스택과 같이 널리 사용되는 많은 알고리즘과 데이터 구조를 구현하는 템플릿으로 범용 클래스 및 함수를 제공하는 강력한 C++ 템플릿 클래스 세트입니다.

 

표준 템플릿 라이브러리의 핵심에는 잘 구성된 세 가지 구성 요소

#include <algorithm>

다양한 요소에서 사용하도록 특별히 설계된 기능 모음을 정의합니다. 그들은 컨테이너에 작용하고 컨테이너의 내용물에 대한 다양한 작업을 위한 수단을 제공합니다.

 

sort(startaddress, endaddress) (참고)

startaddress: 첫 번째 주소
              배열의 요소
endaddress: 다음 주소
            인접 위치
            배열의 마지막 요소.
따라서 실제로 sort()는
범위 (시작 주소, 끝 주소)

 

binary_search(startaddress, endaddress, valuetofind) (참고)

매개변수:
startaddress: 첫 번째 주소
              배열의 요소.
endaddress: 다음 인접 주소
            배열의 마지막 요소의 위치.
valuetofind: 우리가 가지고 있는 목표 값
             검색합니다.
반환값: 
valuetofind와 같은 요소가 발견되면 true이고, 그렇지 않으면 false입니다.

 

Array algorithms

all_of() : 모든 요소에 대해 지정된 속성을 확인하고 범위의 각 요소가 지정된 속성을 만족하면 true를 반환하고 그렇지 않으면 false를 반환합니다.

int ar[6] =  {1, 2, 3, 4, 5, -6};
  
all_of(ar, ar+6, [](int x) { return x>0; }) ?
    cout << "All are positive elements" :
    cout << "All are not positive elements";

any_of() : 하나 이상의 요소가 속성을 충족하면 true를 반환하고 그렇지 않으면 false를 반환합니다. (사용은 any_of()와 동일)

none_of() : 주어진 조건을 충족하는 요소가 없으면 true를 반환하고 그렇지 않으면 false를 반환합니다. (사용은 any_of()와 동일)

 

copy_n() : 하나의 배열 요소를 새 배열에 복사합니다. 이 유형의 복사는 배열의 전체 복사본을 만듭니다. 이 함수는 소스 배열 이름, 배열 크기 및 대상 배열 이름의 3가지 인수를 사용합니다.

iota() : 배열에 연속 값을 할당하는 데 사용됩니다. 이 함수는 3개의 인수(배열 이름, 크기 및 시작 번호)를 받습니다.

int ar[6];
iota(ar, ar+6, 20);

// ar[] : {20, 21, 22, 23, 24, 25}

 

그 외 알고리즘 라이브러리(참고)

 

Vector

: 요소가 삽입되거나 삭제될 때 자동으로 크기가 조정되는 기능이 있는 동적 배열과 동일하며 해당 저장소는 컨테이너에서 자동으로 처리됩니다. 벡터 요소는 반복자를 사용하여 액세스하고 탐색할 수 있도록 연속 스토리지에 배치됩니다.

• begin() – 벡터의 첫 번째 요소를 가리키는 반복자를 반환합니다.
• end() – 벡터의 마지막 요소 뒤에 오는 이론적인 요소를 가리키는 반복자를 반환합니다.
• rbegin() – 벡터의 마지막 요소를 가리키는 역방향 반복자를 반환합니다(역방향 시작). 마지막 요소에서 첫 번째 요소로 이동합니다.
• rend() – 벡터의 첫 번째 요소 앞에 있는 이론적인 요소를 가리키는 역방향 반복자를 반환합니다(역방향 끝으로 간주됨).
• cbegin() – 벡터의 첫 번째 요소를 가리키는 상수 반복자를 반환합니다.
• cend() – 벡터의 마지막 요소 뒤에 오는 이론적인 요소를 가리키는 상수 반복자를 반환합니다.
• crbegin() – 벡터의 마지막 요소를 가리키는 상수 역방향 반복기를 반환합니다(역방향 시작). 마지막 요소에서 첫 번째 요소로 이동합니다.
• crend() – 벡터의 첫 번째 요소 앞에 있는 이론적인 요소를 가리키는 일정한 역방향 반복기를 반환합니다(역방향 끝으로 간주됨).

 

Stack

: LIFO(Last In First Out) 유형이 작동하는 컨테이너 어댑터 유형으로, 한쪽 끝(상단)에 새 요소가 추가되고 해당 끝에서만 요소가 제거됩니다.

#include <stack>
/* 
template <class Type, class Container = deque<Type> > class stack;

Type – is the Type of element contained in the std::stack.
       It can be any valid C++ type or even a user-defined type.
Container – is the Type of underlying container object.
Member Types:
value_type- The first template parameter, T. It denotes the element types.
container_type- The second template parameter, Container. It denotes the underlying container type.
size_type- Unsigned integral type.
*/

• empty() – 스택이 비어 있는지 여부를 반환합니다.
• size() – 스택 크기를 반환합니다. 
• top() – 스택의 최상위 요소를 반환합니다.  
• push(new) – 스택의 맨 위에 'new' 요소를 추가합니다.
• pop() – 맨 위에 있는 요소를 삭제합니다. 

 

iterators(반복자 참고)

:  반복자 STL 컨테이너의 메모리 주소를 가리키는 데 사용됩니다 . 그들은 주로 숫자, 문자 등의 시퀀스에 사용됩니다. 프로그램의 복잡성과 실행 시간을 줄입니다.

---

타입 T를 수용하는 함수 템플릿 easyfind를 작성하세요. 두 개의 매개 변수(첫 번째 유형은 T형이고 두 번째 유형은 정수)가 필요합니다.
T가 정수의 컨테이너라고 가정할 때, 이 함수는 첫 번째 매개 변수에서 두 번째 매개 변수의 첫 번째 발생을 찾아야 한다.
항목이 발견되지 않으면 예외를 발생시키거나 선택한 오류 값을 반환할 수 있습니다. 표준 컨테이너가 어떻게 동작하는지 분석합니다.
당신은  associative containers(연관 컨테이너 참고)를 다룰 필요가 없습니다.

---

std::find (참고)

: 주어진 숫자 범위에서 요소를 찾습니다. 범위 (first,last)에서 val과 같은지 비교하는 첫 번째 요소에 대한 반복자를 반환합니다. 그러한 요소가 발견되지 않으면 함수는 마지막을 반환합니다.

Return Value
An iteratorª to the first element in the range that compares equal to val.
If no elements match, the function returns last

// 이 함수 템플릿의 동작은 다음과 같습니다.

template<class InputIterator, class T>
InputIterator find (InputIterator first, InputIterator last, const T& val)
{
  while (first!=last) {
    if (*first==val) return first;
    ++first;
  }
  return last;
}

Iterator first : 컨테이너의 첫 번째 요소를 가르키는 반복자
lterator last : 컨테이너의 마지막 요소의 다음을 가르키는 반복자

 

Iteratorª (참고1, 참고2)

: 반복자 는 요소 범위(예: 배열 또는 컨테이너) 의 일부 요소를 가리키고 연산자 집합을 사용하여 해당 범위의 요소를 반복할 수 있는 모든 개체입니다( 최소한 증분( ++) 및 역참조( *) 연산자).
반복자의 가장 확실한 형태는 포인터 입니다 . 포인터는 배열의 요소를 가리킬 수 있으며 증가 연산자( ++)를 사용하여 요소를 반복할 수 있습니다. 포인터와 비슷한 형태일 뿐 NULL을 가질 수 없다.

#include<iostream>
#include<iterator> // for iterators
#include<vector> // for vectors

int main()
{
    vector<int> ar = { 1, 2, 3, 4, 5 };
      
    // Declaring iterator to a vector
    vector<int>::iterator ptr;
      
    // Displaying vector elements using begin() and end()
    std::cout << "The vector elements are : ";
    for (ptr = ar.begin(); ptr < ar.end(); ptr++)
        std::cout << *ptr << " ";
      
    return 0;    
}

 

std::vector::begin (참고)

: 반복자를 처음으로 되돌리기
벡터 의 첫 번째 요소를 가리키는 반복자를 반환합니다 . 첫 번째 요소에 대한 참조를 반환하는 vector::front 멤버와 달리 이 함수는 해당 요소를 가리키는 임의 액세스 반복기 를 반환합니다. 컨테이너가 비어 있으면 반환된 반복기 값은 역참조되지 않습니다.

 

std::vector::end (참고)

: 반복자를 끝으로 반환

벡터 컨테이너 의 과거 끝 요소를 참조하는 반복자를 반환합니다 . 과거 요소는 벡터 의 마지막 요소 뒤에 오는 이론적 요소입니다 . 어떤 요소도 가리키지 않으므로 역참조되지 않습니다. 표준 라이브러리의 함수가 사용하는 범위에는 닫는 반복자가 가리키는 요소가 포함되지 않기 때문에 이 함수는 vector::begin 과 함께 사용 하여 컨테이너의 모든 요소를 ​​포함하는 범위를 지정하는 경우가 많습니다. 컨테이너가 비어 있으면 이 함수는 vector::begin 과 동일한 결과를 반환 합니다 .

 

---

최대 N개의 정수를 저장할 수 있는 Span 클래스를 만듭니다. 변수 N은 unsigned int이며 생성자에게 전달되는 유일한 매개 변수입니다.
이 클래스에는 단일 숫자를 범위에 추가하는 addNumber()라는 멤버 함수가 있습니다. 그것은 그것을 채우기 위해 사용될 것이다. 이미 N개의 요소가 저장되어 있는 경우 새 요소를 추가하려고 하면 예외가 발생합니다.

저장된 모든 숫자 중에서 가장 짧은 스팬 또는 가장 긴 스팬(또는 원하는 경우 거리)을 각각 찾아 반환합니다. 저장된 숫자가 없거나 하나만 있는 경우 범위를 찾을 수 없습니다. 따라서 예외를 발생시킵니다.

최소 10,000개의 숫자로 범위를 테스트합니다. 많으면 더 좋을 것 같아요.
마지막으로, 다양한 반복자를 사용하여 여러분의 범위를 채우는 것은 멋질 것입니다.
addNumber() 하기 위해 수천 통의 전화를 거는 것은 정말 짜증난다. 멤버 기능 구현
한 번의 통화로 스팬에 많은 숫자를 추가할 수 있습니다.

🛎 컨테이너를 찾아 보세요. 일부 멤버 함수는 일련의 요소를 컨테이너에 추가하기 위해 일정 범위의 반복자를 사용합니다.

---

위에서 언급이 되었지만, 다시 Vector에 대해서 이야기 하자면,

 

Vector

: 요소가 삽입되거나 삭제될 때 자동으로 크기가 조정되는 기능이 있는 동적 배열과 동일하며 해당 저장소는 컨테이너에서 자동으로 처리됩니다. 벡터 요소는 반복자를 사용하여 액세스하고 탐색할 수 있도록 연속 스토리지에 배치됩니다.

 

N개의 요소로 한정적인 데이터 보관소? 를 한다면,

 

reserve (참고)

: 벡터 용량 이 최소한 n개의 요소 를 포함하기에 충분하도록 요청합니다 .

 

size (참고)
: 벡터 요소 수를 반환합니다. 이것은 벡터 에 포함된 실제 객체의 수이며, 반드시 저장 용량 과 같지는 않습니다 .

 

clear (참고)

: 벡터에서 모든 요소 (파괴됨)를 제거하고 컨테이너의 크기는 0 으로 유지 합니다. 재할당이 보장 되지 않으며 이 함수 호출로 인해 벡터 용량이 변경된다는 보장도 없습니다.

 

min_element (참고)

: 범위에서 가장 작은 값을 가진 요소를 가리키는 반복자를 반환

template <class ForwardIterator>
ForwardIterator min_element (ForwardIterator first, ForwardIterator last);

---

std::stack container 는 매우 좋습니다.

안타깝게도, 이것은 반복자를 사용할 수 없는 유일한 STL 컨테이너 중 하나입니다.

특히 우리가 원본 스택 구조를 지우고 누락된 기능을 생성할 수 있습니다. 이러한 것을 고치려면, 여러분은 std::stack 컨테이너를 반복자를 사용할 수 있도록 만들어야 합니다.

MutantStack 클래스를 만드세요. std::stack의 관점에서 구현합니다.
MutantStack은 모든 멤버 함수와 추가 기능을 제공하고, 추가로 다음의 기능을 갖습니다: 반복자.
예를 들어, 만약 여러분이 MutantStack을 처음으로 실행하고, 그리고 두 번째로 std::list를 MutantStack이 있는 것으로 교체하는 경우, 두 출력이 동일해야 합니다.

당연히, 물론 다른 컨테이너를 테스트할 때 해당 멤버 함수로 아래 코드를 업데이트합니다(push()는 push_back()이 될 수 있음).

---

stack을 누르게 되면 class deque를 기본값으로 T 의 할당자 클래스 템플릿을 사용하는 것을 알 수 있습니다.

protected의 c를 사용하게 되면 deque에서 사용하는 반복자를 사용하게 되며, 이것을 이용하여 나만의 Stack을 구현하면 됩니다.