[C++ Primer Plus] Chapter 16. (2) STL - 이터레이터

Table of Contents

C++ 기초 플러스 책을 읽고 공부한 노트입니다.

표준 템플릿 라이브러리 #

표준 템플릿 라이브러리(STL; Standard Template Library)
- 객체 지향이 아니다. 일반화 프로그래밍(generic programming)이라는 패러다임을 나타낸다.
- 1. 컨테이너(container)
  - 배열 같이, 여러 개의 값을 저장할 수 있는 구성 단위.
- 2. 알고리즘(algorithm)
  - 배열을 정렬하거나, 리스트에서 특정 값을 검색하는 것과 같이, 특별한 작업들을 수행하기 위한 방법.
- 3. 이터레이터(iterator)
  - 배열 안에서 포인터를 사용해서 위치를 옮기듯이, 컨테이너 안에서 위치를 옮길 수 있도록 도와주는 객체.
  - 즉, 포인터의 일반화이다.
- 4. 함수 객체(function object)
  - 함수와 비슷한 역할을 하는 객체.
  - 클래스 일수도 있고, 함수 포인터일 수도 있다.

vector 컨테이너 클래스 #

vector 컨테이너 클래스
- vector 헤더파일에 정의되어 있다.

// 메모리 관리에 사용할 allocator 객체를 선택적으로 지정할 수 있다.
// allocator 클래스는 new와 delete를 표준방식으로 사용한다. 
template<class T, class Allocator = allocator<T>>
class vector
{
    //...
};

생성
- 동적 메모리 대입을 사용한다.
- 원소 개수를 지정하기 위해 초기화 매개변수를 사용할 수 있다.
접근
- [] 연산자로 개별 원소에 접근할 수 있다.
할 수 있는 것
- size()
  - 원소 개수 리턴
- swap()
  - 두 컨테이너 내용을 교환
- begin()
  - 컨테이너에 있는 첫 번째 원소를 참조하는 이터레이터를 리턴
- end()
  - 컨테이너에 있는 마지막 원소 바로 다음(past-the-end)을 참조하는 이터레이터를 리턴
- push_back()
  - 벡터의 끝에 원소를 하나 추가
- erase()
  - 매개변수로 2개의 이터레이터를 받는다.
  - 첫 번째 이터레이터가 가리키는 곳부터 두 번째 이터레이터 전까지를 삭제한다. (두 번째 이터레이터 포함 안 함)
- insert()
  - 매개변수로 3개의 이터레이터를 받는다.
  - 첫 번째 이터레이터 앞에 원소들이 삽입된다.
  - 두 번째 이터레이터가 가리키는 곳부터 세 번째 이터레이터 전까지 추가된다. (세 번째 이터레이터 포함 안 함)

이터레이터
- 단순 포인터를 가지고는 동작시킬 수 없는 클래스를 포함하여, 다양한 컨테이너 클래스들에 일관된 인터페이스를 제공할 수 있다.
- 각 컨테이너 클래스는 하나의 적절한 이터레이터를 정의한다. 데이터형 이름은 iterator이며, 클래스 사용범위를 가지는 typedef이다.

vector<int> scores {0, 2, 3, 4, 5};

vector<int>::iterator vi; // vector<int>를 위한 이터레이터
vi = scores.begin();      // 이터레이터가 첫번째 원소를 가리키게 한다.

auto va = scores.begin(); // C++11의 자동 타입 추론을 사용할 수도 있다. 

*vi = 1;                  // 이터레이터 내용을 참조하여 값을 변경한다. 
++vi;                     // 이터레이터가 다음 원소를 가리키게 한다. 

// end()에 도달하면 그만두는 방식으로 모두 출력할 수 있다. 
for (vi = scores.begin(); vi != scores.end(); vi++)
    cout << *vi << " ";

