[ 혼연 정리 ] STL 알고리즘 - 3 [ 변경 알고리즘 ]

 ㅇ 변경 알고리즘
 - 컨테이너의 요소를 바꿀 수 있다.
 - 요소의 값만 변경, 컨테이너 자체에 대해서 어떠한 조작도 하지 못한다
 - 요소를 제거하거나 새로운 요소를 삽입한다거나 크기 변경 불가능

 ※ 알고리즘이 컨테이너에 접근하는 유일한 방법은 반복자를 통하는 것 뿐이며 반복자는 컨테이너의 요소를 엑서스하는 일반화된 방법을 제공할 뿐이지 컨테이너
     자체를 엑세스 하는 것이 아니다. 알고리즘이 일반성을 획득할 수 있는 이유는 반복자를 통해서만 컨테이너의 요소를 엑세스하므로 컨테이너의 구조를 몰라도
     약속된 방법(주로 연산자)만으로도 하고 싶은 동작을 다 할 수 있기 때문이다.  알고리즘은 자신이 액세스하는 컨테이너가 어떤 구조를 가지고 있는지 상관하지 않으며 내부적인 구조에 상관없이 실행된다. 심지어 어떤 컨테이너를 조작하고 있는 중인지도 전혀 모른다. 따라서 컨테이너에 새 요소를 어떻게 삽입하는지도 모르고, 삭제하는 방법도 알지 못하는 것이다. 알고리즘이 컨테이너에 대해 할 수 있는 일은 요소값을 변경하거나 복사, 교환하는 정도에 불과하다. 컨테이너 자체에 대한 조작은 개별 컨테이너의 멤버 함수를 통해서만 수행할 수 있다.

ㅇ copy
 - 지정한 구간을 복사하는데 주로 일부 요소들을 다른 컨테이너로 복사하고 싶을 때 사용한다.
 - 같은 타입의 컨테이너 전체를 복사하려면 copy 함수를 쓸 필요없이 컨테이너의 =연산자로 대입해 버리면 된다.
 - 복사 방향에 따라 두개의 함수가 정의 되어 있다.

OutIt copy(InIt first, InIt last, OutIt result);
BiIt copy_backward(BiIt first, BiIt last, BiIt result); 

 - copy 함수는 first ~ last 사이의 모든 요소를 result 반복자 위치 이후에 복사한다.
 - result 이후 last ~ first만큼의 기억 장소가 미리 확보되어 있어야 한다.
 - 반복자는 같은 컨테이너의 다른 부분일수도 있지만 다른 컨테이너의 박복자 구간끼리도 복사 가능

 1 #include <iostream>
2 #include <algorithm>
3
4 using namespace std;
5
6 void main()
7 {
8
9      char src[]="1234567890";
10      char dest[]="abcdefghij";
11
12      copy(&src[3],&src[7],&dest[5]);
13      puts(dest);
14 }
15

- 위의 예제의 복사 목적지를 dest[9]로 변경하면 배열 뒤쪽을 덮어 쓰므로 다운이 된다.

- 이럴 때 삽입 반복자를 사용하면  복사와 동시에 요소를 삽입할 수 있다.

1 #include <iostream>
2 #include <list>
3 #include <algorithm>
4
5 using namespace std;
6
7 template<typename C>
8 void dump(const char *desc, C c)

9 {
10     cout.width(12);cout << left << desc << "==> ";
11     copy(c.begin(),c.end(),ostream_iterator<typename C::value_type>(cout," "));
12     cout << endl;
13 }
14
15 void main()
16 {
17     char src[]="1234567890";
18     list<char> li;
19
20     copy(&src[3],&src[7],back_inserter(li));
21     dump("list",li);
22 }

- li 리스트는 빈 상태로 생성되어서 기억 장소를 확보하지 않았지만 back_inserter 반복자가 대입 동작을 push_back 삽입 동작으로 재정의하므로  리스트의 크기가 늘어난다.

- 같은 컨테이너끼리도 복사할 수 있다. 이때 복사 방향에 신경 써야 한다.
- copy는 first에서 부터 시작해서 last로 이동하면서 한 요소씩 순서대로 복사하는데 원본과 목적 구간이 겹쳐 있으면 원본이 앞쪽 복사에 의해 읽기도 전에 파괴되는 문제가
  있다.
