C++ STL 프로그래밍(알고리즘)

10. 알고리즘



10.1 STL 알고리즘 분류
    1) 변경 불가 시퀀스 알고리즘(find, for_each)
    2) 변경 가능 시퀀스 알고리즘(copy, generate)
    3) 정렬 알고리즘(sort, merge)
    3) 범용 수치 알고리즘(accumulate)


10.2 조건자
    - 알고리즘 중 기본 자료형이 아닌, 함수를 파라미터로 받는것이 많다.
    - 사용자 정의형 자료형(struct, class)을 담는 컨테이너를 알고리즘에서 사용하기 위해서는 관련 함수를 만들어 파라미터로 넘겨야 한다.
    - 알고리즘에서 파라미터로 넘기는 함수는 보통 함수보다 함수 객체를 사용한다.


10.3 변경 불가 시퀀스 알고리즘
    - find, find_if, for_each, count, search, equal, adjacent_find, equal 등

    10.3.1 find
        - 컨테이너 내 원하는 데이터 찾기
        - #include <algorithm> 헤더  추가
        
        - 첫 번째 파라미터: 찾기 시작할 반복자 위치
        - 두 번째 파라미터: 찾을 마지막 위치
        - 세 번째 파라미더: 찾을 값
        - 찾기 성공하면 데이터가 있는 위치를 가리키는 반복자 리턴, 실패하면 end() 리턴
        - vector, list, deque 에 사용 가능
        - 단, 기본 자료형을 값으로 받는 컨테이너에서만 사용할 수 있다.
        - map, set, hash_map은 해당 컨테이너의 멤버로 find()가 있다.


    10.3.2 find_if
        - 유저 정의 자료형을 저장하는 컨테이너에서 사용
        
        - find와 세번째 파라미터만 다름(조건자를 넘긴다)

        
        
        - 조건자 함수를 함수 포인터가 아닌 함수 객체를 사용한 예시
        - 함수 객체는 inline화 되므로 함수 포인터 참조와 호출 작업이 필요 없다.
        - 함수 객체는 특정 데이터를 저장할 수 있어 조건자가 유연해진다.
        - 조건자를 일반 함수로 만들었다면 비교할 CompareMoney값은 함수 정의 시 고정
        - 조건자를 함수 객체로 만들면 객체를 생성할 때 CompareMoney의 값을 설정할 수 있어 유연


    10.3.3 for_each
        
        - 지정 구간 내의 컨테이너에 조건자에 지정한 데이터를 함수의 파라미터로 넘겨 실행하는 알고리즘
        
        
        - for_each 사용 예시


10.4 변경 가능 시퀀스 알고리즘
    - 컨테이너에 복사, 삭제 대체 등 가능
    - generate, copy, remove, replace, fill, swap, reverse, transform 등

    10.4.1 generate
         - 특정 구간을 동일한 값으로 채우는 assign(), 다른 값 채우기 generate
        
        - 첫 번째 파라미터: 컨테이너 시작 위치의 반복자
        - 두 번째 파라미터: 마지막 위치 반복자
        - 세 번째 파라미터: 값을 생성할 함수
        
        
        
        - generate사용 예제(구조체 내 operator() () 는 연산자 오버로딩이라니까 알아 볼 것)

    10.4.2 copy
        
        - 세 번째 파라미터: 붙여 넣을 대상의 시작 위치를 가리키는 반복자

    10.4.3 remove
        - 컨테이너 내 특정 값 구간내 전부 삭제
        - 삭제 후 크기가 변하지 않는다.
        - 삭제된 뒤 데이터를 앞으로 옮겨오고, 마지막 위치 반복자 리턴(end() 아니다)
        - 마지막 위치 반복자 부터 end() 까지는 기존의 값이 그대로 남아 있다.
            
        - 공간까지 삭제 하기 위해선 erase() 사용
        
        - 세 번째 파라미터: 지우고 싶은 값

    10.4.4 replace
        - 특정 값을 다른 값으로 바꿀 때
        
        - 세 번째 파라미터: 교체하기 이전의 값
        - 네 번째 파라미터: 교체할 값



10.5 정렬 관련 알고리즘
    - sort, binary_search, merge 등(외 +3개)

    10.5.1 sort
        - 컨테이너 내 데이터들을 정렬할 때 사용하는 알고리즘
        - 데이터 자료형이 기본형이면 STL에 있는 greate나 less 비교 조건자 사용(string은 알파벳 순)
        - 데이터 자료형이 기본형이 아니면 직접 비교 조건자를 만들어 사용
        
        - 비교 조건자가 없으면 오름차순 정렬
        
        - 세 번째 파라미터: 정렬 방법을 기술한 비교 조건자
        - RandomAccess 접근이 가능한 컨테이너만 사용 가능(map, set 등 불가)
        

        - 사용자가 만드는 비교 조건자 예시
        

        - 사용자가 만든 비교조건자를 사용한 정렬 예시
        

    10.5.2 binary_search
        - 정렬되어 있는 컨테이너의 구간 내 데이터를 찾는 알고리즘
        - 정렬하지 않고 사용하면 디버그 모드에서 오류, 릴리즈 모드에서 false 리턴
        - sort처럼 비교 조건자 사용 가능
        - sort와 다르게 랜덤 접근이 되지 않아도 사용 가능
         
        - 세 번째 파라미터: 조사할 값
        
       - 네 번째 파라미터: 비교 조건자

    10.5.3 merge
        - 두 개의 정렬된 구간을 합칠 때 사용
        - 합치는 구간은 겹치면 안되고, 넣을 공간을 미리 확보 해야 한다
        - 비교조건자가 있는 것과 없는게 있다
        
        - 다섯 번째 파라미터: 합친 결과를 넣을 출력 구간의 시작을 가리키는 반복자

        
        - 여섯 번째 파라미터: 비교 조건자



10.6 범용 수치 알고리즘
    - accumulate, inner_product 등

    10.6.1 accumulate
        - 지정한 구간 각각에 일정 값을 모두 더한 후, 모든 구간을 다시 더한다
        - 조간자를 사용하여 더하기 이외의 연산 가능
        - #include <numeric> 헤더 파일 포함
        
        - 세 번째 파라미터: 구간의 값에 더할 값

        
        - 네 번째 파라미터: 조건자를 이용해 기본자료 형 외의 데이터를 사용하거나 더하기 아닌 다른 연산 가능

    10.6.2 inner_product
        - 두 입력 시퀀스의 내적을 계산하는 알고리즘(+ 와 * 를 사용)
        - 두 입력 시퀀스의 값을 서로 곱한 후 더한 것
        - 두 번째 시퀀스는 첫 번째 시퀀스 구간 보다 크거나 같아야 한다