[C++ STL] 코딩테스트를 위한 algorithm

◆algorithm 클래스의 정의

: 알고리즘을 수행하는 C++ 표준 라이브러리 컨테이너 템플릿 함수를 정의합니다.

 

◆algorithm 클래스의 구문

(see links below for specific algorithm syntax)

 

 

◆algorithm 클래스의 함수

copy()

: 소스 범위의 요소를 대상 범위에 할당하여 요소의 소스 시퀀스 전체에서 반복하고 정방향으로 새 위치를 할당합니다.

first는 복사할 첫 위치, last는 마지막 위치, destBeg는 붙여넣을 위치를 나타냅니다. (exec는 사용할 실행 정책입니다.)

※ 단, 붙여넣을 공간이 할당되어 있는지 확인해야 합니다.

template<class InputIterator, class OutputIterator>
OutputIterator copy(
    InputIterator first,
    InputIterator last,
    OutputIterator destBeg);

template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
ForwardIterator2 copy(
    ExecutionPolicy&& exec,
    ForwardIterator1 first,
    ForwardIterator1 last,
    ForwardIterator2 result);

예제 코드)

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

using namespace std;

int main()
{
    vector<int> vec1{1, 2, 3};
    vector<int> vec2{0, 0, 0, 0};
    copy(vec1.begin(), vec1.end(), vec2.begin() + 1);
    for (int i : vec2)
    {
        // 0 1 2 3
        cout << i << " ";
    }
}

실행 예제)

 

count()

: 해당 값이 지정된 값과 일치하는 요소의 개수를 반환합니다.

first ~ last 까지의 범위에서 value의  개수를 반환합니다.

template<class InputIterator, class Type>
typename iterator_traits<InputIterator>::difference_type count(
    InputIterator first,
    InputIterator last,
    const Type& value);

template<class ExecutionPolicy, class ForwardIterator, class Type>
typename iterator_traits<ForwardIterator>::difference_type
count(
    ExecutionPolicy&& exec,
    ForwardIterator first,
    ForwardIterator last,
    const Type& value);

예제 코드)

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

using namespace std;

int main()
{
    vector<int> vec1{1, 1, 2, 3};
    //  1 : 2
    cout << "1 : " << count(vec1.begin(), vec1.end(), 1) << endl;
}

실행 결과 

 

count_if()

: 범위 내에서 해당 값이 지정된 조건과 일치하는 요소의 개수를 반환합니다.

template<class InputIterator, class UnaryPredicate>
typename iterator_traits<InputIterator>::difference_type count_if(
    InputIterator first,
    InputIterator last,
    UnaryPredicate pred);

template<class ExecutionPolicy, class ForwardIterator, class UnaryPredicate>
typename iterator_traits<ForwardIterator>::difference_type
count_if(
    ExecutionPolicy&& exec,
    ForwardIterator first,
    ForwardIterator last,
    UnaryPredicate pred);

예제 코드)

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

bool greater10(int value)
{
    return value > 10;
}

int main()
{
    using namespace std;
    vector<int> v1{10, 20, 10, 40, 10};
    vector<int>::iterator Iter;

    cout << "v1 = ( ";
    for (Iter = v1.begin(); Iter != v1.end(); Iter++)
        cout << *Iter << " ";
    cout << ")" << endl;

    vector<int>::iterator::difference_type result1;
    result1 = count_if(v1.begin(), v1.end(), greater10);
    cout << "The number of elements in v1 greater than 10 is: "
         << result1 << "." << endl;
}

실행 결과)

 

fill()

: 지정한 범위의 모든 요소에 동일한 새 값을 할당합니다.

template<class ForwardIterator, class Type>
void fill(
    ForwardIterator first,
    ForwardIterator last,
    const Type& value);

template<class ExecutionPolicy, class ForwardIterator, class Type>
void fill(
    ExecutionPolicy&& exec,
    ForwardIterator first,
    ForwardIterator last,
    const Type& value);

예제 코드)

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

using namespace std;

int main()
{
    vector<int> vec1(5);

    fill(vec1.begin(), vec1.begin() + 3, 1);
    for (int i : vec1)
    {
        // 1 1 1 0 0
        cout << i << " ";
    }
}

