Move Fast

변경 가능 알고리즘 (Modifying Sequence Algorithm)

• copy 원소들을 복사.

  • copy_n 원하는 개수만큼 원소들을 복사

  • copy_if 원소들 중 조건에 일치하는 것들만 복사

  • copy_backward 원소들을 뒤에서부터 복사

// until C++20
template< class InputIt, class OutputIt >
OutputIt copy( InputIt first, InputIt last, OutputIt d_first );

template< class BidirIt1, class BidirIt2 >
BidirIt2 copy_backward( BidirIt1 first, BidirIt1 last, BidirIt2 d_last );

// since C++20
template< class InputIt, class OutputIt >
constexpr OutputIt copy( InputIt first, InputIt last, OutputIt d_first );

template< class InputIt, class OutputIt, class UnaryPredicate >
constexpr OutputIt copy_if( InputIt first, InputIt last,
                            OutputIt d_first, UnaryPredicate pred );

template< class InputIt, class Size, class OutputIt >
constexpr OutputIt copy_n( InputIt first, Size count, OutputIt result );

template< class BidirIt1, class BidirIt2 >
constexpr BidirIt2 copy_backward( BidirIt1 first, BidirIt1 last, BidirIt2 d_last );

// since C++17
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
ForwardIt2 copy( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last,
                 ForwardIt2 d_first );

template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
          class UnaryPredicate >
ForwardIt2 copy_if( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last,
                  ForwardIt2 d_first, UnaryPredicate pred );

template< class ExecutionPolicy, class ForwardIt1, class Size, class ForwardIt2 >
ForwardIt2 copy_n( ExecutionPolicy&& policy, ForwardIt1 first, Size count,
                   ForwardIt2 result );

// since C++11
template< class InputIt, class OutputIt, class UnaryPredicate >
OutputIt copy_if( InputIt first, InputIt last,
                  OutputIt d_first, UnaryPredicate pred );

template< class InputIt, class Size, class OutputIt >
OutputIt copy_n( InputIt first, Size count, OutputIt result );

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