할 수 있는 그 밖의 것
- 검색하고, 정렬하고, 순서를 무작위화하는 등의 작업을 vector 템플릿 클래스에서 메서드로 가지고 있을까?
  - 아니다. STL은 좀 더 넓은 시각으로, 이러한 연산들을 멤버가 아닌 함수로 정의한다.
  - 예를 들면, 모든 컨테이너 클래스에서 사용할 수 있는 멤버가 아닌 하나의 find()함수를 정의하는 것이다.
- 대표적인 STL 함수인 세 가지를 살펴보자.
  - for_each()
  - random_shuffle()
  - sort()

for_each() 함수
- 3개의 매개변수를 받는다.
  - 첫 번째와 두 번째 매개변수는 범위를 정한다.
  - 세 번째 매개변수는 함수 객체이다.
- 지시된 함수를 그 범위 안에 있는 각 컨테이너 원소에 적용한다.
- 지시된 함수는 컨테이너 원소들의 값을 변경하면 안 된다.

struct Review
{
    string title;
    int rating;
};

void ShowReview(const Review& r)
{
    cout << r.title << " " << r.rating << endl;
}

int main()
{
    vector<Review> books = {
        {"Harry Potter", 10},
        {"Hole", 9},
    };

    // for문을 사용한다.
    for (auto pr = books.begin(); pr != books.end(); pr++)
        ShowReview(*pr);

    // for_each를 사용해서 이렇게 바꿀 수 있다.
    for_each(books.begin(), books.end(), ShowReview); // 함수는 값을 변경하지 않는다. 
}

random_shuffle()
- 2개의 이터레이터 매개변수를 받는다.
- 그 이터레이터 범위 안에 있는 원소들을 무작위 순서로 재배치한다.

random_shuffle(books.begin(), books.end());

sort()
- 두 가지 버전이 있다.
- (1) 2개의 이터레이터 매개변수를 받는다.
  - 컨테이너의 데이터형에 맞게 정의된 <연산자를 사용하여 그 범위를 정렬한다.
  - 만약 데이터형이 사용자 정의 객체라면 operator<()함수가 있어야한다.
- (2) 3번째 매개변수를 받는다.
  - 값을 비교하기 위한 operator<() 대신에 사용할 함수 객체이다.

bool operator<(const Review& r1, const Review& r2)
{
    return r1.rating < r2.rating; // 오름차순
}

bool WorseThan(const Review& r1, const Review& r2)
{
    return r1.rating > r2.rating; // 내림차순
}

int main()
{
    vector<int> coolstuff;
    sort(coolstuff.begin(), coolstuff.end()); // 내장된 < 연산자 사용

    sort(books.begin(), books.end());  // 데이터형에 맞게 정의된 operator<() 사용 (1)
    
    sort(books.begin(), books.end(), WorseThan); // WorseThan함수 사용 (2)
}

Range에 기초한 루프 (C+11)

for_each(books.begin(), books.end(), ShowReview); // ShowReivew는 값변경 안 된다. 
    
for (auto r : books)
    ShowReview(r);     // 값 변경 할 수 있다.

이터레이터(iterator) #

템플릿이 알고리즘을 저장할 데이터형과 무관하게 만드는 것처럼,
이터레이터는 알고리즘을 사용할 컨테이너형과 무관하게 만든다.
- double 배열과 링크드 리스트에서 원하는 값을 찾는 Find()함수를 만들면서 이터레이터에 대해 알아보자.
- 특정한 구조에 매여 있지 않으면 좋겠다. 따라서 다음과 같이 만들어보았다.
- 여기서 두 Find()함수의 유일한 다른점은 검색을 멈추는 마지막 지점이다.
  - past-the-end원소를 링크드 리스트도 갖게 한다면, 두 Find()함수는 똑같아진다.
  - 따라서 각 클래스를 위한 적절한 이터레이터를 정의하고 클래스들을 일관된 방식으로 설계하면, STL을 사용하여서 동일한 코드를 작성할 수 있다.

// 배열의 경우
// 포인터로 정의한다.
typedef double* iterator;