실행 결과) 

 

find()

: 범위에서 지정된 값을 가진 요소가 첫 번째로 나타나는 위치를 찾습니다.

※ 반환 자료형이 iterator 이므로 주의해서 사용합니다.

template<class InputIterator, class Type>
InputIterator find(
    InputIterator first,
    InputIterator last,
    const Type& value);

template<class ExecutionPolicy, class ForwardIterator, class Type>
ForwardIterator find(
    ExecutionPolicy&& exec,
    ForwardIterator first,
    ForwardIterator last,
    const Type& value);

예제 코드)

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

using namespace std;

int main()
{
    vector<int> vec1{0, 10, 20, 30, 1};
    vector<int>::iterator it = find(vec1.begin(), vec1.end(), 10);
    // 1
    cout << it - vec1.begin();
}

실행 결과)

for_each() //추후 추가

: 범위 내에서 정방향으로 각 요소에 지정된 함수 개체를 적용하고 함수 개체를 반환합니다.

: func는 범위의 각 요소에 적용되는 사용자 정의 함수 개체입니다.

template<class InputIterator, class Function>
Function for_each(
    InputIterator first,
    InputIterator last,
    Function func);

template<class ExecutionPolicy, class ForwardIterator, class Function>
void for_each(
    ExecutionPolicy&& exec,
    ForwardIterator first,
    ForwardIterator last,
    Function func);

 max()

: 두 개체를 비교하고 둘 중 큰 개체를 반환합니다. 정렬 기준은 이진 조건자로 지정할 수 있습니다.

template<class Type>
constexpr Type& max(
    const Type& left,
    const Type& right);
template<class Type, class Pr>
constexpr Type& max(
    const Type& left,
    const Type& right,
    BinaryPredicate pred);
template<class Type>
constexpr Type& max (
    initializer_list<Type> ilist);
template<class Type, class Pr>
constexpr Type& max(
    initializer_list<Type> ilist,
    BinaryPredicate pred);

예제 코드)

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int one = 1;
    int ten = 10;
    // 10
    cout << max(one, ten);
}

실행 결과)

 

max_element()

: 지정된 범위에서 가장 큰 첫 번째 요소를 찾습니다. 정렬 기준은 이진 조건자로 지정할 수 있습니다.

※ 반환 자료형이 iterator 이므로 주의해서 사용합니다.

template<class ForwardIterator>
constexpr ForwardIterator max_element(
    ForwardIterator first,
    ForwardIterator last );

template<class ForwardIterator, class Compare>
constexpr ForwardIterator max_element(
    ForwardIterator first,
    ForwardIterator last,
    Compare pred );

template<class ExecutionPolicy, class ForwardIterator>
ForwardIterator max_element(
    ExecutionPolicy&& exec,
    ForwardIterator first,
    ForwardIterator last);

template<class ExecutionPolicy, class ForwardIterator, class Compare>
ForwardIterator max_element(
    ExecutionPolicy&& exec,
    ForwardIterator first,
    ForwardIterator last,
    Compare pred);

예제 코드)

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

using namespace std;

int main()
{
    vector<int> vec1{10, 20, 10, 40, 10};
    // 3 , 위치를 반환합니다.
    cout << max_element(vec1.begin(), vec1.end()) - vec1.begin();
}

 

merge()

: 정렬된 두 소스 범위의 모든 요소를 정렬된 단일 대상 범위로 결합합니다. 정렬 기준은 이진 조건자로 지정할 수 있습니다.

result는 두 개의 소스 범위가 정렬된 단일 범위로 결합되는 대상 범위에서 첫 번째 요소 위치의 주소를 지정하는 입력 반복기입니다. (붙여 놓는 주소 입니다.)

template<class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator merge(
    InputIterator1 first1,
    InputIterator1 last1,
    InputIterator2 first2,
    InputIterator2 last2,
    OutputIterator result );

template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
OutputIterator merge(
    InputIterator1 first1,
    InputIterator1 last1,
    InputIterator2 first2,
    InputIterator2 last2,
    OutputIterator result,
    Compare pred );

