[Effective STL] 5. 범위 멤버 함수(Range Member Function)

v1에 v2의 뒤쪽 반을 채우는 가장 빠른 방법은?

v1.assign(v2.begin() + v2.size() / 2, v2.end());

• assign 멤버 함수
  • 컨테이너의 대용을 완전히 교체하고 싶다면 이 함수를 우선적으로 고려하자.
  • 이는 범위(두 반복자를 사용하여 나타내는 요소 묶음) 단위로 동작하는 멤버 함수이다.
• 범위 멤버 함수를 사용하지 않고 이 문제를 풀려면 루프를 사용하지 않을 수가 없다.
  • 직접 루프를 사용하는 건 지양하자. (항목 43 참조)

 

 

 

범위 멤버 함수(range member function)

• 두 개의 반복자를 시작과 끝으로 하는 범위를 매개변수로 하는 멤버 함수를 말한다.

 

 

 

다른 해결법들

• 다른 방법 1. 루프와 단일 요소를 사용한 코드

vector<Widget> v1, v2;
...
v1.clear();
for(vector<Widget>::const_iterator ci = v2.begin() + v2.size() / 2; ci != v2.end())
{
    v1.push_back(*ci);
}

• 다른 방법 2. 알고리즘 함수 사용 (항목 43 참조)

v1.clear();
copy(v2.begin() + v2.size() / 2, v2.end(), back_inserter(v1));
// back_inserter(반복자 어댑터)는 아래에서 추가 설명

 

• 아무래도 이들은 기존 assign 방식에 비해 타자량이 많다.
• 사실, 사용한 방법들은 모두 루프를 사용한다.
  • assign이나 copy 역시 내부적으로는 루프가 숨어있는 방법이다.(항목 43 참조)

 

 

 

 

반복자 어댑터 

• copy에서는 각 요소를 직접 operator=로 삽입하는데, 뒤에 이어서 삽입하려면 다음처럼 귀찮은 과정을 거쳐야 한다.

// v1에 v2의 뒷쪽 절반을 추가한다.
v1.clear();
v1.resize(v2.size() / 2); // 필요한 만큼 공간 확보
copy(v2.begin() + v2.size() / 2,
     v2.end(),
     v1.begin() // 추가를 시작할 반복자 위치
);


// 헌데, 기존 벡터에 이어서 추가하고자 하면?
// 아래처럼 코드가 복잡해진다.
v1.resize(v1.size() + (v2.size() / 2)); // 미리 추가 공간을 확보해야 한다.
copy(v2.begin() + v2.size() / 2,
     v2.end(),
     v1.end() - (v2.size() / 2) // 추가를 시작할 반복자 위치
 );

• 각각 copy 함수의 용법이 다르다.
• 하지만 반복자 어댑터를 쓰면 위 두 상황 모두 이 코드로 정리된다.

copy(v2.begin() + v2.size() / 2, v2.end(), back_inserter(v1));

• 반복자 어댑터의 종류
  • inserter : 컨테이너의 insert 함수를 사용하여 요소 추가
  • back_inserter : 컨테이너의 push_back 함수를 사용하여 요소 추가
  • front_inserter : 컨테이너의 push_front 함수를 사용하여 요소 추가
• 사실, 반복자 어댑터를 사용하는 복사 대상 범위 지정 copy는 범위 멤버 함수로 바꿀 수 있다.(되도록 바꾸자.)

v1.insert(v1.end(), v2.begin() + v2.size() / 2, v2.end());

• 바꾼 코드의 장점
  • copy에 비해 v1에 insert 하고 있다는 의미가 분명해진다.

 

 

 

단일 요소 로직보다 범위 멤버 함수가 더 좋은 이유

• 범위 멤버 함수를 사용한 코드가 대개 짧다.
• 범위 멤버 함수가 훨씬 명확하고 간결하다. 이해가 쉽다.
• 범위 멤버 함수의 성능이 더 좋다.

 

 

 

