---
description: 과제의 핵심은 stack이 CPP에서 <컨테이너 어댑터>라는 점을 인식하는 것이다.
---

# \[CPP-08] STL containers, iterators, algorithms

> 여러분은 이 모듈에서 풀어야 할 많은 문제들이 표준 컨테이너, 표준 알고리즘을 사용하지 않음으로서 풀 수 있다는 것을 알게 될 것입니다. 그러나, **STL을 사용하는 것이 바로 목표**이며, 적절한 곳에서 표준 컨테이너와 알고리즘을 사용하기 위해 모든 노력을 기울이지 않는다면, 아무리 기능적이더라도 매우 나쁜 점수를 받게 될 것입니다. 너무 게을러지지 마세요.

## Ex00: Easy find

**\[과제 소개]**

* 템플릿 함수 `easyfind` 를 작성한다.
* `easyfind(T, int)`
  * T는 int인 **컨테이너**라 가정하고,
  * T에서 두번째 매개변수(의 첫 번째 항목)가 처음으로 등장하는 부분을 찾는 함수
* 찾았는데 없으면 error (exception 혹은 error 반환값)
  * 표준 컨테이너 작동 방식에서 아이디어를 얻으시오.

### 1. STL(Standard Template Library)

C++ 표준 템플릿 라이브러리인 STL은 CPP의 특징인 일반화 프로그래밍 패러다임의 한 축을 담당하고 있다. STL은 알고리즘을 일반화한 표현을 제공하여, 데이터의 추상화와 코드를 재활용할 수 있게 한다.

STL은 다음과 같은 구성 요소로 이루어진 템플릿을 제공한다.

1. `반복자(iterator)`
2. `컨테이너(container)`
3. `알고리즘(algorithm)`

### 2. 컨테이너(container)

* STL에서 컨테이너(container)는 같은 타입의 여러 객체를 저장하는 일종의 집합이라 할 수 있다.
* 컨테이너의 각 요소에는 **반복자(iterator)**&#xB97C; 사용하여 접근할 수 있다.
* 또한, 컨테이너는 요소의 추가 및 제거를 포함한 다양한 작업을 도와주는 여러 **멤버 함수**를 포함하고 있다.

#### 2.1. 반복자(iterator)

반복자(iterator)란 STL 컨테이너에 저장된 요소를 반복적으로 순회하여, 각각의 요소에 대한 접근을 제공하는 객체이다. 즉, 일종의 포인터로서, **iterator 타입의 iter 객체를 선언해 컨테이너의 특정 위치에 접근**할 수 있는 것이다.

*   **반복자가 필요한 이유**

    지금까지 우리는 배열의 요소에 접근할 때 `i` 같은 인덱스를 선언해 사용해왔다. 반복자는 그런 연산의 과정을 **어떤 객체에서나 동일하게 사용할 수 있도록 통일해서 cpp에서 제공하는 generic 포인터 객체**라고 생각하면 된다. iterator 클래스 내부에는 배열의 요소를 쉽게 가리킬 수 있도록 몇가지 멤버함수들이 정의되어 있다. iterator 메서드와 컨테이너 메서드를 적절히 사용하면 좋은 알고리즘을 가진 클래스와 함수를 작성할 수 있을 것이다.
* **itorator 메서드**
  * `iter`
  * `iter++`
  * `iter--`
  * `iter1 == iter2`
  * `iter1 != iter2`
  * `begin(객체)` : 객체의 시작 주소를 가지는 iterator 객체를 리턴한다.
  * `end(객체)` : 객체의 끝 주소를 가지는 iterator 객체를 리턴한다.

```cpp
std::vector<int>::iterator iter = begin(vec);

while (iter != end(vec))
{
    std::cout << *iter++ << " "; 
}
```

#### 2.2. 컨테이너의 종류

