c++ template, iterator

- template

int maximum(int a, int b) {
    if (a > b)
        return a;
    else
        return b;
}
...
maximum(1, 2); // 2

위 함수는 두 인자를 비교하여 큰 값을 리턴하는 함수이다.

하지만, int 자료형 밖에 비교할 수 없다.

 

만약 double형에 대해서 비교하고 싶다면, 같은 이름의 함수를 double형으로 또 만들어야 한다.

만약 문자열을 비교하고 싶다면? 클래스의 비교는?

같은 기능을 구현하기 위해서 정말 많은 같은 이름의 함수를 만들어야 할 것이다.

 

하지만, 아래의 template 기능을 사용하면 이런 걱정을 할 필요가 없다.

template <class Item>
Item maximum(Item a, Item b) {
    if (a > b)
        return a;
    else
        return b;
}
...
maximum(1, 2); // 2
maximum(12.34, 22.22); // 22.22

이런식으로 호출되는 인자의 타입에 따라 자동으로 그에 맞는 함수 객체를 만들어서 실행하게 된다.

 

아래와 같이 템플릿에 여러가지 타입을 선언할 수도 있다.

template <class Item, class SizeType>
Item array_max(Item data[], SizeType n) {
    SizeType i;
    Item answer;
    assert(n > 0);
    
    answer = data[0];
    for (i = 1; i < n; i++)
        if (data[i] > answer) 
            answer = data[i];
    
    return answer;
}

 

 

함수 뿐 만 아니라 클래스에서도 템플릿을 사용할 수 있다.

// bag.h
template <class Item>
class bag {
    public:
        typedef Item value_type;

        bag(Item v);

        Item get_data();

    private:
        Item data;
};

template <class Item>
bag<Item>::bag(Item v) {
    data = v;
}

template <class Item>
Item bag<Item>::get_data() {
    return data;
}

// main.cpp
#include <iostream>
#include <stdlib.h>
#include "bag.h"

using namespace std;

int main(int argc, char const *argv[])
{
    bag<long> v1(10);

    cout << v1.get_data() << endl;

    return 0;
}

위와 같이 하면 bag에 long 타입의 변수를 담고 저장 및 데이터를 가져올 수 있다.

int 타입을 담고싶다면 bag<int> 형식으로 선언하면 된다.

template을 사용하여 클래스를 분할 구현하고 싶다면, cpp 파일로는 에러가 발생할 수 있다.

.template 파일로 분할하는게 바람직하다.

 

 

- iterator

앞으로 자료 구조를 구현할 때는 c++ STL 안의 구현되어 있는 클래스를 활용하게 될 거 같다.

예로 들어 multiset 이라는 STL 클래스는 우리가 지금까지 구현했던 bag와 유사하다.

이 multiset 클래스 안에 멤버 함수를 살펴보자.

size_type count(const value_type &target) const;
size_type erase(const value_type &target);
size_type size() const;

...

iterator insert(const value_type &entry);

대부분 우리가 구현한 것과 동일한 구조를 갖고 있는데, 하나가 특이하다.

바로 insert 멤버 변수의 리턴 타입이 iterator란 것이다.

 

iterator란, 개발자가 클래스 컨테이너의 모든 아이템을 쉽게 훑어볼 수 있도록 구현한 class 객체이다.

(본질은 이전에 구현하면서 사용했던 cursor와 비슷하다...)

모든 클래스에서 사용할 수 있는 건 아니고, 해당 클래스를 위해 별도로 정의를 해줘야 한다.

 

가끔 iterator를 이용해 클래스 컨테이너 내의 값을 바꿀 수도 있는데, 조건이 있다.

바로, 컨테이너가 선형 구조인 경우이다. (데이터가 잘 정렬되어 있는 경우에만 가능)

 

그럼 multiset에서의 iterator 사용 방법에 대해 알아보자.

 

1. begin()

모든 STL 컨테이너 클래스 안에 정의되어 있는 함수로,

컨테이너에 첫 번째 아이템에 접근할 수 있는 iterator를 반환한다.

multiset<string>::iterator iter;
iter = actors.begin();