iterator FindAr(iterator begin, iterator end, const double& target)
{
    // 배열의 끝 바로 다음 포인터인 end가 아닐 때까지 진행한다. 
    for (iterator it = begin; it != end; it++)
        if (*it = target)
            return it;
    return end;
}

// 링크드 리스트의 경우
struct Node
{
    double item;
    Node* next;
};

// 객체로 정의한다.
class iterator
{
    Node* pt;
    
public:
    iterator() : pt(nullptr) {}
    iterator(Node* pn) : pt(pn) {}
    
    double operator*() { return pt->item; }
    
    // ++iterator
    iterator& operator++()
    {
        pt = pt->next;
        return *this;
    }
    
    // iterator++ (매개변수 int는 사용되지 않기때문에 이름을 부여할 필요가 없다)
    iterator operator++(int)
    {
        iterator temp = *this;
        pt = pt->next;
        return temp;
    }
    
    // ...
};

iterator FindLl(iterator begin, const double& target)
{
    // 마지막인 널 포인터가 아닐 때까지 진행한다. 
    for (iterator it = begin; it != 0; it++)
        if (*it = target)
            return it;
    return 0;
}

이터레이터의 종류
- 1. 입력 이터레이터(input iterator)
- 2. 출력 이터레이터(output iterator)
- 3. 전방 이터레이터(forward iterator)
- 4. 전후방 이터레이터(bidirectional iterator)
- 5. 임의 접근 이터레이터(random access iterator)
알고리즘이 다르면 이터레이터의 종류가 다르다. 예를 들어, 검색의 경우 쓰기는 금지하고 읽기 접근만 허용해야 하며, 원소 교환의 경우 임의 접근을 허용해야 한다.
요구 사항이 가장 적은 이터레이터를 사용하여 알고리즘을 작성함으로써, 가장 넒은 범위의 컨터에너들에 사용할 수 있도록 하기 위해 여러 가지 종류의 이터레이터가 존재한다.
따라서 find()의 경우, 읽을 수 있는 값이 들어 있는 어떠한 컨테이너들에도 사용할 수 있겠다.
vector<int>클래스는 임의 접근 이터레이터를 사용하며, list<int>클래스는 전후방 이터레이터를 사용한다.

// 입력 이터레이터를 요구하는 함수 find()
template<class InputIerator, class T>
InputIerator find(InputIerator first, InputIerator last, const T& value);

// 임의 접근 이터레이터를 요구하는 함수 sort()
template<class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);

1. 입력 이터레이터

컨테이너로부터 값을 읽는 것을 허용한다. 하지만 변경하는 것은 허용하지 않는다.
입력 이터레이터가 이미 증가된 후에, 증가되지 전 값을 내용 참조할 수 있다는 보장이 없다. 이렇게 입력 이터레이터에 기초를 둔 알고리즘은 일회성이며, 일방향적이다.
즉, 증가시킬 수는 있지만 되돌릴 수는 없다.

2. 출력 이터레이터

값을 변경하는 것을 허용하지만, 읽는 것은 허용하지 않는다.
이것은 cout을 생각해보면 된다. cout은 디스플레이로 보내지는 문자들의 스트림을 변경할 수 있지만, 화면에 표시된 것을 읽지는 못한다.
쓰기 전용 일회성 알고리즘에 사용할 수 있다.

3. 전방 이터레이터

입/출력 이터레이터와 마찬가지로 전방 이터레이터도 컨테이너 속을 훑고 지나가기 위해 ++연산자만 사용한다.
다른 점
- 전방 이터레이터는 사용할 때마다 연속된 값들을 반드시 같은 순서로 훑고 지나간다.
- 증가된 후에도 (저장해 두었다면) 그 이전 이터레이터 값을 내용 참조하여 항상 같은 값을 얻을 수 있다. 따라서 다중 패스 알고리즘이 가능해진다.

4. 전후방 이터레이터