int main() {
    vector<int> from_vector, to_vector;
    for (int i = 0; i < 10; i++)
        from_vector.push_back(i);

    copy(from_vector.begin(), from_vector.end(), back_inserter(to_vector));
    /* same as
     *    vector<int> to_vector(from_vector.size());
     *    copy(from_vector.begin(), from_vector.end(), to_vector.begin());
     * or
     *    vector<int> to_vector = from_vector;
     */

    cout << "to_vector contains: ";
    copy(to_vector.begin(), to_vector.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    cout << "odd numbers in to_vector are: ";
    copy_if(to_vector.begin(), to_vector.end(), ostream_iterator<int>(cout, " "),
            [](int x) { return (x % 2) == 1; });
    cout << endl;

    to_vector.clear();
    to_vector.resize(20);
    cout << "4 numbers in to_vector are: ";
    copy_n(from_vector.cbegin(), 4, to_vector.begin());
    copy(to_vector.begin(), to_vector.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    cout << "copy_backward() on to_vector: ";
    copy_backward(from_vector.begin(), from_vector.end(), to_vector.end());
    copy(to_vector.begin(), to_vector.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
to_vector contains: 0 1 2 3 4 5 6 7 8 9
odd numbers in to_vector are: 1 3 5 7 9
4 numbers in to_vector are: 0 1 2 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
copy_backward() on to_vector: 0 1 2 3 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9
 */

• move 원소들을 이동시킴.

  • move_backward 원소들을 뒤에서부터 이동시킴.

// since C++11 until C++20
template< class InputIt, class OutputIt >
OutputIt move( InputIt first, InputIt last, OutputIt d_first );

template< class BidirIt1, class BidirIt2 >
BidirIt2 move_backward( BidirIt1 first, BidirIt1 last, BidirIt2 d_last );

// since C++20
template< class InputIt, class OutputIt >
constexpr OutputIt move( InputIt first, InputIt last, OutputIt d_first );

template< class BidirIt1, class BidirIt2 >
constexpr BidirIt2 move_backward( BidirIt1 first, BidirIt1 last, BidirIt2 d_last );

// since C++17
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
ForwardIt2 move( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last,
                 ForwardIt2 d_first );

// ----------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <iterator> // next()
#include <thread>
#include <chrono>
using namespace std;

void fn(int n) {
    this_thread::sleep_for(chrono::seconds(n));
    cout << "thread " << n << " ended" << endl;
}

int main() {
    vector<thread> v;
    list<thread> l1, l2;

    // copy() would not compile, because thread is noncopyable
    for (int i = 1; i < 7; i++)
        v.emplace_back(fn, i);

    cout << "move(): " << endl;
    move(v.begin(), next(v.begin(), 3), back_inserter(l1));
    for (auto& t : l1) t.join();

    cout << endl << "move_backward(): " << endl;
    l2.emplace_back(fn, 0);
    l2.emplace_back(fn, 0);
    l2.resize(5);
    // error because [v.begin(), v.begin() + 3] are empty.
    // move_backward(v.begin(), v.end(), l2.end());
    move_backward(v.begin() + 3, v.end(), l2.end());
    for (auto& t : l2) {
        t.join();
    }

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
move():
thread 1 ended
thread 2 ended
thread 3 ended

move_backward():
thread 0 ended
thread 0 ended
thread 4 ended
thread 5 ended
thread 6 ended
 */

• fill 특정 값으로 원소들을 채움.

  • fill_n 특정 값으로 원하는 개수만큼 원소들을 채움.

// until C++20
template< class ForwardIt, class T >
void fill( ForwardIt first, ForwardIt last, const T& value );

// since C++20
template< class ForwardIt, class T >
constexpr void fill( ForwardIt first, ForwardIt last, const T& value );

template< class OutputIt, class Size, class T >
constexpr OutputIt fill_n( OutputIt first, Size count, const T& value );

// since C++17
template< class ExecutionPolicy, class ForwardIt, class T >
void fill( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
           const T& value );

template< class ExecutionPolicy, class ForwardIt, class Size, class T >
ForwardIt fill_n( ExecutionPolicy&& policy, ForwardIt first, Size count,
                  const T& value );

// until C++11
template< class OutputIt, class Size, class T >
void fill_n( OutputIt first, Size count, const T& value );

// since C++11 until C++20
template< class OutputIt, class Size, class T >
OutputIt fill_n( OutputIt first, Size count, const T& value );

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

int main() {
    vector<int> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    fill(v.begin(), v.end(), -1);

    for (auto elem : v)
        cout << elem << " ";
    cout << endl;

    fill_n(v.begin(), 5, 0);
    for (auto elem : v)
        cout << elem << " ";
    cout << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
0 0 0 0 0 -1 -1 -1 -1 -1
 */

• transform 범위 내 각 원소에 대해 주어진 함수를 호출.

// until C++20
template< class InputIt, class OutputIt, class UnaryOperation >
OutputIt transform( InputIt first1, InputIt last1, OutputIt d_first,
                    UnaryOperation unary_op );

template< class InputIt1, class InputIt2, class OutputIt, class BinaryOperation >
OutputIt transform( InputIt1 first1, InputIt1 last1, InputIt2 first2, 
                    OutputIt d_first, BinaryOperation binary_op );

// since C++20
template< class InputIt, class OutputIt, class UnaryOperation >
constexpr OutputIt transform( InputIt first1, InputIt last1, OutputIt d_first,
                              UnaryOperation unary_op );

template< class InputIt1, class InputIt2, class OutputIt, class BinaryOperation >
constexpr OutputIt transform( InputIt1 first1, InputIt1 last1, InputIt2 first2, 
                              OutputIt d_first, BinaryOperation binary_op );

// since C++17
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
          class UnaryOperation >
ForwardIt2 transform( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1,
                      ForwardIt2 d_first, UnaryOperation unary_op );

template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
          class ForwardIt3, class BinaryOperation >
ForwardIt3 transform( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1,
                      ForwardIt2 first2, ForwardIt3 d_first,
                      BinaryOperation binary_op );

// ----------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cctype>
#include <functional> // plus<>()
using namespace std;

int main() {
    string s("hello");
    transform(s.begin(), s.end(), s.begin(),
            [](unsigned char c) -> unsigned char { return toupper(c); });

    vector<size_t> ordinals;
    transform(s.begin(), s.end(), back_inserter(ordinals),
            [](unsigned char c) -> size_t { return c; });

    cout << s << ':';
    for (auto ord : ordinals) cout << ' ' << ord;
    cout << endl;
    
    // ordinals[i] = ordinals[i] + ordinals[i]
    transform(ordinals.cbegin(), ordinals.cend(), ordinals.cbegin(),
            ordinals.begin(), plus<>{});

    for (auto ord : ordinals) cout << ord << ' ';
    cout << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++17
$ ./a.out
HELLO: 72 69 76 76 79
144 138 152 152 158
 */

• generate 범위 내 원소들을 주어진 함수를 호출한 결과로 채움.

  • generate_n 범위 내 특정 개수만큼 원소들을 주어진 함수를 호출한 결과로 채움.

// until C++20
template< class ForwardIt, class Generator >
void generate( ForwardIt first, ForwardIt last, Generator g );

// since C++20
template< class ForwardIt, class Generator >
constexpr void generate( ForwardIt first, ForwardIt last, Generator g );

template< class OutputIt, class Size, class Generator >
constexpr OutputIt generate_n( OutputIt first, Size count, Generator g );

// since C++17
template< class ExecutionPolicy, class ForwardIt, class Generator >
void generate( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
               Generator g );

template< class ExecutionPolicy, class ForwardIt , class Size, class Generator >
ForwardIt generate_n( ExecutionPolicy&& policy, ForwardIt first,
                      Size count, Generator g );

// until C++11
template< class OutputIt, class Size, class Generator >
void generate_n( OutputIt first, Size count, Generator g );

// since C++11 until C++20
template< class OutputIt, class Size, class Generator >
OutputIt generate_n( OutputIt first, Size count, Generator g );

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

int fn() {
    static int i = 1;
    return i++;
}

int main() {
    vector<int> v(5);
    generate(v.begin(), v.end(), fn);

    cout << "v: ";
    for (auto iv: v)
        cout << iv << " ";
    cout << endl;

    // Initialize with default values 0,1,2,3,4 from a lambda function
    // Equivalent to iota(v.begin(), v.end(), 0);
    generate(v.begin(), v.end(), [n = 0] () mutable { return n++; });

    cout << "v: ";
    for (auto iv: v)
        cout << iv << " ";
    cout << endl;

    generate_n(v.begin(), 2, []() { return -1; });

    cout << "v: ";
    for (auto iv: v)
        cout << iv << " ";
    cout << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++17
$ ./a.out
v: 1 2 3 4 5
v: 0 1 2 3 4
v: -1 -1 2 3 4
 */

• remove 범위 내 특정 값과 일치하는 원소들을 제거.

  • remove_if 조건과 일치하는 원소들을 제거.

  • remove_copy 특정 값과 일치하는 원소들을 복사한 후 제거. (원본은 유지)

  • remove_copy_if 조건과 일치하는 원소들을 복사한 후 제거. (원본은 유지)

  • 원본 컨테이너에서 제거할 원소는 뒤의 원소를 옮김(move)으로써 제거하기 때문에 erase() 등의 멤버 함수를 사용해서 뒤에 남은 부분을 제거할 필요가 있음.

  • 반환값은 옮긴 후 마지막 원소를 참조하는 iterator.

// until C++20
template< class ForwardIt, class T >
ForwardIt remove( ForwardIt first, ForwardIt last, const T& value );

template< class ForwardIt, class UnaryPredicate >
ForwardIt remove_if( ForwardIt first, ForwardIt last, UnaryPredicate p );

template< class InputIt, class OutputIt, class T >
OutputIt remove_copy( InputIt first, InputIt last, OutputIt d_first,
                      const T& value );

template< class InputIt, class OutputIt, class UnaryPredicate >
OutputIt remove_copy_if( InputIt first, InputIt last, OutputIt d_first,
                         UnaryPredicate p );

// since C++20
template< class ForwardIt, class T >
constexpr ForwardIt remove( ForwardIt first, ForwardIt last, const T& value );

template< class ForwardIt, class UnaryPredicate >
constexpr ForwardIt remove_if( ForwardIt first, ForwardIt last,
                               UnaryPredicate p );

template< class InputIt, class OutputIt, class T >
constexpr OutputIt remove_copy( InputIt first, InputIt last, OutputIt d_first,
                                const T& value );

template< class InputIt, class OutputIt, class UnaryPredicate >
constexpr OutputIt remove_copy_if( InputIt first, InputIt last, OutputIt d_first,
                                   UnaryPredicate p );

// since C++17
template< class ExecutionPolicy, class ForwardIt, class T >
ForwardIt remove( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
                  const T& value );

template< class ExecutionPolicy, class ForwardIt, class UnaryPredicate >
ForwardIt remove_if( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
                     UnaryPredicate p );

template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class T >
ForwardIt2 remove_copy( ExecutionPolicy&& policy,
                        ForwardIt1 first, ForwardIt1 last,
                        ForwardIt2 d_first, const T& value );

template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
          class UnaryPredicate >
ForwardIt2 remove_copy_if( ExecutionPolicy&& policy,
                           ForwardIt1 first, ForwardIt1 last,
                           ForwardIt2 d_first, UnaryPredicate p );

// ----------------------------------------------------------------------------------
#include <algorithm>
#include <iterator>
#include <string>
#include <iostream>
#include <cctype>
using namespace std;;

int main()
{
    string str1 = "Text with some   spaces";
    str1.erase(remove(str1.begin(), str1.end(), ' '), str1.end());
    cout << str1 << endl;

    string str2 = "Text\n with\tsome \t  whitespaces\n\n";
    string str3 = str2;
    str2.erase(remove_if(str2.begin(), str2.end(),
                [](unsigned char x) { return isspace(x); }), str2.end());
    cout << str2 << endl;

    remove(str3.begin(), str3.end(), '\n');
    // after just moving
    cout << str3 << endl;

    str3 = "Text with some   spaces";
    cout << "Before: " << str3 << endl;
    cout << "After remove_copy(): ";
    remove_copy(str3.begin(), str3.end(), ostream_iterator<char>(cout), ' ');
    cout << endl;

    str3 = "Text with some   spaces";
    cout << "Before: " << str3 << endl;
    cout << "After remove_copy_if(): ";
    remove_copy_if(str3.begin(), str3.end(), ostream_iterator<char>(cout),
                   [](unsigned char x) { return isspace(x); });
    cout << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
Textwithsomespaces
Textwithsomewhitespaces
Text with	some 	  whitespacess


Before: Text with some   spaces
After remove_copy(): Textwithsomespaces
Before: Text with some   spaces
After remove_copy_if(): Textwithsomespaces
 */

• replace 특정 범위 내 원소들을 주어진 원소들로 치환.

  • replace_if 범위 내 조건과 일치하는 원소들을 주어진 원소들로 치환.

  • replace_copy 특정 범위 내 원소들을 복사한 후, 주어진 원소들로 치환. (원본은 유지)

  • replace_copy_if 범위 내 조건과 일치하는 원소들을 복사한 후, 주어진 원소들로 치환. (원본은 유지)

// until C++20
template< class ForwardIt, class T >
void replace( ForwardIt first, ForwardIt last,
              const T& old_value, const T& new_value );

template< class ForwardIt, class UnaryPredicate, class T >
void replace_if( ForwardIt first, ForwardIt last,
                 UnaryPredicate p, const T& new_value );

template< class InputIt, class OutputIt, class T >
OutputIt replace_copy( InputIt first, InputIt last, OutputIt d_first,
                       const T& old_value, const T& new_value );

template< class InputIt, class OutputIt, class UnaryPredicate, class T >
OutputIt replace_copy_if( InputIt first, InputIt last, OutputIt d_first,
                          UnaryPredicate p, const T& new_value );

// since C++20
template< class ForwardIt, class T >
constexpr void replace( ForwardIt first, ForwardIt last,
                        const T& old_value, const T& new_value );

template< class ForwardIt, class UnaryPredicate, class T >
constexpr void replace_if( ForwardIt first, ForwardIt last,
                           UnaryPredicate p, const T& new_value );

template< class InputIt, class OutputIt, class T >
constexpr OutputIt replace_copy( InputIt first, InputIt last, OutputIt d_first,
                                 const T& old_value, const T& new_value );

template< class InputIt, class OutputIt, class UnaryPredicate, class T >
constexpr OutputIt replace_copy_if( InputIt first, InputIt last, OutputIt d_first,
                                    UnaryPredicate p, const T& new_value );

// since C++17
template< class ExecutionPolicy, class ForwardIt, class T >
void replace( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
              const T& old_value, const T& new_value );

template< class ExecutionPolicy, class ForwardIt, class UnaryPredicate, class T >
void replace_if( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
                 UnaryPredicate p, const T& new_value );

template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class T >
ForwardIt2 replace_copy( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last,
                         ForwardIt2 d_first, const T& old_value, const T& new_value);

template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
          class UnaryPredicate, class T >
ForwardIt2 replace_copy_if( ExecutionPolicy&& policy,
                            ForwardIt1 first, ForwardIt1 last,
                            ForwardIt2 d_first, UnaryPredicate p,
                            const T& new_value );

// ----------------------------------------------------------------------------------
#include <iostream>
#include <string>
#include <algorithm>
#include <array>
#include <functional>
using namespace std;

void print(array<int, 10> &s, string msg) {
    cout << msg;
    for (int a : s)
        cout << a << " ";
    cout << endl;
}

int main()
{
    array<int, 10> s{5, 7, 4, 2, 8, 6, 1, 9, 0, 3};
    print(s, "Before: ");

    replace(s.begin(), s.end(), 8, 88);
    print(s, "After replace(): ");

    replace_if(s.begin(), s.end(), bind(less<int>(), placeholders::_1, 5), 55);
    print(s, "After replace_if(): ");

    cout << "After replace_copy(): ";
    replace_copy(s.begin(), s.end(), ostream_iterator<int>(cout, " "), 88, 1);
    cout << endl;

    cout << "After replace_copy_if(): ";
    replace_copy_if(s.begin(), s.end(), ostream_iterator<int>(cout, " "),
                    [](int n){return n > 5;}, 99);
    cout << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
Before: 5 7 4 2 8 6 1 9 0 3
After replace(): 5 7 4 2 88 6 1 9 0 3
After replace_if(): 5 7 55 55 88 6 55 9 55 55
After replace_copy(): 5 7 55 55 5 6 55 9 55 55
After replace_copy_if(): 5 99 99 99 99 99 99 99 99 99
 */

• swap 범위 내 두 원소를 교환.

  • swap_ranges 주어진 두 범위의 원소들을 교환.

  • iter_swap 두 반복자가 참조하는 원소들을 교환.

#include <iostream>
#include <list>
#include <vector>
#include <algorithm>
#include <random>
#include <functional>
using namespace std;

template<class ForwardIt>
void selection_sort(ForwardIt begin, ForwardIt end) {
    for (ForwardIt i = begin; i != end; ++i)
        iter_swap(i, min_element(i, end));
}


int main() {
    int a = 5, b = 3;
    cout << "Before swap(): ";
    cout << a << ' ' << b << endl;

    swap(a,b);

    cout << "After swap(): ";
    cout << a << ' ' << b << endl;

    vector<int> v = {1, 2, 3, 4, 5};
    list<int> l = {-1, -2, -3, -4, -5};

    cout << "Call swap_ranges():" << endl;

    swap_ranges(v.begin(), v.begin()+3, l.begin());

    for(int n : v) cout << n << ' ';
    cout << endl;
    for(int n : l) cout << n << ' ';
    cout << endl;

    cout << "Call iter_swap():" << endl;
    random_device rd;
    mt19937 gen(rd());
    uniform_int_distribution<> dist(-10, 10);
    vector<int> v2;
    generate_n(back_inserter(v2), 20, bind(dist, gen));

    cout << "Before sort: ";
    for(auto e : v2) cout << e << " ";

    selection_sort(v2.begin(), v2.end());

    cout << endl << "After sort: ";
    for(auto e : v2) cout << e << " ";
    cout << endl;
    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
Before swap(): 5 3
After swap(): 3 5
Call swap_ranges():
-1 -2 -3 4 5
1 2 3 -4 -5
Call iter_swap():
Before sort: 8 7 -9 -7 9 0 -8 -8 -2 -9 -4 8 -1 -9 -1 -8 -6 10 -2 -9
After sort: -9 -9 -9 -9 -8 -8 -8 -7 -6 -4 -2 -2 -1 -1 0 7 8 8 9 10
 */

• reverse 범위 내 원소들을 뒤집음.

  • reverse_copy 범위 내 원소들을 뒤집은 상태로 복사함. (원본은 유지)

// until C++20
template< class BidirIt >
void reverse( BidirIt first, BidirIt last );

template< class BidirIt, class OutputIt >
OutputIt reverse_copy( BidirIt first, BidirIt last, OutputIt d_first );

// since C++20
template< class BidirIt >
constexpr void reverse( BidirIt first, BidirIt last );

template< class BidirIt, class OutputIt >
constexpr OutputIt reverse_copy( BidirIt first, BidirIt last, OutputIt d_first );

// since C++17
template< class ExecutionPolicy, class BidirIt >
void reverse( ExecutionPolicy&& policy, BidirIt first, BidirIt last );

template< class ExecutionPolicy, class BidirIt, class ForwardIt >
ForwardIt reverse_copy( ExecutionPolicy&& policy, BidirIt first, BidirIt last,
                        ForwardIt d_first );

// ----------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;

int main() {
    cout << "Call reverse():" << endl;
    vector<int> v{1,2,3};
    reverse(begin(v), end(v));
    for(auto e : v) cout << e;
    cout << endl;

    int a[] = {4, 5, 6, 7};
    reverse(begin(a), end(a));
    for(auto e : a) cout << e;
    cout << endl;

    cout << "Call reverse_copy():" << endl;
    // lambda
    auto print = [](vector<int> const& v) {
        for (const auto& value : v)
            cout << value << ' ';
        cout << '\t';
    };

    print(v);
    vector<int> destination(3);
    reverse_copy(begin(v), end(v), begin(destination));
    print(destination);

    reverse_copy(rbegin(v), rend(v), begin(destination));
    print(destination);

    cout << endl;
    return 0;
}

/*
$ g++ test.cpp -std=c++17
$ ./a.out
Call reverse():
321
7654
Call reverse_copy():
3 2 1 	1 2 3 	3 2 1
 */

• rotate 범위 내 원소들을 왼쪽으로 회전시킴.

  • rotate_copy 범위 내 원소들을 왼쪽으로 회전시칸 후 복사. (원본은 유지)

// until C++11
template< class ForwardIt >
void rotate( ForwardIt first, ForwardIt n_first, ForwardIt last );

// since C++11 until C++20
template< class ForwardIt >
ForwardIt rotate( ForwardIt first, ForwardIt n_first, ForwardIt last );

// until C++20
template< class ForwardIt, class OutputIt >
OutputIt rotate_copy( ForwardIt first, ForwardIt n_first,
                      ForwardIt last, OutputIt d_first );

// since C++20
template< class ForwardIt >
constexpr ForwardIt rotate( ForwardIt first, ForwardIt n_first, ForwardIt last );

template< class ForwardIt, class OutputIt >
constexpr OutputIt rotate_copy( ForwardIt first, ForwardIt n_first,
                                ForwardIt last, OutputIt d_first );

// since C++17
template< class ExecutionPolicy, class ForwardIt >
ForwardIt rotate( ExecutionPolicy&& policy,  ForwardIt first, ForwardIt n_first,
                  ForwardIt last );

template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
ForwardIt2 rotate_copy( ExecutionPolicy&& policy, ForwardIt1 first,
                        ForwardIt1 n_first, ForwardIt1 last, ForwardIt2 d_first );

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

void print(string msg, vector<int> &v) {
    cout << msg;
    for (auto n : v)
        cout << n << " ";
    cout << endl;
}

int main() {
    vector<int> v{ 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    print("Before: ", v);

    rotate(v.begin(), v.begin() + 1, v.end());
    print("Simple left rotate: ", v);
    rotate(v.begin(), v.begin() + 1, v.end());
    print("Simple left rotate: ", v);
    rotate(v.begin(), v.begin() + 1, v.end());
    print("Simple left rotate: ", v);

    rotate(v.rbegin(), v.rbegin() + 3, v.rend());
    print("Simple right rotate: ", v);

    vector<int> v2(v.size());
    auto pivot = find(v.begin(), v.end(), 5);
    rotate_copy(v.begin(), pivot, v.end(), v2.begin());
    print("Call rotate_copy(): ", v2);

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
Before: 1 2 3 4 5 6 7 8 9
Simple left rotate: 2 3 4 5 6 7 8 9 1
Simple left rotate: 3 4 5 6 7 8 9 1 2
Simple left rotate: 4 5 6 7 8 9 1 2 3
Simple right rotate: 1 2 3 4 5 6 7 8 9
Call rotate_copy(): 5 6 7 8 9 1 2 3 4
 */

• shift_left, shift_right 범위 내 주어진 횟수만큼 쉬프트 연산 (C++20부터 지원)

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

struct S {
    int value{0};
    bool specified_state{true};

    S(int v = 0) : value{v} {}
    S(S const& rhs) = default;
    S(S&& rhs) { *this = move(rhs); }
    S& operator=(S const& rhs) = default;
    S& operator=(S&& rhs) {
        if (this != &rhs) {
            value = rhs.value;
            specified_state = rhs.specified_state;
            rhs.specified_state = false;
        }
        return *this;
    }
};

ostream& operator<< (ostream& os, vector<S> const& v) {
    for (const auto& s : v)
        s.specified_state ? os << s.value << ' ' : os << "? ";
    return os << '\n';
}

int main() {
    vector<S> v{1,2,3,4,5,6,7};
    cout << v;

    shift_left(v.begin(), v.end(), 3);
    cout << v;

    shift_right(v.begin(), v.end(), 2);
    cout << v;

    return 0;
}

/*
$ g++ test.cpp -std=c++2a
$ ./a.out
1 2 3 4 5 6 7 
4 5 6 7 ? ? ? 
? ? 4 5 6 7 ?
 */

• shuffle 무작위로 원소들을 섞음.

// since C++11
template< class RandomIt, class URBG >
void shuffle( RandomIt first, RandomIt last, URBG&& g );

// ----------------------------------------------------------------------------------
#include <random>
#include <algorithm>
#include <iterator>
#include <iostream>
using namespace std;

int main() {
    vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    random_device rd;
    mt19937 g(rd());

    shuffle(v.begin(), v.end(), g);

    copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
9 2 3 8 1 10 4 6 5 7
$ ./a.out
3 4 1 7 10 6 5 2 8 9
 */

• sample 범위 내에서 무작위로 주어진 개수만큼 원소를 샘플링. (C++17 부터 지원)

// since C++17
template< class PopulationIterator, class SampleIterator,
          class Distance, class URBG >
SampleIterator sample( PopulationIterator first, PopulationIterator last,
                       SampleIterator out, Distance n, URBG&& g);

// ----------------------------------------------------------------------------------
#include <iostream>
#include <random>
#include <string>
#include <iterator>
#include <algorithm>
using namespace std;

int main() {
    string in = "hgfedcba", out;
    sample(in.begin(), in.end(), back_inserter(out), 5,
           mt19937{random_device{}()});
    cout << "five random letters out of " << in;
    cout << " : " << out << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++17
$ ./a.out
five random letters out of hgfedcba : gedcb
$ ./a.out
five random letters out of hgfedcba : hgeda
 */

• unique 중복된 원소를 제거한 후 마지막 원소의 iterator 반환.

  • unique_copy 중복된 원소를 제거한 후 복사. (원본 유지)

// until C++20
template< class ForwardIt >
ForwardIt unique( ForwardIt first, ForwardIt last );

template< class ForwardIt, class BinaryPredicate >
ForwardIt unique( ForwardIt first, ForwardIt last, BinaryPredicate p );

template< class InputIt, class OutputIt >
OutputIt unique_copy( InputIt first, InputIt last, OutputIt d_first );

template< class InputIt, class OutputIt, class BinaryPredicate >
OutputIt unique_copy( InputIt first, InputIt last,
                      OutputIt d_first, BinaryPredicate p );

// since C++20
template< class ForwardIt >
constexpr ForwardIt unique( ForwardIt first, ForwardIt last );

template< class ForwardIt, class BinaryPredicate >
constexpr ForwardIt unique( ForwardIt first, ForwardIt last, BinaryPredicate p );

template< class InputIt, class OutputIt >
constexpr OutputIt unique_copy( InputIt first, InputIt last, OutputIt d_first );

template< class InputIt, class OutputIt, class BinaryPredicate >
constexpr OutputIt unique_copy( InputIt first, InputIt last,
                                OutputIt d_first, BinaryPredicate p );

// since C++17
template< class ExecutionPolicy, class ForwardIt >
ForwardIt unique( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last );

template< class ExecutionPolicy, class ForwardIt, class BinaryPredicate >
ForwardIt unique( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
                  BinaryPredicate p );

template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
ForwardIt2 unique_copy( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last,
                        ForwardIt2 d_first );

template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
          class BinaryPredicate >
ForwardIt2 unique_copy( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last,
                        ForwardIt2 d_first, BinaryPredicate p );

// ----------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cctype>
#include <iterator>
using namespace std;

int main()  {
    // a vector containing several duplicate elements
    vector<int> v{1,2,1,1,3,3,3,4,5,4};

    // remove consecutive (adjacent) duplicates
    auto last = unique(v.begin(), v.end());
    // v now holds {1 2 1 3 4 5 4 x x x}, where 'x' is indeterminate
    v.erase(last, v.end());
    for (int i : v) cout << i << " ";
    cout << endl;

    // sort followed by unique, to remove all duplicates
    sort(v.begin(), v.end()); // {1 1 2 3 4 4 5}
    last = unique(v.begin(), v.end());
    // v now holds {1 2 3 4 5 x x}, where 'x' is indeterminate
    v.erase(last, v.end());
    for (int i : v) cout << i << " ";
    cout << endl;

    string s1 = "The      string    with many       spaces!";
    string s2;
    cout << "before: " << s1 << endl;
    unique_copy(s1.begin(), s1.end(), back_inserter(s2),
                [](char c1, char c2){ return c1 == ' ' && c2 == ' '; });
    cout << "after:  " << s2 << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
1 2 1 3 4 5 4
1 2 3 4 5
before: The      string    with many       spaces!
after:  The string with many spaces!
 */

STL: <algorithm> 헤더파일

• STL 컨테이너의 원소를 탐색, 변경, 관리, 처리할 목적으로 제공되는 함수 집합.

• 컨테이너 뿐만 아니라 일반 배열 구조(int[] 등)에도 적용 가능.

  • 2개의 인자 (first, last)를 이용해서 컨테이너의 범위를 지정하므로, 2개의 인자에 배열의 주소를 직접 주어도 됨.

  • 보통 주어진 범위는 [first, last) 로 지정됨. 마지막 위치는 제외.

• 100 여가지 알고리즘을 제공하며, 대부분의 함수들은 C++11 부터 제공됨.

• 알고리즘의 분류

  • 변경 불가 알고리즘: 원소 값을 변경하지 않음.

  • 변경 가능 알고리즘: 원소 값을 변경.

  • 파티셔닝 알고리즘: 원소들을 두 그룹으로 나눔.

  • 정렬 알고리즘: 원소의 순서를 변경.

  • 이진 탐색 알고리즘: 정렬된 상태에서 원소를 탐색.

  • 병합 알고리즘: 정렬된 상태의 원소들을 병합.

  • 집합 연산 관련 알고리즘: 집합 연산을 제공.

  • 힙 연산 관련 알고리즘: 최대 힙, 최소 힙을 탐색.

  • 최대, 최소 원소 탐색 알고리즘: 주어진 범위의 최댓값과 최솟값을 탐색.

  • 비교 알고리즘: 주어진 두 개의 범위가 동일한지 비교.

  • 순열 알고리즘: 순열 관련 알고리즘.

  • 수치 알고리즘: 부분 합 등 집계 수치 연산 제공.

  • 초기화되지 않은 메모리에 대한 연산

• #include <algorithm>

변경 불가 알고리즘 (Non-modifying Sequence Algorithm)

• all_of 범위 안의 모든 원소가 조건을 만족하는 경우 true를 반환, 그렇지 않으면 false를 반환.

  • 아래의 3번째 매개변수인 UnaryPredicate 는 범위에 적용될 함수 객체인데, 함수 포인터로 이해하면 될 듯. 미리 선언된 함수의 이름을 넘기거나, Lambda 식을 넘기면 됨.

  • any_of 범위 안의 원소 중 하나라도 조건을 만족하는 경우 true를 반환, 그렇지 않으면 false를 반환.

  • none_of 범위 안의 원소 중 어떤 것도 조건을 만족하지 않으면 true를 반환, 그렇지 않으면 false를 반환.

// since C++ 11
template< class InputIt, class UnaryPredicate >
bool all_of( InputIt first, InputIt last, UnaryPredicate p );

// until C++ 20
template< class InputIt, class UnaryPredicate >
constexpr bool all_of( InputIt first, InputIt last, UnaryPredicate p );

// until C++ 20
template< class ExecutionPolicy, class ForwardIt, class UnaryPredicate >
bool all_of( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
             UnaryPredicate p );

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

bool isEven(int i) { return ~(i & 1); }

int main() {
    vector<int> v(10, 2);
    cout << "Lambda as the third parameter: ";
    cout << all_of(v.begin(), v.end(), [](int i){ return i % 2 == 0; }) << endl;

    cout << "Function name as the third parameter: ";
    cout << all_of(v.begin(), v.end(), isEven) << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
Lambda as the third parameter: 1
Function name as the third parameter: 1
 */

• for_each 범위 안의 각각의 원소에 대해 전달된 함수를 호출.

  • 3번째 사용법을 살펴보면, 클래스(struct) 내 오버로딩된 함수(operator())를 넘겼을 때 최종 반환 결과가 객체임에 주의할 것.

  • for_each_n 첫번째 인자에서 두번째 인자로 주어진 개수만큼 전달된 함수를 호출. (C++17 부터 지원)

// until C++20
template< class InputIt, class UnaryFunction >
UnaryFunction for_each( InputIt first, InputIt last, UnaryFunction f );

// since C++20
template< class InputIt, class UnaryFunction >
constexpr UnaryFunction for_each( InputIt first, InputIt last, UnaryFunction f );

// since C++17
template< class ExecutionPolicy, class ForwardIt, class UnaryFunction2 >
void for_each( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
               UnaryFunction2 f );

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

struct Sum {
    void operator()(int n) { sum += n; }
    int sum{0};
};

int main() {
    vector<int> nums{3, 4, 2, 8, 15, 267};

    auto print = [](const int& n) { cout << " " << n; };

    cout << "before:";
    for_each(nums.cbegin(), nums.cend(), print);
    cout << endl;

    for_each(nums.begin(), nums.end(), [](int &n){ n++; });

    // calls Sum::operator() for each number
    Sum s = for_each(nums.begin(), nums.end(), Sum());

    cout << "after: ";
    for_each(nums.cbegin(), nums.cend(), print);
    cout << endl;

    cout << "sum: " << s.sum << endl;
    
    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
before: 3 4 2 8 15 267
after:  4 5 3 9 16 268
sum: 305
 */

• find 범위 안에서 3번째 인자로 주어진 값과 일치하는 원소의 iterator를 반환.

  • find_if 조건과 일치하는 원소의 iterator 를 반환.

  • find_if_not 조건과 일치하지 않는 원소의 iterator 를 반환.

  • set이나 map처럼 연관 컨테이너에서는 find 함수보다 멤버 함수로 제공되는 find 함수를 쓰는 것이 더 효율적임. 멤버 함수는 연관 컨테이너가 정렬된 상태임을 활용하기 때문에 훨씬 빠르게 동작함.

// until C++20
template< class InputIt, class T >
InputIt find( InputIt first, InputIt last, const T& value );

// since C++20
template< class InputIt, class T >
constexpr InputIt find( InputIt first, InputIt last, const T& value );

// since C++17
template< class ExecutionPolicy, class ForwardIt, class T >
ForwardIt find( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
                const T& value );


// until C++20
template< class InputIt, class UnaryPredicate >
InputIt find_if( InputIt first, InputIt last, UnaryPredicate p );

// since C++20
template< class InputIt, class UnaryPredicate >
constexpr InputIt find_if( InputIt first, InputIt last, UnaryPredicate p );

// since C++17
template< class ExecutionPolicy, class ForwardIt, class UnaryPredicate >
ForwardIt find_if( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, 
                   UnaryPredicate p );

// find_if_not 은 find_if 과 인자가 동일
// ----------------------------------------------------------------------------------
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    int n1 = 3, n2 = 5;
    vector<int> v{0, 1, 2, 3, 4};

    auto result1 = find(begin(v), end(v), n1);
    auto result2 = find(begin(v), end(v), n2);

    if (result1 != end(v)) {
        cout << "v contains: " << n1 << endl;
    } else {
        cout << "v does not contain: " << n1 << endl;
    }

    if (result2 != end(v)) {
        cout << "v contains: " << n2 << endl;
    } else {
        cout << "v does not contain: " << n2 << endl;
    }

    auto result3 = find_if(v.begin(), v.end(), [](int i){ return i & 1; });
    if (result3 != end(v)) {
        cout << "odd number: " << *result3 << endl;
    }

    auto result4 = find_if_not(v.begin(), v.end(), [](int i){ return i & 1; });
    if (result4 != end(v)) {
        cout << "even number: " << *result4 << endl;
    }

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
v contains: 3
v does not contain: 5
odd number: 1
even number: 0
 */

• adjacent_find 처음에 연속해서 나타나는 원소의 시작 위치의 iterator를 반환.

  • 3번째 인자로 비교자 함수를 greater<자료형> 으로 줄 경우, 끝에서 최초로 연속해서 나타나는 원소의 시작 위치를 반환.

// until C++20
template< class ForwardIt >
ForwardIt adjacent_find( ForwardIt first, ForwardIt last );

template< class ForwardIt, class BinaryPredicate>
ForwardIt adjacent_find( ForwardIt first, ForwardIt last, BinaryPredicate p );

// since C++20
template< class ForwardIt >
constexpr ForwardIt adjacent_find( ForwardIt first, ForwardIt last );

template< class ForwardIt, class BinaryPredicate>
constexpr ForwardIt adjacent_find( ForwardIt first, ForwardIt last,
                                   BinaryPredicate p );

// since C++17
template< class ExecutionPolicy, class ForwardIt >
ForwardIt adjacent_find( ExecutionPolicy&& policy,
                         ForwardIt first, ForwardIt last );

template< class ExecutionPolicy, class ForwardIt, class BinaryPredicate>
ForwardIt adjacent_find( ExecutionPolicy&& policy,
                         ForwardIt first, ForwardIt last, BinaryPredicate p );

// ----------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;;

int main() {
    vector<int> v1{0, 1, 2, 3, 40, 40, 41, 41, 5};

    auto i1 = adjacent_find(v1.begin(), v1.end());

    if (i1 == v1.end()) {
        cout << "No matching adjacent elements\n";
    } else {
        cout << "The first adjacent pair of equal elements at: ";
        cout << distance(v1.begin(), i1) << endl;
    }

    auto i2 = adjacent_find(v1.begin(), v1.end(), greater<int>());
    if (i2 == v1.end()) {
        cout << "The entire vector is sorted in ascending order" << endl;
    } else {
        cout << "The last element in the non-decreasing subsequence is at: ";
        cout << distance(v1.begin(), i2) << endl;
    }

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
The first adjacent pair of equal elements at: 4
The last element in the non-decreasing subsequence is at: 7
 */

• find_end 주어진 순열이 탐색 범위에서 마지막으로 나타난 위치의 iterator를 반환.

  • 시간 복잡도: O(S * (N - S + 1)), N은 탐색 범위, S는 탐색 대상의 범위

  • 내부적으로 search() 함수를 사용함.

  • 주어진 순열이 포함되었는지 비교하는 함수는 BinaryPredicate p라는 마지막 인자로 넘겨서 커스텀 비교자를 구현할 수 있음.

// until C++20
template< class ForwardIt1, class ForwardIt2 >
ForwardIt1 find_end( ForwardIt1 first, ForwardIt1 last,
                     ForwardIt2 s_first, ForwardIt2 s_last );

template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >
ForwardIt1 find_end( ForwardIt1 first, ForwardIt1 last,
                     ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p );

// since C++20
C++20)
template< class ForwardIt1, class ForwardIt2 >
constexpr ForwardIt1 find_end( ForwardIt1 first, ForwardIt1 last,
                               ForwardIt2 s_first, ForwardIt2 s_last );

template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >
constexpr ForwardIt1 find_end( ForwardIt1 first, ForwardIt1 last,
                               ForwardIt2 s_first, ForwardIt2 s_last,
                               BinaryPredicate p );

// since C++17
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
ForwardIt1 find_end( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last,
                     ForwardIt2 s_first, ForwardIt2 s_last );

template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
          class BinaryPredicate >
ForwardIt1 find_end( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last,
                     ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p );

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

int main() {
    vector<int> v{1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4};
    vector<int>::iterator result;

    vector<int> t1{1, 2, 3};

    result = find_end(v.begin(), v.end(), t1.begin(), t1.end());
    if (result == v.end()) {
        cout << "sequence not found" << endl;
    } else {
        int dist = distance(v.begin(), result);
        cout << "last occurrence is at: " << dist << endl;
    }

    vector<int> t2{4, 5, 6};
    result = find_end(v.begin(), v.end(), t2.begin(), t2.end());
    if (result == v.end()) {
        cout << "sequence not found" << endl;
    } else {
        int dist = distance(v.begin(), result);
        cout << "last occurrence is at: " << dist << endl;
    }

    return 0;
}

/*
$ g++ test.cpp -std=c++11
./a.out
last occurrence is at: 8
sequence not found
 */

• count 범위 안에 주어진 값과 일치하는 원소의 개수를 반환

  • count_if 주어진 조건과 일치하는 원소의 개수를 반환.

// until C++20
template< class InputIt, class T >
typename iterator_traits<InputIt>::difference_type
    count( InputIt first, InputIt last, const T &value );

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

// since C++20
template< class InputIt, class T >
constexpr typename iterator_traits<InputIt>::difference_type
              count( InputIt first, InputIt last, const T &value );

template< class InputIt, class UnaryPredicate >
constexpr typename iterator_traits<InputIt>::difference_type
              count_if( InputIt first, InputIt last, UnaryPredicate p );

// since C++17
template< class ExecutionPolicy, class ForwardIt, class T >
typename iterator_traits<ForwardIt>::difference_type
    count( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
           const T &value );

template< class ExecutionPolicy, class ForwardIt, class UnaryPredicate >
typename iterator_traits<ForwardIt>::difference_type
    count_if( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
              UnaryPredicate p );

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

int main() {
    vector<int> v{ 1, 2, 3, 4, 4, 3, 7, 8, 9, 10 };

    // determine how many integers in a vector match a target value.
    int target1 = 3, target2 = 5;
    int num_items1 = count(v.begin(), v.end(), target1);
    int num_items2 = count(v.begin(), v.end(), target2);
    cout << "number: " << target1 << " count: " << num_items1 << endl;
    cout << "number: " << target2 << " count: " << num_items2 << endl;

    // use a lambda expression to count elements divisible by 3.
    int num_items3 = count_if(v.begin(), v.end(), [](int i){return i % 3 == 0;});
    cout << "number divisible by three: " << num_items3 << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
number: 3 count: 2
number: 5 count: 0
number divisible by three: 3
 */

• search 범위 안에서 주어진 순열이 포함되는 첫번째 위치의 iterator를 반환.

  • 시간 복잡도: O(S * N), 범위의 크기 = N, 주어진 순열의 크기 = S

// until C++20
template< class ForwardIt1, class ForwardIt2 >
ForwardIt1 search( ForwardIt1 first, ForwardIt1 last,
                   ForwardIt2 s_first, ForwardIt2 s_last );

template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >
ForwardIt1 search( ForwardIt1 first, ForwardIt1 last,
                   ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p );

// since C++20
template< class ForwardIt1, class ForwardIt2 >
constexpr ForwardIt1 search( ForwardIt1 first, ForwardIt1 last,
                             ForwardIt2 s_first, ForwardIt2 s_last );

template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >
constexpr ForwardIt1 search( ForwardIt1 first, ForwardIt1 last,
                             ForwardIt2 s_first, ForwardIt2 s_last,
                             BinaryPredicate p );


template<class ForwardIt, class Searcher>
constexpr ForwardIt search( ForwardIt first, ForwardIt last,
                            const Searcher& searcher );

// since C++17
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
ForwardIt1 search( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last,
                   ForwardIt2 s_first, ForwardIt2 s_last );

template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
          class BinaryPredicate >
ForwardIt1 search( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last,
                   ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p );

// since C++17 until C++20
template<class ForwardIt, class Searcher>
ForwardIt search( ForwardIt first, ForwardIt last, const Searcher& searcher );

// ----------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
using namespace std;

template <typename Container>
bool in_quote(const Container& cont, const string& s) {
    return search(cont.begin(), cont.end(), s.begin(), s.end()) != cont.end();
}

int main() {
    string str = "why waste time learning, when ignorance is instantaneous?";
    // str.find() can be used as well
    cout << boolalpha << in_quote(str, "learning") << endl;
    cout << in_quote(str, "lemming")  << endl;

    vector<char> vec(str.begin(), str.end());
    cout << boolalpha << in_quote(vec, "learning") << endl;
    cout << in_quote(vec, "lemming")  << endl;

    // The C++17 overload demo:
    string in = "Lorem ipsum dolor sit amet, consectetur adipiscing elit,"
        " sed do eiusmod tempor incididunt ut labore et dolore magna aliqua";
    string needle = "pisci";
    auto it = search(in.begin(), in.end(), boyer_moore_searcher(needle.begin(), needle.end()));
    if(it != in.end()) {
        cout << "The string " << needle << " found at offset ";
        cout << it - in.begin() << endl;
    } else {
        cout << "The string " << needle << " not found" << endl;
    }

    return 0;
}

/*
$ g++ test.cpp -std=c++17
$ ./a.out
true
false
true
false
The string pisci found at offset 43
 */

• search_n 범위 안에서 주어진 순열을 count번 반복한 순열의 위치(iterator)를 반환.

  • 시간 복잡도: O(N), 범위의 크기 = N

// until C++20
template< class ForwardIt, class Size, class T >
ForwardIt search_n( ForwardIt first, ForwardIt last, Size count, const T& value );

template< class ForwardIt, class Size, class T, class BinaryPredicate >
ForwardIt search_n( ForwardIt first, ForwardIt last, Size count, const T& value, 
                     BinaryPredicate p );

// since C++20
template< class ForwardIt, class Size, class T >
constexpr ForwardIt search_n( ForwardIt first, ForwardIt last, Size count,
                              const T& value );

template< class ForwardIt, class Size, class T, class BinaryPredicate >
constexpr ForwardIt search_n( ForwardIt first, ForwardIt last, Size count,
                              const T& value, BinaryPredicate p );

// since C++17
template< class ExecutionPolicy, class ForwardIt, class Size, class T >
ForwardIt search_n( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
                    Size count, const T& value );

template< class ExecutionPolicy, class ForwardIt, class Size, class T,
          class BinaryPredicate >
ForwardIt search_n( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
                    Size count, const T& value, BinaryPredicate p );

// ----------------------------------------------------------------------------------
#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;

template <class Container, class Size, class T>
bool consecutive_values(const Container& c, Size count, const T& v) {
  return search_n(begin(c),end(c),count,v) != end(c);
}

int main() {
   const char sequence[] = "1001010100010101001010101";

   cout << boolalpha;
   cout << "Has 4 consecutive zeros: " << consecutive_values(sequence,4,'0') << endl;
   cout << "Has 3 consecutive zeros: " << consecutive_values(sequence,3,'0') << endl;

   return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
Has 4 consecutive zeros: false
Has 3 consecutive zeros: true
 */

• mismatch 범위 안에서 주어진 순열과 처음으로 일치하지 않는 위치의 iterator를 반환

개념

• 정의 (위키백과)

표준 템플릿 라이브러리(STL: Standard Template Library)는 C++을 위한 라이브러리로서 C++ 표준 라이브러리의 많은 부분에 영향을 끼쳤다. 이것은 알고리즘, 컨테이너, 함수자 그리고 반복자라고 불리는 네가지의 구성 요소를 제공한다.

STL은 컨테이너와 연관 배열 같은 C++을 위한 일반 클래스들의 미리 만들어진 집합을 제공하는데, 이것들은 어떤 빌트인 타입과도 그리고 어떤 사용자 정의 타입과도 같이 사용될 수 있다. STL 알고리즘들은 컨테이너들에 독립적인데, 이것은 라이브러리의 복잡성을 눈에 띄게 줄여주었다.

STL은 결과를 템플릿의 사용을 통해 달성한다. 이 접근법은 전통적인 런타임 다형성에 비해 훨씬 효과적인 컴파일 타임 다형성을 제공한다. 현대의 C++ 컴파일러들은 STL의 많은 사용에 의해 야기되는 어떤 추상화 패널티도 최소화하도록 튜닝되었다.

STL은 제네릭 알고리즘과 C++을 위한 데이터 구조체들의 첫 번째 라이브러리로서 만들어졌다. 이것은 다음의 네가지를 기초로 한다. 제네릭 프로그래밍, 효율성을 잃지 않은 추상화, 폰 노이만 구조 그리고 밸류 시멘틱스(value semantics)가 그것이다.

• 구성요소

  • 컨테이너(container): 데이터를 저장하는 객체의 집합으로, 연속 컨테이너(sequence container)와 연관 컨테이너(associative container)로 분류됨.

  • 반복자(iterator): 컨테이너에 저장된 객체를 참조하는 포인터.

  • 알고리즘(algorithm): 정렬, 삭제, 검색 등에 대한 함수를 제공

  • 함수 객체(function object): operator()를 오버로드하는 클래스의 인스턴스로, 함수처럼 동작하는 객체. C++에서는 사칙 연산과 관련해서 몇 가지 함수 객체를 제공함. 예를 들면, plus<자료형>()과 times<자료형>() 이 있음. STL의 알고리즘의 인자로 함수 객체를 넘길 수 있는데, 이는 C 언어에서 함수 포인터를 사용했을 때보다 훨씬 빠르게 동작함. 그 이유는 함수 포인터는 실행될 때까지 확인될 수 없기 때문에 인라인(inline)으로 만들어질 수 없으나, 함수 객체는 컴파일 시에 결정되기 때문에 컴파일러는 operator() 호출을 인라인으로 만들어 성능이 증가하기 때문임.

  • 어댑터(container adaptor): STL 구성 요소를 새로운 구성 요소로 보이게 하는 기능으로, 다른 컨테이너들을 사용하면서 특정한 인터페이스와 함께하는 컨테이너

  • 할당기(allocator): 컨테이너의 메모리 할당 정책을 담당

연속 컨테이너 (Sequence Container)

• 표준 연속 컨테이너들은 vector, deque, 그리고 list를 포함.

• vector<자료형>

  • STL에서 가장 많이 사용되는 컨테이너 라이브러리

  • C 배열과 같은 동적 배열로서 객체를 삽입하거나 제거할 때 자동으로 자신의 크기를 조정하는 능력을 갖는다.

  • vector의 end에 요소를 삽입하는 것은 상환 상수 시간(amortized constant time)을 필요로 한다.

  • 마지막 요소를 제거하는 것은 단지 상수 시간을 필요로 하는데, 크기 조정이 일어나지 않기 때문이다.

  • 처음 또는 중간에 삽입하거나 삭제하는 것은 뒤의 원소들을 뒤나 앞으로 옮겨야하므로 선형 시간이 든다.

  • bool 타입을 위한 특수화가 존재하는데 이것은 불린 값을 비트에 저장하기 위해 공간을 최적화한다.

  • 메모리 상에서 연속된 위치에 데이터를 저장하므로, memcpy()나 memset() 등의 함수를 이용하여 직접적인 데이터 수정 가능.

  • vector에서 제공하는 자주 쓰이는 멤버 함수로는 push_back(), pop_back(), front(), back() 이 있으며, 함수명에서 알 수 있듯이 뒤쪽에서만 데이터 삽입, 삭제가 가능함. 중간에 데이터를 수정하고 싶다면 다른 라이브러리를 사용해야 함.

  • 배열과의 차이점: 크기가 동적으로 변하며, 중간에 데이터 삽입 및 삭제가 가능.

  • 배열과의 공통점: 구현이 쉽고, 랜덤 접근(random access)이 가능.

  • 미리 크기를 알 수 있는 데이터 저장에 가장 적합하고, 크기가 가변적인 경우라도 뒤쪽에서만 데이터 삽입, 삭제가 빈번하게 발생할 경우 유용하게 사용됨. 그 외에도 랜덤 접근이 자주 발생하고 빠른 속도를 요구할 때 이용됨. 실제로 앞에서 삽입, 삭제가 많이 일어날 경우 다른 컨테이너 사용이 권장됨.

  • vector는 capacity() 함수를 통해 메모리 재할당 없이 최대 늘릴 수 있는 크기를 제공하며, 이는 size() 함수(=원소의 개수)와는 다른 용도임. 즉, 처음 할당 시 지정한 공간보다 넉넉하게 메모리를 잡기 때문에 미리 크기를 알 경우 메모리 재할당에 따른 추가 연산을 막을 수 있음.

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

int main() {
    cout << "Vector" << endl;
    vector<int> v;
    
    for (int i = 9; i > 0; i--) {
        v.push_back(i);
    }
    
    cout << v.front() << endl; // 9
    cout << v.back() << endl; // 1
    cout << v.size() << endl; // 9
    
    for (vector<int>::iterator iter = v.begin(); iter != v.end(); iter++) {
        cout << *iter << ", ";
    }
    cout << endl;
    
    // or
    for (auto it = v.begin(); it != v.end(); it++) {
        cout << *it << ", ";
    }
    cout << endl;
    
    v.pop_back();
    cout << v.back() << endl; // 2
    cout << v.empty() << endl; // 0 (= false)
    
    // 초기화되지 않은 경우 0으로 채워지지만, 이미 값이 있는 경우 크기만 줄인다.
    v.resize(3, 0);
    cout << v.size() << endl; // 3
    // 9, 8, 7
    for (auto it = v.begin(); it != v.end(); it++) {
        cout << *it << ", ";
    }
    cout << endl << "Vector2" << endl;
    
    vector<int> v2;
    v2.resize(5, 0);
    cout << v2.size() << endl; // 5
    for (auto it = v2.begin(); it != v2.end(); it++) {
        cout << *it << ", "; // 0
    }
    cout << endl;
    
    return 0;
}

• deque<자료형>

  • 앞, 뒤 모두에서 데이터 삽입 및 삭제가 가능.

  • 다른 기능들이 vector보다 성능이 떨어지기 때문에 자주 사용되지 않음.

  • vector와의 공통점은 메모리 상에 연속된 위치에 데이터가 저장되며, 중간 삽입 및 삭제가 용이하지 않다는 것. 즉, 멤버 함수가 제공되지 않음.

  • 대표적인 멤버 함수로는 push_front(), push_back(), pop_front(), pop_back(), front(), back() 이 있음.

• list<자료형>

  • 자료구조의 이중 연결 리스트를 템플릿으로 구현해 놓은 것으로, 중간에 데이터 삽입 및 삭제가 가장 빠름.

  • 메모리 상에서 데이터들이 흩어져서 저장되어 있으므로, vector나 deque처럼 연속된 메모리에 저장되는 컨테이너에 비해 읽는 속도가 굉장히 느림. 캐싱(caching) 작업을 할 때 인접한 메모리들도 함께 가져오기 때문에 list의 경우 캐싱으로 얻는 이점이 다른 컨테이너보다 적음. 또한, list는 각 엔트리마다 이전, 다음 엔트리를 가리키는 포인터를 저장해야 하므로 크기도 vector보다 커서 실제 메모리(물리 메모리) 상에 인접한 곳에 있어도 요소를 적게 가져오게 됨. 따라서 순회가 빈번한 경우 list 는 사용하지 않는 것이 좋음.

  • 느린 검색과 접근(선형 시간)을 갖지만, 한 번 위치가 찾아지면 빠른 삽입과 삭제가 가능(상수 시간).

  • 대표적인 멤버 함수로는 push_front(), push_back(), pop_front(), pop_back(), front(), back()가 있음.

  • 중간에 데이터를 삽입하는 함수로는 insert()가 있고, 삭제하는 함수로는 erase()가 있는데 매개변수에 따라 종류가 3가지로 나뉨.

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

int main () {
    list<int> mylist;
    list<int>::iterator it;

    // set some initial values:
    for (int i = 1; i < 6; ++i) mylist.push_back(i);       // 1 2 3 4 5

    it = mylist.begin();
    ++it;             // it points now to number 2              ^

    mylist.insert(it,10);                                  // 1 10 2 3 4 5

    // "it" still points to number 2                               ^
    mylist.insert(it, 2, 20);                              // 1 10 20 20 2 3 4 5

    --it;             // it points now to the second 20                ^

    vector<int> v(2, 30);
    mylist.insert(it, v.begin(), v.end());                 // 1 10 20 30 30 20 2 3 4 5
                                                           //                ^
    
    cout << "mylist contains:";
    for (it = mylist.begin(); it != mylist.end(); ++it)
        cout << ' ' << *it;
    cout << '\n';

    return 0;
}

/*
mylist contains: 1 10 20 30 30 20 2 3 4 5
 */

#include <iostream>
#include <list>
using namespace std;

int main ()
{
    list<int> mylist;
    list<int>::iterator it1, it2;

    // set some values:
    for (int i=1; i<10; ++i) mylist.push_back(i * 10);

                                   // 10 20 30 40 50 60 70 80 90
    it1 = it2 = mylist.begin();    // ^^
    advance(it2, 6);               // ^                  ^
    ++it1;                         //     ^              ^

    it1 = mylist.erase(it1);       // 10 30 40 50 60 70 80 90
                                   //     ^           ^

    it2 = mylist.erase(it2);       // 10 30 40 50 60 80 90
                                   //     ^           ^

    ++it1;                         //        ^        ^
    --it2;                         //        ^     ^

    mylist.erase(it1, it2);        // 10 30 60 80 90
                                   //        ^

    cout << "mylist contains:";
    for (it1=mylist.begin(); it1!=mylist.end(); ++it1)
        cout << ' ' << *it1;
    cout << '\n';

    return 0;
}

/*
mylist contains: 10 30 60 80 90
 */

연관 컨테이너 (Associative Container)

• 키(Key)와 값(Value)의 짝(pair)으로 이루어진 자료구조(아닌 것도 있으나 자주 사용되지 않음)를 구현한 컨테이너.

• 저장된 자료의 순서와 상관없이 특정 기준에 맞게 저장(주로 키 값의 정렬 순서대로 저장).

• 간단한 연관 컨테이너로 pair와 tuple이 있음.

• pair<자료형, 자료형>

  • 데이터 요소의 2-튜플 또는 객체들로(고정된 순서에 따라 변수명.first 그리고 변수명.second로 접근 가능) 이루어짐.

  • STL 내부적으로 많이 사용되며, 함수의 리턴 값이 2개가 필요할 경우 사용됨.

  • map 또는 hash_map 에서 할당된 객체들의 배열은 기본 값으로 pair 타입을 가지며, 배치 및 복사 그리고 비교할 수 있음.

  • 비교 시 모든 first 요소들이 유니크 키로서 동작하고 second 요소는 키에 매핑되는 값 혹은 객체로 동작함.

  • 다른 컨테이너에 자료형으로 pair를 쓰는 경우 make_pair<자료형, 자료형>(값, 값) 함수로 pair 객체를 만들어서 컨테이너에 저장함.

  • C++11 부터 emplace_back() 이라는 함수를 제공하여 객체를 받는 대신, 객체의 생성자의 매개변수를 받아 vector 내부에서 직접 객체를 생성하므로 임시 객체를 생성하고 파괴 및 복사하는 추가 연산이 필요 없음.

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

int main() {
    vector<pair<int, double> > v;
    v.push_back(make_pair(3, 5.0)); // same as "v.emplace_back(3, 5.0);"

    pair<int, double> p;
    p.first = 10;
    p.second = 15.5;
    v.push_back(p);
    
    cout << p.first << ", " << p.second << endl;
    
    return 0;
}

• tuple<자료형, 자료형, ..., 자료형>

  • 3개 이상의 값을 반환하거나 저장할 때 사용되는 컨테이너.

  • pair와 유사하게 make_tuple<자료형, 자료형, ..., 자료형>(값, 값, ..., 값) 함수로 객체를 생성할 수 있음.

  • 그러나 값을 꺼내올 경우 get<인덱스>(변수명) 를 사용하여야 함. (멤버 함수 아님.)

#include <iostream>
#include <tuple>
using namespace std;

int main() {
    tuple<int, double, bool> T(10, 15.5, true);
    
    // or
    T = make_tuple<int, double, bool>(10, 15.5, true);
    
    cout << get<0>(T) << endl; // 10
    cout << get<1>(T) << endl; // 15.5
    cout << get<2>(T) << endl; // 1 (=true)
    
    return 0;
}

• 표준 연관 컨테이너들은 set, multiset, map, multimap, unordered_set, unordered_map, unordered_multiset 그리고 unordered_multimap를 포함하며, 모두 정렬된 구조.

• 정렬되지 않는 경우 명칭이 "unordered_컨테이너명"가 됨.

• 보통 키를 기준으로 정렬하기 때문에 중복된 키 값을 입력할 수 없으나, mutli-가 붙은 컨테이너들은 중복된 키를 가질 수 있음.

• map<Key 자료형, Value 자료형>

  • 하나의 데이터 아이템(키)에서 다른 것(값)으로 매핑을 허용.

  • 키의 타입은 반드시 비교 연산 < 또는 명시된 커스텀 비교자를 통해 구현되어야 함. (map<자료형, 자료형, 비교자> 로 선언)

  • 이러한 비교 연산 또는 비교자 함수는 반드시 strict weak ordering을 보장해야 하며, 아니면 행위가 정의되지 않음.

  • 일반적으로 자가 균형 이진 탐색 트리(Red-Black Tree)를 사용해서 구현됨.

  • 자주 사용되는 멤버 함수로는 insert(), erase(), find(), count() 등이 있음.

  • 정렬된 상태로 많은 데이터를 저장하고, 빠른 검색이 필요하며, 삽입 및 삭제 연산이 빈번하게 일어나지 않는 경우에 굉장히 효율적으로 사용됨.

  • multimap 같은 키(Key)로 여러 개의 값(Value) 입력 가능. #include <map>

  • unordered_map C++11에서 해시 테이블로 구현된 것으로, 정렬되지 않으나, 검색 속도가 빠름. #include <unordered_map>

  • unordered_multimap 같은 키(Key)로 여러 개의 값(Value) 입력 가능하며, 정렬되지 않은 상태로 저장. #include <unordered_multimap>

#include <iostream>
#include <map>
using namespace std;

int main() {
    map<int, double> m;

    // How to insert
    m.insert(make_pair<int, double>(5, 10.1));
    m.insert(pair<int, double>(3, 15.5));
    m.insert({7, 8.123}); // using initializer_list
    m.emplace(1, 5.5); // C++11
    m[123] = 0.3145723;


    // How to read
    cout << m[3] << endl; // 15.5

    for (auto it = m.begin(); it != m.end(); it++) {
        cout << "(" << it->first << ", " << it->second << ")" << endl;
    }

    // How to delete
    map<int, double>::iterator it = m.find(3);
    m.erase(it);    // erasing by iterator
    m.erase(1);     // erasing by key
    it = m.find(7);
    m.erase(it, m.end()); // erasing by range

    cout << "After deleting ..." << endl;
    for (auto it = m.begin(); it != m.end(); it++) {
        cout << "(" << it->first << ", " << it->second << ")" << endl;
    }

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
15.5
(1, 5.5)
(3, 15.5)
(5, 10.1)
(7, 8.123)
(123, 0.314572)
After deleting ...
(5, 10.1)
 */

• set<Key 자료형>

  • 키(Key)만으로 이루어진 이진트리 자료구조로, map과 마찬가지로 자가 균형 이진 탐색 트리(Red-Black Tree)로 구현됨.

  • 수학의 집합(set)을 표현한 자료구조이기 때문에, 집합 연산(union, intersection, difference, symmetric difference) 그리고 포함 테스트를 제공.

  • 키의 타입은 반드시 비교 연산 < 또는 명시된 커스텀 비교자 함수를 통해서 구현되어야 함.

  • 이러한 비교 연산 또는 비교자 함수는 반드시 strict weak ordering을 보장해야 하며, 아니면 행위가 정의되지 않음.

  • map과 마찬가지로 자주 사용되는 멤버 함수로는 insert(), erase(), find() 등이 있음.

  • 정렬된 상태로 많은 데이터를 저장하고 빠른 검색 속도를 필요로 하는 경우 (특정 값의 유무를 파악해야 할 때 등) 효율적으로 사용됨.

  • mutliset 중복 요소들을 허용. #include <set>

  • unordered_set C++11에서 해시 테이블로 구현됨. 정렬되지 않은 대신 검색 속도가 빠름. #include <unordered_set>

  • unordered_mutliset 중복 요소 허용 및 정렬되지 않으나 빠른 검색 속도 제공. #include <unordered_set>

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s{9, 7, 5, 1, 3}; // 1, 3, 5, 7, 9
    s.insert(4); // 1, 3, 4, 5, 7, 9
    s.insert(4); // no new element inserted.

    for (auto it = s.begin(); it != s.end(); it++)
        cout << (*it) << ", ";
    cout << endl;

    auto found = s.find(5);
    if (found != s.end())
        cout << "Found:" << *found << endl;

    cout << endl << "After inserting 123:" << endl;
    s.insert(found, 123);
    for (auto it = s.begin(); it != s.end(); it++)
        cout << (*it) << ", ";
    cout << endl;

    cout << endl << "After inserting an array:" << endl;
    int arr[] = {20, 21, 23, 25};
    s.insert(arr, arr + 4);
    for (auto it = s.begin(); it != s.end(); it++)
        cout << (*it) << ", ";
    cout << endl;

    cout << endl << "After erasing:" << endl;
    found = s.find(4);
    s.erase(found);             // erasing by iterator
    s.erase(9);                // erasing by key
    found = s.find(23);
    s.erase(found, s.end());    // erasing by range
    for (auto it = s.begin(); it != s.end(); it++)
        cout << (*it) << ", ";
    cout << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
1, 3, 4, 5, 7, 9,
Found:5

After inserting 123:
1, 3, 4, 5, 7, 9, 123,

After inserting an array:
1, 3, 4, 5, 7, 9, 20, 21, 23, 25, 123,

After erasing:
1, 3, 5, 7, 20, 21,
 */

반복자(Itrerator)

• 컨테이너 내 객체를 참조하는 포인터로, 컨테이너명<자료형>::iterator 변수명 = ... 으로 선언하여 사용함.

• ++나 --, 그리고 -> 또는 *과 같은 포인터 연산이 대부분 그대로 사용됨.

• 우항에는 일반적으로 컨테이너명.begin(); 이 들어가는데, begin()과 end()는 0번 인덱스와 마지막 인덱스 + 1의 위치를 참조하고 있음.

• 반대로 순회하길 원할 경우 rbegin()과 rend()를 활용하면 됨.

• 반복자의 종류로는 Input, Output, Forward, Bidirectional, Random Access가 있음.

  • Input과 Output은 입/출력을 담당하는 최소한의 기능만을 가진 반복자.

  • Forward와 Bidirectional은 순회하는 방향에 따라 지어진 이름으로, 각각 순방향과 양방향을 의미함. 즉, bidirectional 반복자는 양방향으로 이동하면서 데이터를 참조할 수 있음.

  • Random Access는 말 그대로 무작위로 데이터에 접근할 수 있는 반복자.

  • 포함 범위: Input/Output < Forward < Bidirectional < Random Access

• 각 컨테이너의 반복자를 반환하는 멤버 함수로 begin(), end(), rbegin(), rend(), cbegin(), cend(), crbegin(), crend()가 있음.

  • begin()과 end()는 순방향으로 데이터를 조회하기 위한 함수.

  • rbegin()과 rend()는 반대로 순회(역방향)하기 위해 각각 마지막 원소와 첫 원소 - 1 의 위치를 참조함.

  • cbegin()과 cend()는 auto 키워드를 사용할 경우 상수 타입(const)의 반복자를 받지 못하는 문제를 개선하기 위해 C++11부터 도입된 것으로 상수 반복자를 반환함.

  • crbegin()과 crend()는 역방향 상수 반복자를 반환.

• auto 키워드 사용 시 상수 반복자를 반환하는 멤버 함수를 사용해야 함.

  • auto it = v.cbegin();

제네릭 프로그래밍 (Generic Programming)

• 데이터 형식에 의존하지 않고, 하나의 값이 여러 다른 데이터 타입들을 가질 수 있는 기술에 중점을 두어 재사용성을 높일 수 있는 프로그래밍 방식.

• 여러가지 유용한 소프트웨어 컴포넌트들을 체계적으로 융합하는 방법을 연구하는 것으로, 그 목적은 알고리즘, 데이터 구조, 메모리 할당 메커니즘, 그리고 기타 여러 소프트웨어적인 장치들을 발전시켜 이들의 재사용성, 모듈화, 사용 편이성을 보다 높은 수준으로 끌어올리고자 하는 것.

• 프로그래밍 패러다임의 하나로, 다양한 데이터 타입에 대해 동일한 연산을 수행할 수 있는 다형성을 보장함.

• C++ 에서는 템플릿(template)으로 선언한 자료형을 사용하면 제네릭 프로그래밍을 할 수 있음.

  • 아래와 같은 방법을 함수 템플릿(Function Template)이라고 함.

#include <iostream>
using namespace std;

template <typename T>

T add(T a, T b) {
    return a + b;
}

int main() {
    int x1 = 3, y1 = 5;
    cout << add(x1, y1) << endl; // 8
    
    double x2 = 3.2, y2 = 4.5;
    cout << add(x2, y2) << endl; // 7.7
    
    return 0;
}

• C++에서 일반적인 자료 구조와 알고리즘을 구현해 놓은 라이브러리 집합을 제공하는데, 이를 표준 템플릿 라이브러리(Standard Template Library, STL)이라고 함.

  • 지원하는 자료구조에는 vector, map, set 등이 있으며, 여러 가지 탐색 변경 알고리즘을 지원함.

  • 각 자료구조의 데이터 타입은 템플릿으로 선언되어 있어서 자료구조마다 다양한 데이터 타입에 대해 사용 가능.

  • 자료의 유형에 상관없이 구현되어 있어 generic 이라고 말하기도 함.

template < class T, class Alloc = allocator<T> > class vector; // generic template

• C++에서 template <typename T> 선언 시, 컴파일 될 때 T가 구체적인 타입으로 해석되어 지는데, 이는 사용된 모든 타입에 대해 인스턴스화를 진행하기 때문임.

template <typename T>
T max(T a, T b) { return a > b ? a : b; }

// 위 함수는 컴파일 시점에 인스턴스화가 진행되어 아래의 함수들이 생성됨.
int Max(int a, int b) { return a > b ? a : b; }
float Max(float a, float b) { return a > b ? a : b; }
double Max(double a, double b) { return a > b ? a : b; }
// ...

클래스 템플릿 (Class Template)

• 템플릿 적용 전: 하나의 데이터 타입만 허용하는 클래스

class Data {
private:
    int data;
public:
    Data(int d) { data = d; }
    void setData(int d) { data = d; }
    int getData() const { return data; }
};

• 템플릿 적용 후: 여러 데이터 타이을 허용하는 클래스

template <typename T>

class Data {
private:
    T data;
public:
    Data(T d) { data = d; }
    void setData(T d) { data = d; }
    T getData() const { return d; }
};

• 템플릿을 정의할 때 typename과 class 키워드가 있음. 보통은 둘 다 사용 가능.

template <typename T1>
template <class T2>

• 그러나, 둘을 혼용할 수 없는 특수한 경우가 있음.

• 의존적인 형(dependent type)인 경우, typename만 사용 가능.

  • 즉, 다른 템플릿 타입과 관련된 타입을 사용하는 경우.

  • 중첩 의존 타입 이름(nested dependent typename)을 식별하는 용도는 typename 키워드이며, 클래스 내부 서브 타입을 지정할 때 사용된다.

// typename만 사용 가능한 경우
template <typename param_t>

class Foo {
    typedef typename param_t::baz sub_t;
};

• 템플릿 타입에 대해 템플릿을 정의하는 경우, class만 사용 가능.

  • template template 구문에서는 classa만 사용되며, 템플릿을 인스턴스화 할 때에도 class만 사용됨.

  • typename은 템플릿 내부에서만 사용되고, 초기화 리스트 및 기본 클래스 리스트에서는 사용 불가.

// class만 사용 가능한 경우
template <template <typename, typename> class Container, typename Type>
template class Foo<int>;