template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator>
ForwardIterator merge(
    ExecutionPolicy&& exec,
    ForwardIterator1 first1,
    ForwardIterator1 last1,
    ForwardIterator2 first2,
    ForwardIterator2 last2,
    ForwardIterator result);

template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator, class Compare>
ForwardIterator merge(
    ExecutionPolicy&& exec,
    ForwardIterator1 first1,
    ForwardIterator1 last1,
    ForwardIterator2 first2,
    ForwardIterator2 last2,
    ForwardIterator result,
    Compare pred);

예제 코드)

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

using namespace std;

int main()
{
    vector<int> vec1{10, 20, 10, 40, 10};
    vector<int> vec2{1, 2, 1, 4, 1};
    // 충분한 공간이 선언되어 있어야 합니다.
    vector<int> vec3(11);

    // 두개의 컨테이너를 오름차순으로 붙여넣습니다.
    // 1 2 1 4 1 10 20 10 40 10 0
    merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), vec3.begin());
    for (int i : vec3)
    {
        cout << i << " ";
    }
}

실행 결과)

 

min()

: 두 개체를 비교하고 둘 중 작은 개체를 반환합니다. 정렬 기준은 이진 조건자로 지정할 수 있습니다.

template<class Type>
constexpr const Type& min(
    const Type& left,
    const Type& right);

template<class Type, class Pr>
constexpr const Type& min(
    const Type& left,
    const Type& right,
    BinaryPredicate pred);

template<class Type>
constexpr Type min(
    initializer_list<Type> ilist);

template<class Type, class Pr>
constexpr Type min(
    initializer_list<Type> ilist,
    BinaryPredicate pred);

 

next_permutation()

: 원래 순서가 있는 경우 사전적으로 다음으로 더 큰 순열로 대체되도록 범위의 요소를 다시 정렬합니다. 다음 사전적 의미는 이진 조건자를 사용하여 지정할 수 있습니다.

template<class BidirectionalIterator>
bool next_permutation(
    BidirectionalIterator first,
    BidirectionalIterator last);

template<class BidirectionalIterator, class BinaryPredicate>
bool next_permutation(
    BidirectionalIterator first,
    BidirectionalIterator last,
    BinaryPredicate pred);

예제 코드)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void printV(vector<int> v);

int main()
{
    // 1. next_permutation을 이용한 순열
    int a[3]{1, 2, 3};
    vector<int> v;
    for (int i = 0; i < 3; i++)
        v.push_back(a[i]);
    do
    {
        printV(v);
    } while (next_permutation(v.begin(), v.end()));

    return 0;
}

void printV(vector<int> v)
{
    for (int i = 0; i < v.size(); i++)
    {
        cout << v[i] << " ";
    }
    cout << "\n";
}

실행 결과)

 

reverse()

: 범위 내에서 요소의 순서를 반대로 바꿉니다.

template<class BidirectionalIterator>
void reverse(
    BidirectionalIterator first,
    BidirectionalIterator last);

template<class ExecutionPolicy, class BidirectionalIterator>
void reverse(
    ExecutionPolicy&& exec,
    BidirectionalIterator first,
    BidirectionalIterator last);

예제 코드)

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main()
{
    string str = "Why so Serious?";
    cout << "Before Reverse : " << str << endl;
    reverse(str.begin(), str.end());
    cout << "After Reverse : " << str << endl;
}

실행 결과)

 

rotate()

: 인접한 두 범위에 있는 요소를 교환합니다.

(middle ~ last]과 (first ~ middle]의 순서를 바꿔 줍니다.

template<class ForwardIterator>
void rotate(
    ForwardIterator first,
    ForwardIterator middle,
    ForwardIterator last);

template<class ExecutionPolicy, class ForwardIterator>
ForwardIterator rotate(
    ExecutionPolicy&& exec,
    ForwardIterator first,
    ForwardIterator middle,
    ForwardIterator last);

예제 코드)

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