전방 이터레이터가 가지고 있는 모든 기능에 감소 연산자(전방, 후방)에 대한 기능을 추가한다.
예를 들어, 뒤집기(reverse) 함수는 첫 번째 원소와 마지막 원소를 맞바꾸고, 첫 번째 원소를 지시하는 포인터는 증가시키고, 마지막 원소를 지시하는 포인터는 감소시킨다.

5. 임의 접근 이터레이터

전후방 이터레이터가 가지고 있는 모든 기능에 임의 접근을 지원하는(포인터 덧셈 등) 연산과, 원소들의 순서를 매기는 데 사용할 관계 연산자들을 추가한다.
예를 들어, 이진 탐색(binary search)의 경우 임의 원소로 직접 점프가 가능해야 한다.
임의 접근 이터레이터 연산
- a, b는 이터레이터이다. n은 정수이며 r는 임의 접근 이터레이터 변수/참조이다.
- a + n과 같은 식은 a와 a + n이 둘 다 컨테이너의 범위 안에 있을 때만 유효하다.

식	설명
`a + n`, `n + a`	`a`가 지시하는 원소로부터 `n`번째 뒤의 원소를 지시한다.
`a - n`	`a`가 지시하는 원소로부터 `n`번째 앞의 원소를 지시한다.
`r += n`	`r = r + n`과 같다.
`r -= n`	`r = r - n`과 같다.
`a[n]`	`*(a + n)`과 같다.
`b - a`	`b = a + n`과 같은 경우에 `n`의 값
`a < b`	`b - a > 0`이면 `true`
`a > b`	`b < a`이면 `true`
`a >= b`	`!(a < b)`이면 `true`
`a <= b`	`!(a > b)`이면 `true`

이터레이터 계층

이터레이터 기능	입력	출력	전방	전후방	임의 접근
내용 참조하여 읽기	O	X	O	O	O
내용 참조하여 쓰기	X	O	O	O	O
고정 반복 가능한 순서	X	X	O	O	O
`++i`, `i++`	O	O	O	O	O
`--i`, `i--`	X	X	X	O	O
`i[n]`	X	X	X	X	O
`i + n`	X	X	X	X	O
`i - n`	X	X	X	X	O
`i += n`	X	X	X	X	O
`i -= n`	X	X	X	X	O

개념(concept)
- 요구 사항의 집합
개량(refinement)
- 개념적인 상속
- 예를 들어, 전후방 이터레이터는 전방 이터레이터의 기능을 상속한다. 하지만 C++의 일반적인 상속과는 다르다. 이것들은 내장 데이터형이기 때문에 클래스로부터 파생시킬 수가 없다. 따라서 이런 것을 개념적인 상속인 개량이라고 부른다.
모델(model)
- 어떤 개념의 특별한 한 구현
- 예를 들어, int를 지시하는 단순 포인터는 임의 접근 이터레이터 개념의 한 모델이다. 또한 전방 이터레이터 개념의 모델이기도 하다.

이터레이터 자격의 포인터
- 이터레이터는 포인터를 일반화한 것이다.
- 따라서 STL알고리즘은 포인터에 기초를 두고 있는 STL이 아닌 컨테이너들에 적용할 수 있다.

const int SIZE = 10;
double arr[SIZE];

sort(arr, arr + SIZE);  // (O)

copy()
- 하나의 컨테이너에서 다른 컨테이너로 데이터를 복사하는 알고리즘.
- 첫 번째와 두 번째 매개변수로 범위를 지정하고,
- 세 번째 매개변수로 복사할 위치를 지정한다.
- 이것은 목적지의 크기를 자동으로 조절하지 않는다. (뒤에 볼 insert_iterator 등을 사용하면 가능하다. )

int arr[5] = {1, 2, 3, 4, 5};
vector<int> vec[5];   // 빈 벡터에는 복사할 수 없다. 

copy(arr, arr + 5, vec.begin());  // arr의 인덱스 0~4를 vec의 인덱스 0지점에 복사한다.

디스플레이에 복사하려면?
- 출력 스트림을 나타내는 이터레이터가 있으면 가능하겠다.
- STL은 ostream_iterator을 제공한다. 이것은 출력 이터레이터 개념의 모델이다.

