[C++] Algorithm

1. Algorithm

#include <algorithm>
#include <vector>
#include <list>

int main()
{
    std::list   s = {1,2,3,4,5};
    std::vector v = {1,2,3,4,5};

    // 각 컨테이너에서 3을 검색하고 싶다고 할때 어떻게 할까
}

- 컨테이너에 검색기능을 추가한다고 가정해보자

 

① 멤버 함수 find를 제공

s.find(3);
v.find(3);

(1) 장점

- 사용하기 쉽다

 

(2) 단점

- 이 방법은 사용하기는 쉽지만, 동일한 기능을 하는 모든 컨테이너에 넣어야 한다.

- 또한, 새로운 함수(기능)을 추가혀려면 모든 컨테이너에 추가해야 한다.

 

② 멤버 함수가 아닌 일반 함수(템플릿) 형태로 find를 제공

std::find(s.begin(), s.end(), 3);
std::find(v.begin(), v.end(), 3);

(1) 장점

- 한 개의 함수(템플릿)로 모든 컨테이너에서 검색할 수 있다.

(2) 단점

- 코드가 좀 복잡해 보인다.

#include <algorithm>
#include <vector>
#include <list>

int main()
{
    std::list   s = {1,2,3,4,5};
    std::vector v = {1,2,3,4,5};

    // 각 컨테이너에서 3을 검색하고 싶다고 할때 어떻게 할까
    auto ret1 = std::find(s.begin(), s.end(), 3);
    auto ret2 = std::find(v.begin(), v.end(), 3);
}

- std::find 는 전달된 인자가 list 반복자인지 vector 반복자인지 알 필요가 없다.

- 왜냐하면 모든 반복자는 다음으로 이동하는 방법이 동일하기 때문이다.

 

1-1. Algorithm의 정의

① 일반적으로 말하는 알고리즘

- 문제를 해결하는 방법이라는 용어

② STL 라이브러리에서 알고리즘(algorithm)

- std::find와 같은 특정 기능(검색, 정렬 등)을 구현한 멤버가 아닌 일반 함수(템플릿)을 가리키는 용어

- <algorithm> 헤더 필요

- C++ 표준에 정렬, 검색, 순열, 치환 다양한 알고리즘이 제공된다.

 

1-2. std::find

#include <algorithm>
#include <vector>
#include <list>
#include <iostream>

int main()
{
    std::list   s = {1,2,3,4,5};

    auto ret1 = std::find(s.begin(), s.end(), 3);
}

- 알고리즘에는 크게 2가지 형태가 존재한다.

 

1-2-1. 인자로 반복자를 전달하는 방법

- STL 처음(C++98) 부터 지원

- std:: 이름 공간 안에 제공한다.

- 컨테이너의 전체 또는 일부 구간 검색 가능

auto ret = std::find(first, last, 3);

※ last는 검색 대상이 아님에 유의할 것.

- [first, last)로 표기. [ -> 검색 대상 ) -> 검색 대상이 아님을 의미

- 검색 실패시 last를 반환한다.

 

※ 반환값

검색 성공	해당 요소의 위치를 가리키는 반복자
검색 실패	2번째 인자로 전달한 last 반환

 

#include <algorithm>
#include <vector>
#include <list>
#include <iostream>

int main()
{
    std::list   s = {1,2,3,4,5};

    auto ret1 = std::find(s.begin(), s.end(), 3);
    
    if ( ret1 == s.end() ) // 검색 실패한 경우 처리
}

 

#include <algorithm>
#include <vector>
#include <list>
#include <iostream>

int main()
{
    std::list   s = {1,2,3,4,5};

    auto ret1 = std::find(s.begin(), s.end(), 3);
    
    if (ret1 == s.end() )
    
    auto first = s.begin();
//  auto last = first + 3; // vector 반복자는 가능, list 반복자는 안됨.
    auto last = std::next(first, 3);  // 4를 가리킴.
    
    auto ret2 = std::find(first, last, 3);
    
    if(ret2 == last)
    {
    	std::cout << "fail" << std::endl;
    }
    else
    {
        std::cout << "success : " << *ret2 << std::endl;
    }
}

- vector 반복자는 first+3; 과 같은 연산이 가능하나, list 반복자는 그것이 불가능하다.

 

1-2-2. 인자로 컨테이너를 전달하는 방법 // C++20

#include <iostream>
#include <algorithm>
#include <vector>
#include <list>
#include <ranges>

int main()
{
    std::list s = {1,2,3,4,5};
    
    //auto ret1 = std::find(s.begin(), s.end(), 3);
    auto ret1 = std::ranges::find(s, 3);
    
    if ( ret1 == s.end()) // 검색 실패한 경우
    
    auto iv = std::views::take(s, 3);
    
    auto ret2 == std::ranges::find(iv, 3);
    
    if (ret2 == last)
        std::cout << "fail" << std::endl;
    else
        std::cout << "success : " << *ret2 << std::endl;
}

- std::ranges 이름 공간 안에 제공한다.

- <ranges> 헤더가 필요하다.

- 검색 실패시 cont.end()가 반환된다. 