- 그래서 역방향으로 진행하면서 복사하는 copy_backward 함수가 따로 있다.

 1 #include <iostream>
2 #include <list>
3 #include <algorithm>
4
5 using namespace std;
6
7 template<typename C>
8 void dump(const char *desc, C c)

9 {
10     cout.width(12);cout << left << desc << "==> ";
11     copy(c.begin(),c.end(),ostream_iterator<typename C::value_type>(cout," "));
12     cout << endl;
13 }
14
15 void main()
16 {
17      int i;
18      list<int> li,li2;
19      list<int>::iterator first,last,result,it;
20
21      for (i=0;i<10;i++) li.push_back(i);
22      li2=li;
23
24      dump("복사전",li);
25      first=find(li.begin(),li.end(),2);
26      last=find(li.begin(),li.end(),7);
27      result=find(li.begin(),li.end(),3);
28      copy(first,last,result);
29      dump("copy",li);
30
31      first=find(li2.begin(),li2.end(),2);
32      last=find(li2.begin(),li2.end(),7);
33      result=find(li2.begin(),li2.end(),8);
34      copy_backward(first,last,result);
35      dump("back",li2);
36 }

- 역방향은 복사할 때는 원본이 먼저 복사되고 다른 값을 대입받으므로 순방향 처럼 복사가 되지 않는다.
- result가 복사 목적지의  시작점이 아니라 끝 다음점이어야 한다는 점도 다르다

1 #include <iostream>
2 #include <vector>
3 #include <algorithm>
4
5 using namespace std;
6
7 template<typename C>
8 void dump(const char *desc, C c) 9 {
10     cout.width(12);cout << left << desc << "==> ";
11     copy(c.begin(),c.end(),ostream_iterator<typename C::value_type>(cout," "));
12     cout << endl;
13 }
14
15 void main()
16 {
17      int i;
18      vector<int> vi,vi2;
19      for (i=0;i<10;i++) vi.push_back(i);
20      vi2=vi;
21
22      dump("복사전",vi);
23      copy(vi.begin()+2,vi.begin()+7,vi.begin()+3);
24
25      dump("copy",vi);
26
27      copy_backward(vi2.begin()+2,vi2.begin()+7,vi2.begin()+8);
28      dump("back",vi2);
29 }

- 똑같은 소스를 작성했는데 벡터의 경우는 복사 방향에 상관없이 잘 동작한다.
- 데크에 대해 작성해보면 리스트와 마찬가지로 방향이 잘못되면 원본이 파괸다.
- 벡터가 복사 방향에 상관없이 잘 복사되는 이유는 구현 방식과 관련있다.
 - 벡터는 요소들이 인접해 있는 구조를 가지고 있으므로 더 빠른 복사를 위해  memmove 함수 또는 그에 준하는 메모리 복사 함수를 사용한다.
 - 이 함수는 cpu의 메모리 이동 코드를 호출하는 데 cpu가 복사 방향에 따라 순서를 적절하게 조정하기 때문에 겹치더라도 잘 동작한다.
- 리스트의 경우는 리스트의 노드는 메모리의 도처에 흩어져 잇어 반복자만으로 앞뒤 순서를 판단할 수 없기 때문에 사용자가 수동으로 복사 방향을 선택해야 한다.
 - 대부분 컴파일러에서는 벡터는 복사 방향에 상관없도록 구현되어 있지만  STL 스팩에 그렇게 구현해야 한다고 되어 있지는 않으므로 방향에 맞는 함수를 선택해서 사용하는
   것이 바람직하다.

ㅇ void swap(T& x, T& y);
- 내부 알고리즘  : T =a ; a = b ; b = T
- 기본 타입 및 컨테이너에서 사용가능
- 대입 연산이 느린 경우는 특수화된 함수가 호출됨
 - 대부분의 컨테이너 타입에 대해 특수화 되어 있어 컨테이너의 구조에 딱 맞는 교환 멤버 함수가 호출된다.

ㅇ FwdIt2 swap_ranges(FwdIt1 first1, FwdIt1 last1, FwdIt2 first2);
 - 반복자 끼리 교체한다.
 - first1 ~ last1 사이를 first2구간과 바꾼다
 - 다른 컨테이너의 반복자 구간끼리도 값을 교환할 수 있다.
 - 동일 컨테이너 내의 교환인 경우 반복자 구간이 겹쳐서는 안된다.