int 배열을 vector<int>의 앞으로 복사해보자

• 방법 1. vector의 범위 버전 insert를 사용하면 쉽게 해결된다.

int data[numValues];
vector<int> v;
...
v.insert(v.begin(), data, data + numValues); // data를 v 앞에 삽입

• 방법 2. 루프 및 단일 요소로 구현하면 아래와 같을 것이다.

vector<int>::iterator insertLoc(v.begin());
for(int i = 0 i < numValues; ++i)
{
    insertLoc = v.insert(insertLoc, data[i]);
}

• 위 코드에서 insertLoc이 제대로 갱신되지 않으면 생기는 문제
  
  • 루프의 가장 처음에만 제대로 동작했을 것이다.
    • insert로 요소가 삽입되고 나면 기존 반복자는 무효화 되기 때문이다.
  • 만일 무효화되지 않았더라도, 매번 v.begin() 위치에 값을 삽입하므로 data가 역순으로 삽입될 것이다.
• 방법 3. 위 코드의 루프를 copy로 바꾸면 아래와 같을 것이다.(항목 43 참조)

copy(data, data + numValues, inserter(v, v.begin()));

 

 

 

루프 및 단일 요소로 구현된 로직(방법 2)의 비효율 3가지

1. 불필요한 함수 호출
   • v에 numValue개의 요소를 한 번에 하나씩 넣는다.
     • insert가 numValue번 불린다는 의미이다.
   • 물론 인라인 함수라면 생기지 않을 비용이지만..
     • 호출 함수는 인라인 일수도, 아닐 수도 있다.
2. 새로운 요소를 넣기 위해 v에 들어 있던 요소들을 뒤로 미는 비용
   • 새 값을 넣기 위해 요소마다 한 자리씩 뒤로 민다.
   • 이 예제는 int이므로 memmove(메모리를 큰 단위로 옮기는 함수)가 호출되는 것으로 마무리될 수 있지만..
     • v가 복잡한 객체를 담고 있다면 이동 시마다 매번 대입 연산자, 복사 생성자가 호출될 것이다.
   • 반면 표준안에 따르면 범위 기반 insert는 내부 요소를 마지막 위치로 한번에 옮기도록 되어 있다.
     • 사실, 모든 상황의 범위 기반 insert에 사실이라곤 할 수 없다.
       • 두 반복자의 위치를 잃지 않고 그 사이 거리를 알아낼 수 있어야 하는데..
       • 이는 모든 순방향 반복자에서 지원되는 기능이긴 하지만,
       • 입, 출력 반복자는 순방향 반복자를 지원하지 않는다.
       • 즉, insert에 입력 반복자(예컨대 istream_iterator) 같은 게 넘겨졌을 때는 거짓인 셈.
3. 벡터의 메모리 할당
   • 메모리가 꽉 찬 벡터에 새 요소를 넣으려고 하면
     • 벡터는 메모리가 두 배가 되도록 재할당된다.(항목 14 참조)
   • 만약 numValue개의 새 요소를 삽입하려고 하면 log₂numValue 번 하게 된다는 의미이다.
   • 하지만 범위 버전 삽입 함수는 삽입 전에 필요한 메모리량을 예측할 수 있으므로 메모리 할당을 여러번 반복할 필요가 없다.

 

 

 

표준 시퀀스 컨테이너 전체로 보자면?

• 위에서는 vector가 예시였지만 string도 완전히 동일하다.
• deque는 메모리 재할당 외 나머지는 일반적으로 맞다.
• list도 불필요한 함수 호출 부분만 맞다.
  • 허나, 뒤로 미는 비용 대신 노드의 포인터 설정에서 비용이 발생한다.

 

 

 

list에서 insert 시 노드 포인터 설정 비용