#include <iterator>


ostream_iterator<int, char> outIterator(cout, " ");
// int는 출력 스트림으로 보내는 데이터형이다. 
// char는 출력 스트림이 사용하는 데이터형이다.
// cout은 cout이 관리하는 출력 스트림을 사용한다는 뜻이다. 
// " "은 출력 스트림에 보내진 각 항목 뒤에 표시되는 분리자이다.  

*outIterator++ = 15;  // cout << 15 << " "; 와 같다. 

copy(vec.begin(), vec.end(), outIterator);  // 벡터를 출력 스트림에 복사한다. 


// 혹은 익명 이터레이터를 만들 수도 있다. 
copy(vec.begin(), vec.end(), ostream_iterator<int, char>(cout, " "));

istream_iterator
- 같은 논리로, 입력을 위한 istream_iterator가 입력 이터레이터 개념의 모델이다.

copy(istream_iterator<int, char>(cin), istream_iterator<int, char>(), vec.begin())  // 입력

// int는 읽을 데이터형이다.
// char는 입력 스트림이 사용하는 데이터형이다. 
// cin은 cin이 관리하는 입력 스트림을 사용한다는 뜻이다. 
// 매개변수를 생략하는 것은 입력 실패를 나타낸다. 
// 따라서 파일 끝, 데이터형 불일치 등의 입력 실패가 일어날 때까지 데이터를 읽는다는 뜻이다.

reverse_iterator
- 이것을 증가시키면, 실제 내용은 감소한다.
- rbegin()은 past-the-end를 지시하며, rend()는 첫 번째 원소를 지시한다.
- 특이한 점은 역방향 포인터들은 먼저 감소시킨 후에 내용 참조를 한다는 점이다.
- 따라서 다음 코드와 같이 하면, 벡터를 뒤에서 부터 거꾸로 출력한다.

// 암시적 사용
copy(vec.rbegin(), vec.rend(), outIterator); // 마지막 원소 ~ 처음 원소 출력

// 명시적 사용
vector<int>::reverse_iterator ri;
for (ri = vec.rbegin(); ri != vec.rend(); ++ri)
    cout << *ri << " ";

추가적인 출력 이터레이터 개념의 모델들…
front_insert_iterator
- 컨테이너 선두에 원소들을 삽입한다.
- 선두에 삽입하는데 고정 시간이 걸리는 컨테이너형에만 사용할 수 있다.
end_insert_iterator
- 컨테이너 말미에 원소들을 삽입한다.
- 멀미에 삽입하는데 고정 시간이 걸리는 컨테이너형에만 사용할 수 있다.
insert_iterator
- 매개변수로 지정된 위치 앞에 원소들을 삽입한다.
- 시간 제한은 없다. 대신 다른 것들에 비해 좀 느리다.

이와 같은 모델들은 생성자 매개변수로 실제 컨테이너 식별자를 사용한다.
- copy()는 컨테이너 크기를 조절하는 권한이 없다.
- 하지만 이 모델들은 아래와 같이 컨테이너형을 선언하여서 vector<int>::push_back()에 접근이 가능하며, 따라서 컨테이너 크기를 조절할 수 있다.

back_insert_iterator<vector<int>> backIterator(vec);

insert_iterator<vector<int>> insertIterator(vec, vec.begin());
// vec.begin()은 삽입될 위치이다.

string strs[5] = { "A", "B", "C", "D", "E" };
vector<string> words = { "a", "b", "c", "d", "e" };

copy(strs, strs + 2, back_insert_iterator<vector<string>>(words));
// str의 0 ~ 1인덱스에 있는 "A", "B"를 words벡터 뒤에 삽입한다.
// a b c d e A B

copy(strs, strs + 2, insert_iterator<vector<string>>(words, words.begin() + 2));
// str의 0 ~ 1인덱스에 있는 "A", "B"를 words의 인덱스 2 위치 부터 삽입한다.
// a b A B c d e