- 부분 검색이 필요한 경우에는 views를 사용한다.

---

2. 조건자(predicator)

#include <iostream>
#include <algorithm>
#include <list>

int main()
{
   std::list s = {1, 9, 5, 7, 3, 8, 10};
   
   // s 에서 첫 번째 나오는 3을 찾고 싶다.
   auto ret1 = std::find(s.begin(), s.end(), 3);
   
   // s 에서 첫 번째 나오는 "3의 배수"를 찾고 싶다.
   auto ret2 = std::find(s.begin(), s.end(), 3);
 
}

 

※ 값 검색과 조건 검색이 다르다.

값 검색	std::find(first, last, 값);
조건 검색	std::find_if(first, last, 함수);

 

2-1. 조건자 ( predicator ) 란?

- bool을 반환하는 함수이다

- _if 로 끝나는 알고리즘에 전달되어 정책으로 사용한다.

 

※ 단항 조건자 & 이항 조건자

단항 조건자	인자가 1개인 조건자
이항 조건자	인자가 2개인 조건자

- std::find_if는 3번째 인자로 단항 조건자를 요구한다.

#include <iostream>
#include <list>
#include <algorithm>

bool foo(int n) { return n % 3 == 0; }

int main()
{
    std::list s = {1, 9, 5, 7, 3, 8, 10};
    
    auto ret1 = std::find(s.begin(), s.end(), 3);
    
    auto ret2 = std::find_if(s.begin(), s.end(), foo);
    
}

- 일반적으로 일반 함수 보다 람다 함수를 권장한다.

 

① 람다 함수 구현 예시

#include <iostream>
#include <list>
#include <algorithm>

bool foo(int n) { return n % 3 == 0; }

int main()
{
    std::list s = {1, 9, 5, 7, 3, 8, 10};
    
    auto ret1 = std::find(s.begin(), s.end(), 3);
    
    auto ret2 = std::find_if(s.begin(), s.end(), [](int n) { return n % 3 == 0;} );
    
}

② 지역 변수 캡처의 예시

#include <iostream>
#include <list>
#include <algorithm>

bool foo(int n) { return n % 3 == 0; }

int main()
{
    std::list s = {1, 9, 5, 7, 3, 8, 10};
    
    auto ret1 = std::find(s.begin(), s.end(), [](int n) { return n % 3 == 0;} );
    
    int k = 0;
    std::cin >> k;
    
    auto ret1 = std::find(s.begin(), s.end(), [k](int n) { return n % k == 0;} ); 
    // 람다 표현식 안에서 지역변수 k를 사용할 수 있다.
    
}

---

3. etc

 

3-1. std::replace

#include <iostream>
#include <vector>
#include <algorithm>
int main()
{
    std::vector v = {1, 3, 10, 30, 4, 7, 8, 20};
    
    for (auto e : v)
         std::cout << e << ", ";
    std::endl;
    
    
    // std::replace(v,begin(), v.end(), 3, 0);
    std::replace_if(v.begin(), v.end(), [](int n) { return n > 10; }, 0);
    
    for (auto e : v)
         std::cout << e << ", ";
    std::endl;
}

- 특정 범위 내에 있는 모든 원소의 값을 변경한다.

 

3-2. std::accumulate 

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
int main()
{
    std::vector v = {1, 3, 10, 30, 4, 7, 8, 20};
    
    for (auto e : v)
         std::cout << e << ", ";
    std::endl;
    
    int n = std::accumulate(v.begin(), v.end(), 0);
    std::cout << n << std::endl;
    // 3번째 인자 값에 더하기를 하기 위해서는 0을 넣어야 한다. 
}

- <numeric> 헤더가 필요하다.

- 특정 범위 내 합을 구해주는 알고리즘이다.

 

3-3. std::sort

#include <iostream>
#include <vector>
#include <algorithm>
int main()
{
    std::vector v = {1, 3, 10, 30, 4, 7, 8, 20};
    
    for (auto e : v)
         std::cout << e << ", ";
    std::endl;
    
    std::sort(v.begin(), v.end());
    
    for (auto e : v)
         std::cout << e << ", ";
    std::endl;

}

- sort의 기본 정렬은 '오름차순'이다.

- 내림차순은 다음과 같이 수정하면 된다.

- std::sort는 std::sort_if가 없다.

std::sort(v.begin(), v.end(), [](int a, int b) { return a > b; }

 

3-4. std::fill

#include <iostream>
#include <vector>
#include <algorithm>
int main()
{
    std::vector v = {1, 3, 10, 30, 4, 7, 8, 20};
    
    for (auto e : v)
         std::cout << e << ", ";
    std::endl;
    
    std::fill(v.begin(), v.end(), 1);
    
    for (auto e : v)
         std::cout << e << ", ";
    std::endl;

}

- 특정 컨테이너의 요소를 모두 1로 채워주는 알고리즘이다.

---

4. Etc

- cppreference.com 의 Algorithm Library를 참고하면 여러 예제를 익혀볼 수 있다.

- 사용법이나 구현 방법도 있으니 종종 확인해봐야겠다.