STL에서 컨테이너는 자료를 저장하는 방식과 관리하는 방식에 따라 여러 가지 형태로 나뉠 수 있다. 표 [참고](http://tcpschool.com/cpp/cpp_container_intro)

|               컨테이너 종류              |                                       설명                                       |                   컨테이너                   |
| :--------------------------------: | :----------------------------------------------------------------------------: | :--------------------------------------: |
|  **시퀀스 컨테이너**(sequence container)  |                  데이터를 선형으로 저장하며, 특별한 제약이나 규칙이 없는 가장 일반적인 컨테이너                  | `vector`, `deque`, `list`, `forwad_list` |
| **연관 컨테이너**(associative container) |                 키(key)와 값(value)처럼 관련있는 데이터를 하나의 쌍으로 저장하는 컨테이너                 |   `set`, `multiset`, `map`, `multimap`   |
|   **컨테이너 어댑터**(adapter container)  | 간결함과 명료성을 위해 인터페이스를 제한한 시퀀스나 연관 컨테이너의 변형. 반복자를 지원하지 않으므로 STL 알고리즘에서는 사용할 수 없다. |    `stack`, `queue`, `priority_queue`    |

* [각 컨테이너의 설명, 예제 정리](http://tcpschool.com/cpp/cpp_container_sequence)

### 3. 벡터(vector)

undefined

벡터(vector) 객체는 요소가 추가되거나 삭제될 때마다 **자동으로 메모리를 재할당**하여 크기를 동적으로 변경하는 배열이다. 시퀀스 컨테이너로 분류된다.

#### 3.1. 생성

```cpp
#include <vector> //헤더파일 추가
vector<[data type]> [변수이름] //선언
```

* `vector<int> v`: 비어있는 vector v를 생성
* `vector<int> v` = {10, 20, 30} : 10, 20, 30으로 초기화된 vector v를 생성
* `vector<int> v(5)`: 기본값(0)으로 초기화 된 5개의 원소를 가지는 vector v를 생성
* `vector<int> v(5, 2)`:  2로 초기화된 5개의 원소를 가지는 vector v를 생성
* `vector<int> v2(v1)`:  v2는 v1 vector를 복사해서 생성

#### 3.2. 멤버함수

| 분 류                | 멤버 함수               | 설 명                                                          |
| ------------------ | ------------------- | ------------------------------------------------------------ |
| **Iterators**      | begin               | 첫 번째 원소를 가리키는 반복자를 리턴한다.                                     |
|                    | end                 | 마지막 원소를 가리키는 반복자를 리턴한다.                                      |
|                    | rbegin              | 역 순차열의 첫 번째 원소를 가리키는 반복자를 리턴한다.                              |
|                    | rend                | 역 순차열의 마지막 원소를 가리키는 반복자를 리턴한다.                               |
| **Element access** | **at(inx)**         | **n번째 원소를 참조할 때 사용하며 v\[idx] 보다 속도는 느리지만, 범위를 점검하므로 안전합니다.** |
|                    | operator\[]         | n번째 원소를 참조할 때 사용하며 범위 점검을 안하므로 at보다 빠르다.                     |
|                    | **front()**         | **첫 번째 원소의 참조를 리턴한다.**                                       |
|                    | **back()**          | **마지막 원소의 참조를 리턴한다.**                                        |
| **Capacity**       | empty               | 원소 존재 유무를 체크한다. 아무것도 없으면 true, 있으면 false를 리턴한다.              |
|                    | size                | 원소의 개수를 리턴한다.                                                |
|                    | capacity            | vector에 할당된 메모리의 크기를 리턴한다.                                   |
| **Modifiers**      | clear()             | vector의 모든 원소를 제거한다. 메모리는 남아있다.                              |
|                    | **assign(n, x)**    | **기존 원소들은 모두 제거 후, 임의 x 값으로 n개의 원소를 할당한다.**                  |
|                    | **insert(2, 3, 4)** | **2번째 위치에 3개의 4값을 삽입합니다. (뒤엣놈들은 뒤로 밀림)**                     |
|                    | erase(iter)         | iter 가 가리키는 원소를 제거합니다.                                       |
|                    | **push\_back(7)**   | **vector의 끝에 원소 7을 추가한다.**                                   |
|                    | **pop\_back(**      | **vector의 마지막 원소를 제거한다.**                                    |
|                    | **swap**            | **v1.swap( v2 )일때 v1과 v2를 swap한다.**                          |

* [vector](https://blockdmask.tistory.com/70)

### **4. std::algorithm::find()**

[algorithm](https://modoocode.com/256) 클래스에 정의되어 있는 함수이다.

```jsx
template <class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T& val);
```

범위 안 (`first` 부터 `last` 전 까지) 의 원소들 중 `val` 과 일치하는 첫 번째 원소를 가리키는 반복자를 리턴한다. 만일 일치하는 원소를 찾지 못할 경우 `last` 를 리턴한다.

* 범위에는 first 가 가리키는 원소는 포함되지만 last 가 가리키는 원소는 포함되지 않는다.

## Ex01: Span

**\[과제 소개]**

* N ints를 저장할 수 있는 클래스를 만들어라.
* N은 unsigned int이고 생성자의 단일 파라미터로 사용된다.
* 이 클래스는 `addNumber`라는 하나의 숫자를 저장하는 함수가 있어야한다.
  * 이미 N개가 저장되어있는 경우 새 번호 추가시 예외가 발생함.
* `shortestSpan`,`longestSpan` 함수를 만들어라.
  * `shortestSpan` : 백터 안에 있는 원소들 중 차이가 가장 큰 값 구하기
  * `longestSpan` : 백터안에있는 원소들 중 차이가 가장 작은 값 구하기
  * 저장된 숫자가 없거나, 하나만 있으면 범위가 없므로 예외가 발생한다.
* 아래는 test main 예시와 출력값이다. 최소한 10000 개의 숫자로 테스트해야한다. iterator 범위를 전달하여 숫자를 추가 할 수 있다면, 숫자를 추가하기 위해 addNumber를 수천번 호출하는 번거로움을 피할 수 있을 것이다.

```cpp
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
$>
```

STL 알고리즘을 적절히 사용해서 함수를 작성했는지 확인하는 과제.

```cpp
int Span::shortestSpan(void) const
```

* 예외처리
  * span이 비어있거나 원소가 하나 뿐일 때
* 알고리즘
  * 카피 후 오름차순 정렬
  * 앞에서부터 두 개씩 차이를 저장해서 가장 작은 값 저장. `std::min()` 메서드 사용

## Ex02: Mutated abomination 8

**\[과제 소개]**

> std::stack 컨테이너는 훌륭하지만, **iterable이 아닌 유일한 STL 컨테이너** 입니다. iterator를 std::stack 컨테이너에 접목시켜 이 문제를 해결해보세요.

* std::stack을 상속받아 MutantStack 만들기
* `MutantStack` 클래스는 std::stack의 모든 멤버 함수를 제공하고, iterator도 제공한다.

즉, 스택에 이터레이터 기능을 추가한 컨테이너 구현하는 것이 과제의 핵심이다. 아래 주어진 메인문이 되도록 mutantstack를 구현한다.

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

### 1. 스택(stack)

![](https://github.com/hidaehyunlee/Fork-my-brain/tree/4f7d19f4487fe8d450e22a9b6451bbed865ce125/images/lectures-img_cpp_stack.png)

* `LIFO` (Last In First Out, 후입선출): 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 구조. 즉, 가장 나중에 저장된(push) 데이터가 가장 먼저 인출(pop)되는 구조이다.
* stack은 container가 아니라 **container adapter. 기존의 컨테이너에서 인터페이스를 제한**하여 만든 것이다.
* stack은 deque, list, vector 등의 **시퀀스 컨테이너를 기반으로 구현**된다. default는 deque 컨테이너이다.
  * \[stack Containe&#x72;_&#x74;ype]\(_[https://en.wikipedia.org/wiki/Stack](https://en.wikipedia.org/wiki/Stack)(C%2B%2B)) 를 참고하면 좋다.

#### 1.1. 생성

```cpp
// <stack> 헤더 추가
#include <stack>

// 비어있는 stack 생성
stack<int> s1;

// {1, 2, 3, 4, 5}로 초기화 된 stack 생성. s2.top()하면 5 나옴.
stack<int> s2({ 1, 2, 3, 4, 5 });
```

#### 1.2. 멤버함수

* `s.empty()` : 비어있는지 확인
* `s.size()` : 원소 수를 반환
* `s.top()` : 맨 위의 원소 리턴
* `s.push(n)` : 맨 위에 원소 추가
* `s.pop()` : 맨 위의 원소 삭제

#### 1.3. 멤버객체

* Container `c` : the underlying container. 즉, deque 컨테이너. 이 멤버는 `protected` member object이다.&#x20;

### 2. **container adapter**

과제의 핵심은 stack이 cpp에서 **컨테이너 어댑터** 라는 점을 인식하는 것이다. 컨테이너 어댑터는 각각의 기초가 되는 클래스의 인터페이스를 제한하여, 특정 형태의 동작만을 수행하도록 한다. 기초가 되는 컨테이너를 protected로 가지고 있기 때문에, stack을 상속 하면 deque 시퀀스 컨테이너의 멤버함수를 사용할 수 있다. 이를 이용해 iterator를 구현한다.
