[CPP-08] STL containers, iterators, algorithms

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

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

Ex00: Easy find

[과제 소개]

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

1. STL(Standard Template Library)

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

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

반복자(iterator)
컨테이너(container)
알고리즘(algorithm)

2. 컨테이너(container)

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

2.1. 반복자(iterator)

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

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

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

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

2.2. 컨테이너의 종류

STL에서 컨테이너는 자료를 저장하는 방식과 관리하는 방식에 따라 여러 가지 형태로 나뉠 수 있다. 표 참고

컨테이너 종류

설명

컨테이너

시퀀스 컨테이너(sequence container)

데이터를 선형으로 저장하며, 특별한 제약이나 규칙이 없는 가장 일반적인 컨테이너

vector, deque, list, forwad_list

연관 컨테이너(associative container)

키(key)와 값(value)처럼 관련있는 데이터를 하나의 쌍으로 저장하는 컨테이너

set, multiset, map, multimap

컨테이너 어댑터(adapter container)

간결함과 명료성을 위해 인터페이스를 제한한 시퀀스나 연관 컨테이너의 변형. 반복자를 지원하지 않으므로 STL 알고리즘에서는 사용할 수 없다.

stack, queue, priority_queue

각 컨테이너의 설명, 예제 정리

3. 벡터(vector)

undefined

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

3.1. 생성

#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

4. std::algorithm::find()

algorithm 클래스에 정의되어 있는 함수이다.

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를 수천번 호출하는 번거로움을 피할 수 있을 것이다.

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 알고리즘을 적절히 사용해서 함수를 작성했는지 확인하는 과제.

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를 구현한다.

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)

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

1.1. 생성

// <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이다.

2. container adapter

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

PreviousCPP Next[CPP-06] CPP 형변환 연산자

Last updated 3 years ago