C++ STL Algorithm

1. Algorithm

- sequence container에서 동작 가능한 알고리즘들이 들어있다.

- find(), sort(), min(), binary_search()등등이 있다.

2. sort (built in)

- sort는 vector와 deque에서 사용가능하다.

- List에서는 사용이 불가한데 이는 sort가 general하게 O(nlogn)으로 동작하도록 하기 위해서는 random access가 필요하기 때문이다.

- 따라서 random access가 가능한 vector나 deque같은 random access sequence container에서만 동작한다.

3. sort (user defined class)

- 위의 예시는 built in type의 sort를 수행하였는데 만약 내가 원하는 타입에서 동작하게 하려면 어떻게 해야 할까?

- vector에 사용자가 직접 정의한 Student class가 들어가 있다고 하자.

- sort가 가능하게 하려면 먼저 student element들의 순서를 반환해주는 comp_student를 정의할 필요가 있다.

- 그다음 sort의 세번째 parameter로 넘겨준다.

- 이렇게해야 sort가 element들끼리 비교를 해서 전후 관계를 알 수 있다.

 

- 또 다른 방법은 operator overloading을 활용하는 것이다.

- 아래 코드처럼 sort가 동작하도록 하려면 student class에 <연산자 오버로딩을 해준다.

4. find (built in type)

5. find (user defined class)

- 참고로 사용자가 정의한 class type의 element들의 vector에서 find가 동작하게 하려면 어떻게 하면 될까?

- Student(3, "Mike")와 3을 비교할 수 있도록 하는 ==연산자를 오버로딩 해주면 될 것이다.

- Find함수에서 == 연산자를 통해 같음을 확인하기 때문에 == 를 오버로딩 해준다.

6. find if

- find와 비슷한데 value를 넘겨서 같은 element를 찾는게 아니라 함수를 넘겨서 true를 반환하는 element를 찾는다.

7. Transform

- foo에서 (임의의)시작, (임의의)끝 iterator를 넘겨주고 bar에서 원하는 위치에 시작 interator를 넘겨준다. 그리고 새롭게 정의한 함수를 넣어주면 foo에서 꺼낸 element들을 op_increase를 거치게하여 나온 결과들을 bar에 담는다.

- 첫번째 두번째 인풋으로 range를 알고 있기때문에 bar의 끝 iterator는 알려주지 않아도 된다.

- plus가 들어간 transform 문장을 살펴보자. pluss는 두개의 element를 필요로하기 때문에 이전과 해석에서 약간 차이를 보인다.

- 첫번째, 두번째 인자는 전달할 vector이고 bar.begin()은 앞서 전달한 element와 함께 더할 element이다. 그렇게 더한 값들을 foo.begin()부터 다시 저장한다.