• 리스트에 요소가 추가되면..
  1. 새 노드의 next 포인터와 prev 포인터를 갱신하여 앞 뒤 노드를 설정한다.
  2. 앞 노드는 next 포인터를, 뒤 노드는 prev 포인터를 갱신한다.

• insert 함수로 단일 요소를 한번에 하나씩 넣는다면?
  • 가장 마지막에 삽입하는 노드 외의 노드들은 계속해서 next 포인터를 업데이트 해야 한다.
    • 처음 삽입 시, 노드 A를 가리키는 포인터가 되었다가
    • 다음 노드를 삽입하면 이전에 삽입한 이 노드의 next는, 새 노드를 가리키도록 갱신되어야 하므로.
  • 노드 A 역시 prev 포인터를 끊임없이 갱신해줘야 한다.
    • 새로 들어오는 노드의 포인터로 계속해서 갱신되어야 한다.
  • 즉, 한번만 설정하면 될 포인터(next 포인터)가 두 번씩 업데이트 된다.
• 삽입된 노드의 next 포인터와 A의 prev 포인터가 각각 (추가하는 요소 갯수 - 1) 번이나 쓸데없이 갱신된다.
• 그러므로 list의 범위 버전 insert를 사용하는 것이 좋다.
  • 이 함수는 최종적으로 삽입될 노드의 개수를 파악할 수 있으므로 불필요한 포인터 세팅을 피한다.

 

 

 

연관 컨테이너에서는 어떨까?

• 반복 함수 호출 오버헤드는 분명히 있다.
• 하지만, 다른 효율적 부분은 딱 부러지게 그렇다고 말하기 힘든 부분이 있다.

 

 

 

범위 버전 컨테이너 함수 정리

• 참고
  
  • 매개 변수 타입 iterator는 컨테이너의 반복자를 뜻한다.
  • InputIteractor는 어떤 입력 반복자도 받을 수 있다는 뜻이다.
• 범위 생성(Range Construction)
  • 모든 표준 컨테이너는 다음 형태의 생성자를 지원한다.

  • container::container(InputIteractor begin, InputIterator end);

  • 여기에 istream_iteractor나 istreambuf_iterator를 넘기면 컴파일러가 잘못 해석한다.(항목 29 참조)
    • 컨테이너 객체의 정의가 아니라 함수 선언으로 이해한다.(항목 6 참조)
• 범위 삽입(Range Insertion)
  • 모든 표준 컨테이너는 다음 형태의 insert를 지원한다.

  • void container::insert(iterator position, // 범위 삽입 위치
                           InputIteractor begin, // 삽입할 범위 시작
                           InputIterator end); // 삽입할 범위 끝
                           
    // 연관 컨테이너는 컨테이너 내부 비교 함수로 요소 위치를 결정하므로
    // 위치 매개 변수를 받지 않는다.
    void container::insert(InputIteractor begin, // 삽입할 범위 시작
                           InputIterator end); // 삽입할 범위 끝

• 범위 삭제(Range Erasure)
  • 이 함수의 반환 타입은 시퀀스 컨테이너와 연관 컨테이너 각각이 다르다.
    • C++11에서는 개선된 사항이다.

  • // 시퀀스 컨테이너
    iterator container::erase(iteractor begin, iterator end);
    
    // 연관 컨테이너
    // 허나 C++11 부터는 연관 컨테이너도 반복자를 반환하게 변경.
    void container::erase(iterator begin, iterator end);

  • 왜 다르냐?
    • 연관 컨테이너가 iterator를 반환하면 수행 성능 저하가 있을 수 있다고 표준안은 말하고 있다.
  • erase와 remove를 함께 사용하는 erase-remove idiom에서 범위 버전 erase의 특성을 확실히 볼 수 있다.(항목 32 참조)
• 범위 대입(Range Assignment)
  • 모든 표준 시퀀스 컨테이너는 범위 버전 assign을 제공한다.

  • void container::assign(InputIterator begin, InputIterator end);