int main()
{
    using namespace std;
    vector<int> v1;
    vector<int>::iterator v1Iter1;

    int i;
    for (i = -3; i <= 5; i++)
    {
        v1.push_back(i);
    }

    cout << "Vector v1 is ( ";
    for (v1Iter1 = v1.begin(); v1Iter1 != v1.end(); v1Iter1++)
    {
        cout << *v1Iter1 << " ";
    }
    cout << ")." << endl;

    rotate(v1.begin(), v1.begin() + 3, v1.end());
    cout << "After rotating, vector v1 is ( ";
    for (v1Iter1 = v1.begin(); v1Iter1 != v1.end(); v1Iter1++)
    {
        cout << *v1Iter1 << " ";
    }

    cout << ")." << endl;
}

실행 결과) 

 

sort()

: 지정된 범위에 있는 요소를 비내림차순 또는 이진 조건자로 지정한 정렬 기준에 따라 정렬합니다.

pred는  순서에 따라 연속적인 요소에 대해 충족될 비교 조건을 정의하는 사용자 정의 조건자 함수 개체입니다.

template<class RandomAccessIterator>
void sort(
    RandomAccessIterator first,
    RandomAccessIterator last);

template<class RandomAccessIterator, class Compare>
void sort(
    RandomAccessIterator first,
    RandomAccessIterator last,
    Compare pred);

template<class ExecutionPolicy, class RandomAccessIterator>
void sort(
    ExecutionPolicy&& exec,
    RandomAccessIterator first,
    RandomAccessIterator last);

template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
void sort(
    ExecutionPolicy&& exec,
    RandomAccessIterator first,
    RandomAccessIterator last,
    Compare pred);

예제 코드)

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

using namespace std;

void printV(vector<int> vec1, string str)
{
    cout << str << " : ";
    for (int i : vec1)
    {
        cout << i << " ";
    }
    cout << endl;
    return;
}

int main()
{
    vector<int> vec1{0, 2, 5, 4, 3, 1, 0};
    printV(vec1, "Origin");
    sort(vec1.begin(), vec1.end());
    printV(vec1, "Ascending");
    sort(vec1.begin(), vec1.end(), greater<>());
    printV(vec1, "Descending");
}

실행 결과)

 

 

swap()

: 첫 번째 재정의는 두 개체의 값을 교환합니다. 두 번째 재정의는 두 개체 배열 간에 값을 교환합니다.

※ 인자 left, right를 iterator가 아닌 변수로 주어야 합니다.

template<class Type>
void swap(
    Type& left,
    Type& right);
template<class Type, size_t N>
void swap(
    Type (& left)[N],
    Type (& right)[N]);

코드 예제)

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

using namespace std;

void printV(vector<int> vec1, string str)
{
    cout << str << " : ";
    for (int i : vec1)
    {
        cout << i << " ";
    }
    cout << endl;
    return;
}

int main()
{
    vector<int> vec1{0, 1, 2, 3};
    printV(vec1, "Origin vec1");
    swap(vec1[0], vec1[vec1.end() - vec1.begin() - 1]);
    printV(vec1, "Swap vec1");
}

실행 결과)

 

 

swap_ranges()

: 한 범위의 요소를 크기가 동일한 다른 범위의 요소로 교환합니다.

template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator2 swap_ranges(
   ForwardIterator1 first1,
   ForwardIterator1 last1,
   ForwardIterator2 first2 );

template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
ForwardIterator2 swap_ranges(
    ExecutionPolicy&& exec,
    ForwardIterator1 first1,
    ForwardIterator1 last1,
    ForwardIterator2 first2);

코드 예제)

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

using namespace std;

void printV(vector<int> vec1, string str)
{
    cout << str << " : ";
    for (int i : vec1)
    {
        cout << i << " ";
    }
    cout << endl;
    return;
}

int main()
{
    vector<int> vec1{0, 2, 5, 4, 3, 1, 0};
    vector<int> vec2{0, 1, 10, 100, 1000, 10000, 100000};
    printV(vec1, "Origin vec1");
    printV(vec2, "Origin vec1");
    swap_ranges(vec1.begin(), vec1.end(), vec2.begin());
    printV(vec1, "Swap vec1");
    printV(vec2, "Swap vec2");
}

실행 결과)