multiset의 경우에는 첫 번째 아이템으로 가장 작은 값이 리턴되는데, 

아이템의 순서를 결정하는 기준이 뭘까...?

 

바로, '<' 가 아래의 세 조건을 만족하는 기준 하에, multiset은 작은 순서대로 정렬한다.

1. Irreflexivity
   a, b가 같다면, a<b, b>a 는 절대 참이 될 수 없다. 즉, a<a는 참이 될 수 없다.
2. Antisymmetry
   a, b가 다르다면, a<b, b>a 둘 중 하나는 참이다. 단, 둘 다 참일 수는 없다.
3. Transitivity
   a<b, b<c를 만족한다면, a<c이다.

2. * operator

iterator가 가리키고 있는 현재 아이템에 접근할 수 있다.

multiset<string>::iterator iter;
iter = actors.begin();
cout << *iter << endl;

참고로, list같이 선형 구조를 취하고 있는 클래스 컨테이너는 *iter을 이용해 값을 바꿀 수는 있지만,

multiset같이 비 선형 구조를 취하고 있는 클래스 컨테이너는 *iter을 이용해 값을 바꿀 수 없다.

 

3. ++ operator

iterator가 컨테이너에서 다음 아이템을 가리키도록 바꿀 수 있다.

multiset<string>::iterator iter;
iter = actors.begin();
++iter;

 

4. end()

아이템의 끝을 가리키는 iterator을 반환한다.

for (iter = actors.begin(); iter != actors.end(); ++iter) {
    cout << *iter << endl;
}

여기서 중요한 점은 마지막 아이템을 가리키는 것이 아닌, 마지막 아이템의 다음을 가리킨다는 것이다.

즉, actors.end()를 한 뒤에 *iter을 하면 에러가 발생한다. actors.end() - 1 까지 접근이 가능하다.

 

추가적인 팁으로,

본인이 어떤 배열을 정렬하고 싶다면, 정렬하고자 하는 대상을 모조리 multiset 안에 집어넣고,

위 코드로 *iter을 통해 값을 뽑아보면, 정렬하고자 하는 대상이 정렬되서 나온다!

(앞서 말했 듯, multiset은 비 선형 구조이기 때문에 넣는 즉시 정렬되는게 아니라, iterator로 관측시 정렬되서 나오는 것이다)

 

 

multiset에서의 iterator 사용 방법에 대해 알아 봤으니, 이제 multiset에 구현된 함수도 한 번 사용해보자.

 

1. find(const value_type &target);

multiset<int> m;
multiset<int>::iterator position;
position = m.find(42);

find 함수를 사용하면, multiset에 42값을 가지는 아이템 중 처음으로 나오는 아이템의 iterator을 반환해준다.

만약 안나오면 end()에 해당하는 iterator을 반환해준다.

 

2. erase(iterator i);

position = m.find(42);
if (position != m.end())
    m.erase(position);

erase 함수를 사용하면, 현재 iterator가 가리키고 있는 아이템을 삭제한다.

 

 

iterator의 사용 방법, iterator의 사용처(multiset 함수의 일부)를 알았으니, 이제 직접 iterator을 구현해보자.

그 전에, iterator에 종류에 대해 설명하고 만들어보자.

 

전에 클래스의 동일한 함수를 일반 클래스 타입으로 리턴하는 경우와 const 클래스 타입으로 리턴하는 경우를 기억하는가?

이렇게 두 개를 구현했던 이유는 클래스 타입을 선언할 때, const 타입으로 선언할 수 있기 때문이다.

iterator의 경우에도 이렇게 일반 타입, const 타입 두 개을 정의해야 한다.

const multiset<int> m;
multiset<int>::const_iterator cursor;
for (cursor = m.begin(); cursor != m.end(); ++cursor) {…}

여기서 begin()은 const_iterator을 반환하고, end()도 const_iterator을 반환한다.

반환된 const_iterator을 이용하면 아무리 선형 구조의 클래스 컨테이너라도 값을 변경할 수 없다.

참고로, 이 예시는 살짝 부적절 한데, multiset은 iterator을 이용해 값을 변경할 수 없기에,

cursor을 const_iterator 타입으로 선언하는 것은 부적절 하다. (사용할 수 없다)

 

iterator의 경우에는 크게 5가지가 있다.

1. Forward iterator

이 iterator은 주로 single linked list를 구현할 때 같이 구현한다.

Constructor, Copy constructor, Destructor, Assignment operator overloading을 구현해야 할 수 있으며

(일부는 구현해야 함, 일부는 구현 안해도 됨)

*, ++, ==, != operator overloading을 필수로 구현해야 한다.

 

2. Bidirectional iterator

이 iterator은 주로 binary linked list를 구현할 때 같이 구현한다.

Constructor, Copy constructor, Destructor, Assignment operator overloading을 구현해야 할 수 있으며

(일부는 구현해야 함, 일부는 구현 안해도 됨)

*, ++, ==, != 외에 -- 까지 필수로 구현해야 한다.

 

3. Random Access iterator

Constructor, Copy constructor, Destructor, Assignment operator overloading을 구현해야 할 수 있으며

(일부는 구현해야 함, 일부는 구현 안해도 됨)

*, ++, --, ==, != 외에 +, -, +=, -=도 필수로 구현해야 하며,

[] (array notation)도 구현해야 한다. (여러칸을 이동하게 해주는 +=, -=을 이용하여 구현하면 될 듯..)

 

이 외에도 Input iterator, Output iterator 가 있다.

 

 

이제 구현해보자!

우선 기존에 만들었던 노드 클래스를 약간 수정해준다.

// Before
value_type data() const { return data_field; }
...
node *list_locate(node *head_ptr, size_t position);
const node *list_locate(const node *head_ptr, size_t position);

// After
value_type &data() const { return data_field; }
...
template <class NodePtr, class SizeType>
NodePtr list_locate(NodePtr head_ptr, SizeType position);

기존에 linked list에서 만들었던 노드 클래스에 선언을 위에서 아래와 같이 바꿔준다.

value_type data() const 가 value_type &data()로 바뀐 이유는,

추후 iterator을 구현할 때, * operator overloading 의 리턴값이 &로 리턴하기 때문에 통일시켜 주었다. (사실 잘 모르겠음..ㅜㅜ)

NodePtr로 템플릿화 시켰기 때문에, 포인터를 포함한 const node*, node*를 분리해서 만들 필요가 없고,

하나로만 만들어도 되는 이점이 생긴다.

 

 

다음은 노드 클래스 밖에서 노드 클래스를 위한 iterator 클래스를 정의하자.

template <class Item>
class node_iterator: public std::iterator<std::forward_Iterator_tag, Item> { 
    private:
        node<Item> *current;
        ...
};

node_iterator 클래스는 public std::iterator 클래스에서 상속받아 만들어줄 예정이다.

 

그리고 노드 클래스의 멤버를 정의하면 된다.

single linked list의 iterator을 만들거기 때문에, Forward iterator로 구현하면 된다.

1. Constructor

node_iterator(node<Item> *initial = NULL) {
    current = initial;
}

 

2. * operator

Item &operator*() const {
    return current->data();
}

 

3. ++ operator

// Prefix ++
node_iterator &operator++() {
    current = current->link();
    return *this ;
}

// Postfix ++
node_iterator operator++(int) {
    node_iterator original(current);
    current = current->link();
    return original;
}

위에는 ++iter를 정의한 경우이고, 아래는 iter++를 정의한 경우이다.

아래에서 눈 여겨 봐야 할점은 인자로 int가 들어갔다는 것인데,

이는 int 파라미터가 있다는 뜻이 아니라, postifx 버전의 ++ operator을 만들겠다는 뜻이다.

 

위의 경우는 증가 후 값을 리턴하면 되서 상식적으로 만들었지만 (효율적인 리턴이 가능하고, 리턴 값을 변경할 수 있다는 장점이 있다),

아래의 경우에는 리턴 후 증가해야 해서 약간의 트릭을 썼다.

그래서 리턴 타입을 reference 타입을 쓸 수 없었다.

 

4. ==, != operator

bool operator==(const node_iterator &other) const {
    return current == other.current;
}

bool operator!=(const node_iterator &other) const {
    return current != other.current;
}