<algorithm> 헤더를 포함해야 한다. (아래에 정의된) Operators 범주는 예외이다. Operators 범주에서 총칭 알고리즘을 사용하려면 <numeric> 헤더를 포함해야 한다.
이전 장에 표준 템플릿 라이브러리(STL)를 소개했다. STL의 중요한 요소인 총칭 알고리즘은 다루지 않았는데 범위가 아주 넓기 때문이다. 시간이 지나면서 STL은 크게 성장했다. 주로 템플릿의 중요성이 높아진 덕분이다. STL 장에 총칭 알고리즘을 다루면 좀 이상할 것 같았다. 그래서 총칭 알고리즘에 따로 별도의 장을 할애했다.
sort 총칭 알고리즘이다. 대조적으로 C라면 프로그래머가 직접 역호출 함수를 작성해야 하며 이 함수는 유형에 안전하지 않은 void const * 매개변수를 사용하지 않을 수 없다. 때문에 내부적으로 프로그래머는 유형 변환에 의존하지 않을 수 없는데 반하여, STL의 sort에서는 그저 다음과 비슷하게 서술하기만 하면 된다.
sort(first-element, last-element)
가능하면 총칭 알고리즘을 사용해야 한다. 자주 마주하는 알고리즘을 위하여 따로 코드를 설계하고 싶은 욕망은 버리는게 좋다. 습관처럼 먼저 총칭 알고리즘 중에서 적절한 후보를 골라야 한다. 총칭 알고리즘은 코드를 작성할 때 여러분이 고른 무기가 되어야 한다. 완전히 사용법을 숙지하고 `습관'처럼 익히시기를 바란다.
이 장은 STL의 총칭 알고리즘을 알파벳 순으로 나누어서 연구한다. 각 알고리즘에 대하여 다음 정보를 제공한다.
Type은 총칭 데이터 유형을 가리킨다. 또, 특별한 유형의 반복자는 물론이고 (예를 들어 plus<Type> 같이 이항 연산을 수행하는) 다른 총칭 유형도 필요하면 언급한다 (18.2절). 반복자는 추상 컨테이너와 거의 미리-정의된 데이터 구조로 제공되지만 어느 시점이 되면 자신만의 반복자를 설계하고 싶을 것이다. 22.14절에 자신만의 반복자 클래스를 구성하는데 필요한 지침을 제공하고 다양한 유형의 반복자를 구현해야 하는 연산자들을 소개한다.
거의 모든 총칭 알고리즘은 반복자 [first, last) 범위를 요구하는데, 이 범위의 원소에 알고리즘이 적용된다. 반복자는 객체나 값을 가리킨다. 반복자가 Type 값이나 객체를 가리킬 때 알고리즘이 사용하는 함수객체는 Type const & 객체나 값을 받는다. 함수객체는 인자로 받은 객체를 변경할 수 없다. 이 사실은 총칭 알고리즘을 변형하기에는 적용되지 않는다. 물론 알고리즘이 적용되는 객체는 변경할 수 있다.
총칭 알고리즘을 범주별로 나눌 수 있다. 이 책에서는 다음 범주와 같이 총칭 알고리즘을 분류한다.
all_of; any_of; none_of; is_premutation; is_sorted; is_sorted_until; is_heap; is_heap_until; minmax_element; copy_n; copy_if; move; move_backward; iota;
equal; includes; lexicographical_compare; max; min; mismatch;
copy; copy_backward; partial_sort_copy; remove_copy; remove_copy_if; replace_copy; replace_copy_if; reverse_copy; rotate_copy; unique_copy;
count; count_if;
make_heap; pop_heap; push_heap; sort_heap;
fill; fill_n; generate; generate_n;
accumulate; adjacent_difference; inner_product; partial_sum;
adjacent_find; binary_search; equal_range; find; find_end; find_first_of; find_if; lower_bound; max_element; min_element; search; search_n; set_difference; set_intersection; set_symmetric_difference; set_union; upper_bound;
inplace_merge; iter_swap; merge; next_permutation; nth_element; partial_sort; partial_sort_copy; partition; prev_permutation; random_shuffle; remove; remove_copy; remove_copy_if; remove_if; reverse; reverse_copy; rotate; rotate_copy; sort; stable_partition; stable_sort; swap; unique; exchange;
for_each; replace; replace_copy; replace_copy_if; replace_if; transform; unique_copy;
<numeric>
Type accumulate(InputIterator first, InputIterator last, Type init);
Type accumulate(InputIterator first, InputIterator last, Type init, BinaryOperation op);
#include <numeric>
#include <vector>
#include <iostream>
using namespace std;
int main()
{
int ia[] = {1, 2, 3, 4};
vector<int> iv(ia, ia + 4);
cout <<
"Sum of values: " << accumulate(iv.begin(), iv.end(), int()) <<
"\n"
"Product of values: " << accumulate(iv.begin(), iv.end(), int(1),
multiplies<int>()) << '\n';
}
/*
출력:
Sum of values: 10
Product of values: 24
*/
<numeric>
OutputIterator adjacent_difference(InputIterator first, InputIterator last, OutputIterator result);
OutputIterator adjacent_difference(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation op);
op 연산자의 결과와 같다. 이 연산자는 입력 범위에서 상응하는 원소(왼쪽 피연산자)와 그리고 그의 이전 원소(오른쪽 피연산자)에 적용된다.
#include <numeric>
#include <vector>
#include <iterator>
#include <iostream>
using namespace std;
int main()
{
int ia[] = {1, 2, 5, 10};
vector<int> iv(ia, ia + 4);
vector<int> ov(iv.size());
adjacent_difference(iv.begin(), iv.end(), ov.begin());
copy(ov.begin(), ov.end(), ostream_iterator<int>(cout, " "));
cout << '\n';
adjacent_difference(iv.begin(), iv.end(), ov.begin(), minus<int>());
copy(ov.begin(), ov.end(), ostream_iterator<int>(cout, " "));
cout << '\n';
}
/*
출력:
1 1 3 5
1 1 3 5
*/
<algorithm>
ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last);
OutputIterator adjacent_find(ForwardIterator first, ForwardIterator last, Predicate pred);
last가 반환된다.
pred가 true를 돌려주는 첫 쌍의 첫 원소를 가리키는 반복자를 돌려준다. 그런 원소가 존재하지 않으면 last가 반환된다.
#include <algorithm>
#include <string>
#include <iostream>
using namespace std;
class SquaresDiff
{
size_t d_minimum;
public:
SquaresDiff(size_t minimum)
:
d_minimum(minimum)
{}
bool operator()(size_t first, size_t second)
{
return second * second - first * first >= d_minimum;
}
};
int main()
{
string sarr[] =
{
"Alpha", "bravo", "charley", "delta", "echo", "echo",
"foxtrot", "golf"
};
string *last = sarr + sizeof(sarr) / sizeof(string);
string *result = adjacent_find(sarr, last);
cout << *result << '\n';
result = adjacent_find(++result, last);
cout << "Second time, starting from the next position:\n" <<
(
result == last ?
"** No more adjacent equal elements **"
:
"*result"
) << '\n';
size_t iv[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
size_t *ilast = iv + sizeof(iv) / sizeof(size_t);
size_t *ires = adjacent_find(iv, ilast, SquaresDiff(10));
cout <<
"The first numbers for which the squares differ at least 10: "
<< *ires << " and " << *(ires + 1) << '\n';
}
/*
출력:
echo
Second time, starting from the next position:
** No more adjacent equal elements **
The first numbers for which the squares differ at least 10: 5 and 6
*/
<algorithm>
bool binary_search(ForwardIterator first, ForwardIterator last, Type const &value);
bool binary_search(ForwardIterator first, ForwardIterator last, Type const &value, Comparator comp);
[first, last)에 해당하는 일련의 원소에서 이진 검색으로 value를 찾는다. 범위 안에 있는 원소들은 Type::operator< 함수로 정렬되어 있어야 한다. 원소를 발견하면 true가 반환된다. 그렇지 않으면 false가 반환된다.
[first, last)에 해당하는 일련의 원소에서 이진 검색으로 value를 찾는다. 범위 안의 원소들은 Comparator 함수객체로 정렬되어 있어야 한다. 원소를 발견하면 true를 반환하고 그렇지 않으면 false를 돌려준다.
#include <algorithm>
#include <string>
#include <iostream>
#include <functional>
using namespace std;
int main()
{
string sarr[] =
{
"alpha", "bravo", "charley", "delta", "echo",
"foxtrot", "golf", "hotel"
};
string *last = sarr + sizeof(sarr) / sizeof(string);
bool result = binary_search(sarr, last, "foxtrot");
cout << (result ? "found " : "didn't find ") << "foxtrot" << '\n';
reverse(sarr, last); // reverse the order of elements
// binary search now fails:
result = binary_search(sarr, last, "foxtrot");
cout << (result ? "found " : "didn't find ") << "foxtrot" << '\n';
// ok when using appropriate
// comparator:
result = binary_search(sarr, last, "foxtrot", greater<string>());
cout << (result ? "found " : "didn't find ") << "foxtrot" << '\n';
}
/*
출력:
found foxtrot
didn't find foxtrot
found foxtrot
*/
<algorithm>
OutputIterator copy(InputIterator first, InputIterator last, OutputIterator destination);
[first, last)에 있는 원소들을 destination부터 출력 범위에 복사한다. 아래 데이터 유형의 할당 연산자를 사용한다. 반환 값은 OutputIterator이다. 목표 범위에 복사된 마지막 원소 바로 다음을 가리킨다 (그래서 목표 범위의 `last'가 반환된다).
copy를 호출한 것에 주목하라. string 객체에 ostream_iterator를 사용한다. 이 반복자는 string 값을 지정된 ostream (즉, cout)에 지정된 가름 문자열로 분리해 쓴다 (즉, " ").
#include <algorithm>
#include <string>
#include <iostream>
#include <iterator>
using namespace std;
int main()
{
string sarr[] =
{
"alpha", "bravo", "charley", "delta", "echo",
"foxtrot", "golf", "hotel"
};
string *last = sarr + sizeof(sarr) / sizeof(string);
copy(sarr + 2, last, sarr); // 모든 원소를 왼쪽으로 두 위치만큼 이동
// 문자열용 ostream_iterator를 사용하여
// cout에 복사,
copy(sarr, last, ostream_iterator<string>(cout, " "));
cout << '\n';
}
// 출력: charley delta echo foxtrot golf hotel golf hotel
unique_copy
<algorithm>
BidirectionalIterator copy_backward(InputIterator first, InputIterator last, BidirectionalIterator last2);
last - 1 위치에 있는 원소부터 first 위치에 있는 원소까지 [first, last) 반복자 범위의 원소를 last2 - 1 위치에서 끝나는 범위에 복사한다. 아래 데이터 유형의 할당 연산자를 사용한다. 그러므로 목표 범위는 [last2 - (last - first), last2)이다.
이 알고리즘은 원소들을 목표 범위에 복사할 때 순서를 뒤집지 않는다는 것을 눈여겨보라.
반환 값은 BidirectionalIterator 반복자이다. 목표 범위에 복사된 마지막 원소를 가리킨다 (그래서 목표 범위에서 last2 - (last - first)이 가리키는 `첫 번째 원소의' 위치가 반환된다).
#include <algorithm>
#include <string>
#include <iostream>
#include <iterator>
using namespace std;
int main()
{
string sarr[] =
{
"alpha", "bravo", "charley", "delta", "echo",
"foxtrot", "golf", "hotel"
};
string *last = sarr + sizeof(sarr) / sizeof(string);
copy
(
copy_backward(sarr + 3, last, last - 3),
last,
ostream_iterator<string>(cout, " ")
);
cout << '\n';
}
// 다음을 보여준다. golf hotel foxtrot golf hotel foxtrot golf hotel
<algorithm>
size_t count(InputIterator first, InputIterator last, Type const &value);
value 값이 반복자 범위 [first, last)에 나타나는 횟수를 돌려준다. value 값이 반복자 범위의 한 원소에 동일한지 알아 보려면 Type::operator==를 사용한다.
#include <algorithm>
#include <iostream>
using namespace std;
int main()
{
int ia[] = {1, 2, 3, 4, 3, 4, 2, 1, 3};
cout << "Number of times the value 3 is available: " <<
count(ia, ia + sizeof(ia) / sizeof(int), 3) <<
'\n';
}
// 다음을 보여준다. Number of times the value 3 is available: 3
<algorithm>
size_t count_if(InputIterator first, InputIterator last, Predicate predicate);
#include <algorithm>
#include <iostream>
using namespace std;
class Odd
{
public:
bool operator()(int value) const
{
return value & 1;
}
};
int main()
{
int ia[] = {1, 2, 3, 4, 3, 4, 2, 1, 3};
cout << "The number of odd values in the array is: " <<
count_if(ia, ia + sizeof(ia) / sizeof(int), Odd()) << '\n';
}
// 출력: The number of odd values in the array is: 5
<algorithm>
bool equal(InputIterator first, InputIterator last, InputIterator otherFirst);
bool equal(InputIterator first, InputIterator last, InputIterator otherFirst, BinaryPredicate pred);
[first, last) 범위의 원소를 otherFirst에서 시작하여 같은 길이만큼 비교한다. 두 범위에 방문한 원소들이 쌍별로 같다면 true를 돌려준다. 두 범위의 길이는 같지 않아도 된다. 지정된 범위 안에 있는 원소들만 고려한다 (반드시 있어야 한다).
[first, last) 범위의 원소를 otherFirst에서 시작하여 같은 길이만큼 비교한다. 두 범위에서 상응하는 원소들에 진위함수를 적용하여 매 쌍마다 모두 true를 돌려주면 true를 돌려준다. 범위는 길이가 같을 필요는 없다. 지정한 범위 안의 원소들만 고려한다 (반드시 있어야 한다).
#include <algorithm>
#include <string>
#include <cstring>
#include <iostream>
using namespace std;
class CaseString
{
public:
bool operator()(string const &first,
string const &second) const
{
return !strcasecmp(first.c_str(), second.c_str());
}
};
int main()
{
string first[] =
{
"Alpha", "bravo", "Charley", "delta", "Echo",
"foxtrot", "Golf", "hotel"
};
string second[] =
{
"alpha", "bravo", "charley", "delta", "echo",
"foxtrot", "golf", "hotel"
};
string *last = first + sizeof(first) / sizeof(string);
cout << "The elements of `first' and `second' are pairwise " <<
(equal(first, last, second) ? "equal" : "not equal") <<
'\n' <<
"compared case-insensitively, they are " <<
(
equal(first, last, second, CaseString()) ?
"equal" : "not equal"
) << '\n';
}
/*
출력:
The elements of `first' and `second' are pairwise not equal
compared case-insensitively, they are equal
*/
<algorithm>
pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last, Type const &value);
pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last, Type const &value, Compare comp);
map (12.4.7항) 그리고 multimap (12.4.8항)에서 이름이 동일한 함수를 참고하라):
operator< 연산자를 사용하여 정렬되어 있다). 반환 값은 각각 lower_bound와upper_bound를 가리킨다 (lower_bound는 제공된 참조 값보다 작지 않은 첫 원소를 돌려주고 (19.1.25항), upper_bound는 제공된 참조 값보다 더 큰 첫 원소를 돌려준다 (19.1.66항)).
comp 함수객체가 사용되었다). 반환 값은 각각 lower_bound (19.1.25항) 그리고 upper_bound (19.1.66항)이다.
#include <algorithm>
#include <functional>
#include <iterator>
#include <iostream>
using namespace std;
int main()
{
int range[] = {1, 3, 5, 7, 7, 9, 9, 9};
size_t const size = sizeof(range) / sizeof(int);
pair<int *, int *> pi;
pi = equal_range(range, range + size, 6);
cout << "Lower bound for 6: " << *pi.first << '\n';
cout << "Upper bound for 6: " << *pi.second << '\n';
pi = equal_range(range, range + size, 7);
cout << "Lower bound for 7: ";
copy(pi.first, range + size, ostream_iterator<int>(cout, " "));
cout << '\n';
cout << "Upper bound for 7: ";
copy(pi.second, range + size, ostream_iterator<int>(cout, " "));
cout << '\n';
sort(range, range + size, greater<int>());
cout << "Sorted in descending order\n";
copy(range, range + size, ostream_iterator<int>(cout, " "));
cout << '\n';
pi = equal_range(range, range + size, 7, greater<int>());
cout << "Lower bound for 7: ";
copy(pi.first, range + size, ostream_iterator<int>(cout, " "));
cout << '\n';
cout << "Upper bound for 7: ";
copy(pi.second, range + size, ostream_iterator<int>(cout, " "));
cout << '\n';
}
/*
출력:
Lower bound for 6: 7
Upper bound for 6: 7
Lower bound for 7: 7 7 9 9 9
Upper bound for 7: 9 9 9
Sorted in descending order
9 9 9 7 7 5 3 1
Lower bound for 7: 7 7 5 3 1
Upper bound for 7: 5 3 1
*/
<utility>
Type exchange(Type &object1, ValueType &&newValue);
newValue가 object1에 할당되고, object1의 이전 값이 반환된다.
#include <utility>
#include <iostream>
using namespace std;
int main(int argc, char **argv)
{
bool more = argc > 5;
cout << "more than 5: " << exchange(more, argc > 2) <<
", more than 2: " << more << '\n';
}
/*
g++ 7.0.0 버전 이상을 사용:
`a.out one two three'를 적용하면 출력됨:
more than 5: 0, more than 2: 1
*/
<algorithm>
void fill(ForwardIterator first, ForwardIterator last, Type const &value);
[first, last) 범위의 모든 원소들을 value로 초기화하고, 이전에 저장된 값들을 덮어쓴다.
#include <algorithm>
#include <vector>
#include <iterator>
#include <iostream>
using namespace std;
int main()
{
vector<int> iv(8);
fill(iv.begin(), iv.end(), 8);
copy(iv.begin(), iv.end(), ostream_iterator<int>(cout, " "));
cout << '\n';
}
// 출력: 8 8 8 8 8 8 8 8
<algorithm>
void fill_n(ForwardIterator first, Size n, Type const &value);
first로 지정된 원소부터 시작하여 n개의 원소를 value로 초기화한다. 이전에 저장된 값들을 덮어쓴다.
#include <algorithm>
#include <vector>
#include <iterator>
#include <iostream>
using namespace std;
int main()
{
vector<int> iv(8);
fill_n(iv.begin() + 2, 4, 8);
copy(iv.begin(), iv.end(), ostream_iterator<int>(cout, " "));
cout << '\n';
}
// 출력: 0 0 8 8 8 8 0 0
<algorithm>
InputIterator find(InputIterator first, InputIterator last, Type const &value);
[first, last) 범위의 원소에 대하여 value 원소를 검색한다. 발견된 첫 원소를 가리키는 반복자를 돌려준다. 발견하지 못하면 last가 반환된다. 아래 데이터 유형의 operator== 연산자를 사용하여 원소를 비교한다.
#include <algorithm>
#include <string>
#include <iterator>
#include <iostream>
using namespace std;
int main()
{
string sarr[] =
{
"alpha", "bravo", "charley", "delta", "echo"
};
string *last = sarr + sizeof(sarr) / sizeof(string);
copy
(
find(sarr, last, "delta"), last,
ostream_iterator<string>(cout, " ")
);
cout << '\n';
if (find(sarr, last, "india") == last)
{
cout << "`india' was not found in the range\n";
copy(sarr, last, ostream_iterator<string>(cout, " "));
cout << '\n';
}
}
/*
출력:
delta echo
`india' was not found in the range
alpha bravo charley delta echo
*/
<algorithm>
ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2)
ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred)
[first1, last1)로 의도한 원소들의 연속열을 검색해 마지막으로 나타난 [first2, last2) 범위로 의도한 원소들의 연속열을 찾는다. [first2, last2) 연속열을 발견하지 못하면 last1이 반환된다. 그렇지 않으면 일치한 연속열의 첫 원소를 가리키는 반복자를 돌려준다. 아래 데이터 유형의 operator== 연산자를 사용하여 두 연속열에 있는 원소들을 비교한다.
[first1, last1) 범위로 의도한 원소들의 연속열을 검색해 마지막으로 나타난 [first2, last2) 범위로 의도한 원소들의 연속열을 찾는다. 연속열 [first2, last2)를 발견하지 못하면, last1을 돌려준다. 그렇지 않으면 부합한 연속열의 첫 원소를 가리키는 반복자를 돌려준다. 제공된 진위함수를 사용하여 두 연속열에 있는 원소들을 비교한다.
#include <algorithm>
#include <string>
#include <iterator>
#include <iostream>
using namespace std;
class Twice
{
public:
bool operator()(size_t first, size_t second) const
{
return first == (second << 1);
}
};
int main()
{
string sarr[] =
{
"alpha", "bravo", "charley", "delta", "echo",
"foxtrot", "golf", "hotel",
"india", "juliet", "kilo"
};
string search[] =
{
"foxtrot",
"golf",
"hotel"
};
string *last = sarr + sizeof(sarr) / sizeof(string);
copy
(
find_end(sarr, last, search, search + 3), // 2번째 'foxtrot'에서
last, ostream_iterator<string>(cout, " ") // 시작하는 연속열
);
cout << '\n';
size_t range[] = {2, 4, 6, 8, 10, 4, 6, 8, 10};
size_t nrs[] = {2, 3, 4};
copy // range[]의 원소중에서
( // nrs[] 원소의 두 배가 되는 원소들로 구성된 연속열
find_end(range, range + 9, nrs, nrs + 3, Twice()),
range + 9, ostream_iterator<size_t>(cout, " ")
);
cout << '\n';
}
/*
출력:
foxtrot golf hotel india juliet kilo
4 6 8 10
*/
<algorithm>
ForwardIterator1 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2)
ForwardIterator1 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred)
[first1, last1) 범위로 의도한 원소들의 연속열을 검색하여 [first2, last2) 범위의 연속열 안에 있는 원소 중에서 처음으로 나타난 원소를 찾는다. [first2, last2) 연속열 안에서 어떤 원소도 발견하지 못하면 last1을 돌려준다. 그렇지 않으면 [first1, last1)안에서 [first2, last2) 안의 원소와 동일한 첫 원소를 가리키는 반복자를 돌려준다. 아래의 operator== 연산자를 사용하여 두 연속열에 있는 원소들을 비교한다.
[first1, last1) 범위로 의도한 원소들의 연속열을 검색하여 [first2, last2)로 의도한 원소들의 연속열 안에서 처음으로 나타난 원소를 찾는다. [first1, last1) 범위의 각 원소를 [first2, last2) 범위의 각 원소와 비교한다. [first1, last1) 범위에서 이항 pred 진위함수가 ([first1, last1) 범위의 원소와 [first2, last2) 범위의 원소 하나를 받아 비교하여) true를 돌려주는 첫 번째 원소를 가리키는 반복자가 반환된다. 그렇지 않으면 last1이 반환된다.
#include <algorithm>
#include <string>
#include <iterator>
#include <iostream>
using namespace std;
class Twice
{
public:
bool operator()(size_t first, size_t second) const
{
return first == (second << 1);
}
};
int main()
{
string sarr[] =
{
"alpha", "bravo", "charley", "delta", "echo",
"foxtrot", "golf", "hotel",
"foxtrot", "golf", "hotel",
"india", "juliet", "kilo"
};
string search[] =
{
"foxtrot",
"golf",
"hotel"
};
string *last = sarr + sizeof(sarr) / sizeof(string);
copy
( // 첫 번째 'foxtrot'에서
find_first_of(sarr, last, search, search + 3),// 시작하는 연속열
last, ostream_iterator<string>(cout, " ")
);
cout << '\n';
size_t range[] = {2, 4, 6, 8, 10, 4, 6, 8, 10};
size_t nrs[] = {2, 3, 4};
// 'range'의 원소중에서
// 'nrs' 원소의 두 배가 되는
// 원소들을 복사한다.
copy
(
find_first_of(range, range + 9, nrs, nrs + 3, Twice()),
range + 9, ostream_iterator<size_t>(cout, " ")
);
cout << '\n';
}
/*
출력:
foxtrot golf hotel foxtrot golf hotel india juliet kilo
4 6 8 10 4 6 8 10
*/
<algorithm>
InputIterator find_if(InputIterator first, InputIterator last, Predicate pred);
[first, last) 반복자 범위에서 (단항) pred 진위함수가 true를 돌려주는 첫 원소를 가리키는 반복자를 돌려준다. 원소를 발견하지 못하면 last가 반환된다.
#include <algorithm>
#include <string>
#include <cstring>
#include <iterator>
#include <iostream>
using namespace std;
class CaseName
{
std::string d_string;
public:
CaseName(char const *str): d_string(str)
{}
bool operator()(std::string const &element) const
{
return strcasecmp(element.c_str(), d_string.c_str()) == 0;
}
};
int main()
{
string sarr[] =
{
"Alpha", "Bravo", "Charley", "Delta", "Echo"
};
string *last = sarr + sizeof(sarr) / sizeof(string);
copy
(
find_if(sarr, last, CaseName("charley")),
last, ostream_iterator<string>(cout, " ")
);
cout << '\n';
if (find_if(sarr, last, CaseName("india")) == last)
{
cout << "`india' was not found in the range\n";
copy(sarr, last, ostream_iterator<string>(cout, " "));
cout << '\n';
}
}
/*
출력:
Charley Delta Echo
`india' was not found in the range
Alpha Bravo Charley Delta Echo
*/
<algorithm>
Function for_each(ForwardIterator first, ForwardIterator last, Function func);
[first, last) 반복자 범위의 각 원소를 func 함수 (또는 함수객체)에 참조로 순서대로 건넨다. 이 함수는 받은 원소를 변경할 수도 있다 (사용된 반복자가 정방향 반복자이기 때문이다). 또, 원소를 변형해야 한다면 transform을 사용할 수 있다 (19.1.63항). 함수 자체 또는 제공된 함수객체의 사본이 반환된다. 아래의 예제를 참고하라. 인자 리스트를 for_each 호출에 추가했고 인자는 결국 for_each에 주어진 함수에도 건네어진다. for_each 안에서 함수의 반환 값은 무시된다. for_each 총칭 알고리즘은 범위-기반의 for 회돌이를 많이 닮았다. 그러나 다르다. for_each 알고리즘은 부-범위와 역방향-반복자에도 사용할 수 있다.
#include <algorithm>
#include <string>
#include <cstring>
#include <iostream>
#include <cctype>
using namespace std;
void lowerCase(char &c) // `c' *변경 가능*
{
c = tolower(static_cast<unsigned char>(c));
}
void capitalizedOutput(string const &str) // `str' *변경 불가*
{
char *tmp = strcpy(new char[str.size() + 1], str.c_str());
for_each(tmp + 1, tmp + str.size(), lowerCase);
tmp[0] = toupper(*tmp);
cout << tmp << " ";
delete tmp;
};
int main()
{
string sarr[] =
{
"alpha", "BRAVO", "charley", "DELTA", "echo",
"FOXTROT", "golf", "HOTEL"
};
string *last = sarr + sizeof(sarr) / sizeof(string);
for_each(sarr, last, capitalizedOutput)("that's all, folks");
cout << '\n';
}
/*
출력:
Alpha Bravo Charley Delta Echo Foxtrot Golf Hotel That's all, folks
*/
#include <algorithm>
#include <string>
#include <iostream>
#include <cctype>
using namespace std;
void lowerCase(char &c)
{
c = tolower(static_cast<unsigned char>(c));
}
class Show
{
int d_count;
public:
Show()
:
d_count(0)
{}
void operator()(std::string &str)
{
std::for_each(str.begin(), str.end(), lowerCase);
str[0] = toupper(str[0]); // assuming str is not empty
std::cout << ++d_count << " " << str << "; ";
}
int count() const
{
return d_count;
}
};
int main()
{
string sarr[] =
{
"alpha", "BRAVO", "charley", "DELTA", "echo",
"FOXTROT", "golf", "HOTEL"
};
string *last = sarr + sizeof(sarr) / sizeof(string);
cout << for_each(sarr, last, Show()).count() << '\n';
}
/*
(한 줄에 모두) 출력:
1 Alpha; 2 Bravo; 3 Charley; 4 Delta; 5 Echo; 6 Foxtrot;
7 Golf; 8 Hotel; 8
*/
for_each 알고리즘을 const와 비-const 매개변수를 정의한 함수와 사용할 수도 있다는 것을 보여준다. 또, for_each와 transform 총칭 알고리즘 사이의 차이점은 19.1.63항을 보라.
for_each 알고리즘은 자신의 객체를 변경하기 위하여 멤버 함수 안에 직접적으로 (즉, *this를 함수객체의 인자로 건네서) 사용할 수 없다. for_each 알고리즘은 먼저 건네어진 함수객체의 사본을 만들기 때문이다. 람다 함수 또는 포장 클래스(wrapper class)가 이 문제를 해결해 준다. 생성자가 현재 객체와 그의 멤버 함수중 하나를 가리키는 포인터나 참조를 받으면 된다.
<algorithm>
void generate(ForwardIterator first,
ForwardIterator last, Generator generator);
[first, last) 범위의 반복자로 의도한 모든 원소들을 generator의 반환 값으로 초기화한다. 반환 값은 함수 또는 함수객체일 수 있다. Generator::operator()는 어떤 인자도 받지 않는다. 예제는 대수학의 유명한 정리를 이용한다. n + 1의 평방근을 얻기 위하여 1 + 2 * n을 n * n에 더한다.
#include <algorithm>
#include <vector>
#include <iterator>
#include <iostream>
using namespace std;
class NaturalSquares
{
size_t d_newsqr;
size_t d_last;
public:
NaturalSquares(): d_newsqr(0), d_last(0)
{}
size_t operator()()
{ // using: (a + 1)^2 == a^2 + 2*a + 1
return d_newsqr += (d_last++ << 1) + 1;
}
};
int main()
{
vector<size_t> uv(10);
generate(uv.begin(), uv.end(), NaturalSquares());
copy(uv.begin(), uv.end(), ostream_iterator<int>(cout, " "));
cout << '\n';
}
// 출력: 1 4 9 16 25 36 49 64 81 100
<algorithm>
void generate_n(ForwardIterator first, Size n,
Generator generator);
first 반복자가 가리키는 첫 원소로부터 시작하여 n개의 원소가 generator의 반환 값으로 초기화된다. 이 반환 값은 함수 또는 함수객체일 수 있다.
#include <algorithm>
#include <vector>
#include <iterator>
#include <iostream>
using namespace std;
class NaturalSquares
{
size_t d_newsqr;
size_t d_last;
public:
NaturalSquares(): d_newsqr(0), d_last(0)
{}
size_t operator()()
{ // using: (a + 1)^2 == a^2 + 2*a + 1
return d_newsqr += (d_last++ << 1) + 1;
}
};
int main()
{
vector<size_t> uv(10);
generate_n(uv.begin(), 5, NaturalSquares());
copy(uv.begin(), uv.end(), ostream_iterator<int>(cout, " "));
cout << '\n';
}
// 출력: 1 4 9 16 25 0 0 0 0 0
<algorithm>
bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp);
[first1, last1) 범위와 [first2, last2) 범위의 두 연속열 모두 반복자가 가리키는 데이터 유형의 operator<를 사용하여 원소들이 정렬되어 있어야 한다. [first2, last2) 범위의 두 번째 연속열에 있는 원소들이 [first1, last1) 범위의 첫 번째 연속열에 포함되면 true를 돌려준다 (두 번째 범위는 첫 번째 범위의 부분집합이다).
[first1, last1) 범위와 [first2, last2) 범위의 모든 원소들은 comp 함수객체를 사용하여 정렬되어 있어야 한다. [first2, last2) 범위의 두 번째 연속열에 있는 원소들이 [first1, last1) 범위의 첫 번째 원소에 모두 포함되어 있다면 true를 돌려준다 (두 번째 범위는 첫 번째 범위의 부분집합이다).
#include <algorithm>
#include <string>
#include <cstring>
#include <iostream>
using namespace std;
class CaseString
{
public:
bool operator()(string const &first,
string const &second) const
{
return !strcasecmp(first.c_str(), second.c_str());
}
};
int main()
{
string first1[] =
{
"alpha", "bravo", "charley", "delta", "echo",
"foxtrot", "golf", "hotel"
};
string first2[] =
{
"Alpha", "bravo", "Charley", "delta", "Echo",
"foxtrot", "Golf", "hotel"
};
string second[] =
{
"charley", "foxtrot", "hotel"
};
size_t n = sizeof(first1) / sizeof(string);
cout << "The elements of `second' are " <<
(includes(first1, first1 + n, second, second + 3) ? "" : "not")
<< " contained in the first sequence:\n"
"second is a subset of first1\n";
cout << "The elements of `first1' are " <<
(includes(second, second + 3, first1, first1 + n) ? "" : "not")
<< " contained in the second sequence\n";
cout << "The elements of `second' are " <<
(includes(first2, first2 + n, second, second + 3) ? "" : "not")
<< " contained in the first2 sequence\n";
cout << "Using case-insensitive comparison,\n"
"the elements of `second' are "
<<
(includes(first2, first2 + n, second, second + 3, CaseString()) ?
"" : "not")
<< " contained in the first2 sequence\n";
}
/*
출력:
The elements of `second' are contained in the first sequence:
second is a subset of first1
The elements of `first1' are not contained in the second sequence
The elements of `second' are not contained in the first2 sequence
Using case-insensitive comparison,
the elements of `second' are contained in the first2 sequence
*/
<numeric>
Type inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, Type init);
Type inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, Type init, BinaryOperator1 op1, BinaryOperator2 op2);
[first1, last1) 범위의 원소와 first2가 가리키는 원소에서 시작하여 같은 갯수만큼 하나씩 짝지어 곱한 합을 init에 더한다. 그리고 이 합을 돌려준다. 이 함수는 반복자가 가리키는 데이터 유형의 operator+와 operator*를 사용한다.
op1 연산자와 기본 곱셈 연산자 대신에 이항 op2 연산자를 [first1, last1) 범위에 있는 원소와 first2가 가리키는 원소에서 시작하여 같은 갯수만큼 하나씩 짝지어서 모두 적용한다. 이항 연산자 호출의 결과가 init에 더해지고 init의 최종 값이 반환된다.
#include <numeric>
#include <algorithm>
#include <iterator>
#include <iostream>
#include <string>
using namespace std;
class Cat
{
std::string d_sep;
public:
Cat(string const &sep)
:
d_sep(sep)
{}
string operator()
(string const &s1, string const &s2) const
{
return s1 + d_sep + s2;
}
};
int main()
{
size_t ia1[] = {1, 2, 3, 4, 5, 6, 7};
size_t ia2[] = {7, 6, 5, 4, 3, 2, 1};
size_t init = 0;
cout << "The sum of all squares in ";
copy(ia1, ia1 + 7, ostream_iterator<size_t>(cout, " "));
cout << "is " <<
inner_product(ia1, ia1 + 7, ia1, init) << '\n';
cout << "The sum of all cross-products in ";
copy(ia1, ia1 + 7, ostream_iterator<size_t>(cout, " "));
cout << "and ";
copy(ia2, ia2 + 7, ostream_iterator<size_t>(cout, " "));
cout << "is " <<
inner_product(ia1, ia1 + 7, ia2, init) << '\n';
string names1[] = {"Frank", "Karel", "Piet"};
string names2[] = {"Brokken", "Kubat", "Plomp"};
cout << "A list of all combined names in ";
copy(names1, names1 + 3, ostream_iterator<string>(cout, " "));
cout << "and\n";
copy(names2, names2 + 3, ostream_iterator<string>(cout, " "));
cout << "is:" <<
inner_product(names1, names1 + 3, names2, string("\t"),
Cat("\n\t"), Cat(" ")) <<
'\n';
}
/*
출력:
The sum of all squares in 1 2 3 4 5 6 7 is 140
The sum of all cross-products in 1 2 3 4 5 6 7 and 7 6 5 4 3 2 1 is 84
A list of all combined names in Frank Karel Piet and
Brokken Kubat Plomp is:
Frank Brokken
Karel Kubat
Piet Plomp
*/
<algorithm>
void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last);
void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last,
Compare comp);
[first, middle)와 [middle, last)를 합병한다. 정렬된 리스트는 그대로 유지한다 (반복자가 가리키는 데이터 유형의 operator< 연산자를 사용한다). 최종 결과는 [first, last) 범위에 저장된다.
[first, middle)와 [middle, last)를 합병한다. 정렬된 리스트는 그대로 유지한다 (이항 comp 비교 연산자의 결과를 사용한다). 최종 결과는 [first, last) 범위에 저장된다.
#include <algorithm>
#include <string>
#include <cstring>
#include <iterator>
#include <iostream>
using namespace std;
class CaseString
{
public:
bool operator()(string const &first, string const &second) const
{
return strcasecmp(first.c_str(), second.c_str()) < 0;
}
};
int main()
{
string range[] =
{
"alpha", "charley", "echo", "golf",
"bravo", "delta", "foxtrot",
};
inplace_merge(range, range + 4, range + 7);
copy(range, range + 7, ostream_iterator<string>(cout, " "));
cout << '\n';
string range2[] =
{
"ALFHA", "CHARLEY", "DELTA", "foxtrot", "hotel",
"bravo", "ECHO", "GOLF"
};
inplace_merge(range2, range2 + 5, range2 + 8, CaseString());
copy(range2, range2 + 8, ostream_iterator<string>(cout, " "));
cout << '\n';
}
/*
출력:
alpha bravo charley delta echo foxtrot golf
ALHFA bravo CHARLEY DELTA ECHO foxtrot GOLF hotel
*/
<algorithm>
void iter_swap(ForwardIterator1 iter1, ForwardIterator2 iter2);
iter1과 iter2가 가리키는 원소를 서로 바꾼다.
#include <algorithm>
#include <iterator>
#include <iostream>
#include <string>
using namespace std;
int main()
{
string first[] = {"alpha", "bravo", "charley"};
string second[] = {"echo", "foxtrot", "golf"};
size_t const n = sizeof(first) / sizeof(string);
cout << "Before:\n";
copy(first, first + n, ostream_iterator<string>(cout, " "));
cout << '\n';
copy(second, second + n, ostream_iterator<string>(cout, " "));
cout << '\n';
for (size_t idx = 0; idx < n; ++idx)
iter_swap(first + idx, second + idx);
cout << "After:\n";
copy(first, first + n, ostream_iterator<string>(cout, " "));
cout << '\n';
copy(second, second + n, ostream_iterator<string>(cout, " "));
cout << '\n';
}
/*
출력:
Before:
alpha bravo charley
echo foxtrot golf
After:
echo foxtrot golf
alpha bravo charley
*/
<algorithm>
bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp);
[first1, last1) 범위와 [first2, last2) 범위를 비교한다. 이 함수는 다음과 같은 경우에 true를 돌려준다.
operator< 연산자를 사용한다),
last1에 도달했지만 아직 last2에는 도달하지 못했을 때.
false가 반환된다.
operator< 연산자를 사용한다. 피 연산자의 순서를 뒤집는다).
last2에 도달했지만 last1은 아직 도달하지 못 했을 때.
last1과 last2에 모두 도달했을 때.
operator< 연산자 대신에 comp로 정의된 이항 비교 연산자를 사용한다.
#include <algorithm>
#include <iterator>
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
class CaseString
{
public:
bool operator()(string const &first,
string const &second) const
{
return strcasecmp(first.c_str(), second.c_str()) < 0;
}
};
int main()
{
string word1 = "hello";
string word2 = "help";
cout << word1 << " is " <<
(
lexicographical_compare(word1.begin(), word1.end(),
word2.begin(), word2.end()) ?
"before "
:
"beyond or at "
) <<
word2 << " in the alphabet\n";
cout << word1 << " is " <<
(
lexicographical_compare(word1.begin(), word1.end(),
word1.begin(), word1.end()) ?
"before "
:
"beyond or at "
) <<
word1 << " in the alphabet\n";
cout << word2 << " is " <<
(
lexicographical_compare(word2.begin(), word2.end(),
word1.begin(), word1.end()) ?
"before "
:
"beyond or at "
) <<
word1 << " in the alphabet\n";
string one[] = {"alpha", "bravo", "charley"};
string two[] = {"ALPHA", "BRAVO", "DELTA"};
copy(one, one + 3, ostream_iterator<string>(cout, " "));
cout << " is ordered " <<
(
lexicographical_compare(one, one + 3,
two, two + 3, CaseString()) ?
"before "
:
"beyond or at "
);
copy(two, two + 3, ostream_iterator<string>(cout, " "));
cout << "\n"
"using case-insensitive comparisons.\n";
}
/*
출력:
hello is before help in the alphabet
hello is beyond or at hello in the alphabet
help is beyond or at hello in the alphabet
alpha bravo charley is ordered before ALPHA BRAVO DELTA
using case-insensitive comparisons.
*/
<algorithm>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const Type &value);
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const Type &value, Compare comp);
[first, last) 반복자 범위의 원소 중에서 value보다 작지 않은 (즉, 이상의) 첫 원소를 찾는다. 반환된 반복자는 연속열에서 정렬 순서를 깨지 않고 value를 삽입할 수 있는 위치를 가리킨다. 반복자가 가리키는 데이터 유형의 operator< 연산자를 사용한다. 만약 그런 원소를 찾지 못하면 last가 반환된다.
[first, last) 반복자 범위의 원소는 comp 진위 함수를 사용하여 정렬되어 있어야 한다 (-object). comp 진위함수가 범위 안의 각 원소들을 value와 비교하여 false를 돌려주는 첫 원소를 가리키는 반복자를 돌려준다. 그런 원소를 발견하지 못하면 last를 돌려준다.
#include <algorithm>
#include <iostream>
#include <iterator>
#include <functional>
using namespace std;
int main()
{
int ia[] = {10, 20, 30};
cout << "Sequence: ";
copy(ia, ia + 3, ostream_iterator<int>(cout, " "));
cout << '\n';
cout << "15 can be inserted before " <<
*lower_bound(ia, ia + 3, 15) << '\n';
cout << "35 can be inserted after " <<
(lower_bound(ia, ia + 3, 35) == ia + 3 ?
"the last element" : "???") << '\n';
iter_swap(ia, ia + 2);
cout << "Sequence: ";
copy(ia, ia + 3, ostream_iterator<int>(cout, " "));
cout << '\n';
cout << "15 can be inserted before " <<
*lower_bound(ia, ia + 3, 15, greater<int>()) << '\n';
cout << "35 can be inserted before " <<
(lower_bound(ia, ia + 3, 35, greater<int>()) == ia ?
"the first element " : "???") << '\n';
}
/*
출력:
Sequence: 10 20 30
15 can be inserted before 20
35 can be inserted after the last element
Sequence: 30 20 10
15 can be inserted before 10
35 can be inserted before the first element
*/
<algorithm>
Type const &max(Type const &one, Type const &two);
Type const &max(Type const &one, Type const &two, Comparator comp);
one과 two중 더 큰 원소를 돌려준다. 반복자가 가리키는 데이터 유형의 operator> 연산자를 사용한다.
comp(one, two) 진위함수가 true를 반환하면 one을 돌려준다. 그렇지 않으면 two를 돌려준다.
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
class CaseString
{
public:
bool operator()(string const &first, string const &second) const
{
return strcasecmp(second.c_str(), first.c_str()) > 0;
}
};
int main()
{
cout << "Word '" << max(string("first"), string("second")) <<
"' is lexicographically last\n";
cout << "Word '" << max(string("first"), string("SECOND")) <<
"' is lexicographically last\n";
cout << "Word '" << max(string("first"), string("SECOND"),
CaseString()) << "' is lexicographically last\n";
}
/*
출력:
Word 'second' is lexicographically last
Word 'first' is lexicographically last
Word 'SECOND' is lexicographically last
*/
<algorithm>
ForwardIterator max_element(ForwardIterator first, ForwardIterator last);
ForwardIterator max_element(ForwardIterator first, ForwardIterator last, Comparator comp);
#include <algorithm>
#include <iostream>
using namespace std;
class AbsValue
{
public:
bool operator()(int first, int second) const
{
return abs(first) < abs(second);
}
};
int main()
{
int ia[] = {-4, 7, -2, 10, -12};
cout << "The max. int value is " << *max_element(ia, ia + 5) << '\n';
cout << "The max. absolute int value is " <<
*max_element(ia, ia + 5, AbsValue()) << '\n';
}
/*
출력:
The max. int value is 10
The max. absolute int value is -12
*/
<algorithm>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
[first1, last1) 범위와 [first2, last2) 범위 두 개를 합병한다. 정렬된 리스트는 그대로 유지한다 (반복자가 가리키는 데이터 유형의 operator< 연산자를 사용한다). 그 결과는 result에서 시작하고 이 함수가 돌려준 OutputIterator 바로 앞에서 끝나는 범위에 저장된다.
[first1, last1) 범위와 [first2, last2) 범위를 합병한다. 정렬된 리스트는 그대로 유지한다 (이항 comp 비교 연산자의 결과를 이용한다). 결과는 result에서 시작하여 이 함수가 돌려주는 OutputIterator 바로 앞에서 끝나는 범위에 저장된다.
#include <algorithm>
#include <string>
#include <cstring>
#include <iterator>
#include <iostream>
using namespace std;
class CaseString
{
public:
bool operator()(string const &first, string const &second) const
{
return strcasecmp(first.c_str(), second.c_str()) < 0;
}
};
int main()
{
string range1[] =
{ // 원소 5개
"alpha", "bravo", "foxtrot", "hotel", "zulu"
};
string range2[] =
{ // 원소 4개
"delta", "echo", "golf", "romeo"
};
string result[5 + 4];
copy(result,
merge(range1, range1 + 5, range2, range2 + 4, result),
ostream_iterator<string>(cout, " "));
cout << '\n';
string range3[] =
{
"ALPHA", "bravo", "foxtrot", "HOTEL", "ZULU"
};
string range4[] =
{
"delta", "ECHO", "GOLF", "romeo"
};
copy(result,
merge(range3, range3 + 5, range4, range4 + 4, result,
CaseString()),
ostream_iterator<string>(cout, " "));
cout << '\n';
}
/*
출력:
alpha bravo delta echo foxtrot golf hotel romeo zulu
ALPHA bravo delta ECHO foxtrot GOLF HOTEL romeo ZULU
*/
<algorithm>
Type const &min(Type const &one, Type const &two);
Type const &min(Type const &one, Type const &two, Comparator comp);
one과 two 중에 더 작은 원소를 돌려준다. 반복자가 가리키는 데이터 유형의 operator< 연산자를 사용한다.
comp(one, two) 진위 함수가 false를 반환하면 one을 돌려준다. 그렇지 않으면 two를 돌려준다.
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
class CaseString
{
public:
bool operator()(string const &first, string const &second) const
{
return strcasecmp(second.c_str(), first.c_str()) > 0;
}
};
int main()
{
cout << "Word '" << min(string("first"), string("second")) <<
"' is lexicographically first\n";
cout << "Word '" << min(string("first"), string("SECOND")) <<
"' is lexicographically first\n";
cout << "Word '" << min(string("first"), string("SECOND"),
CaseString()) << "' is lexicographically first\n";
}
/*
출력:
Word 'first' is lexicographically first
Word 'SECOND' is lexicographically first
Word 'first' is lexicographically first
*/
<algorithm>
ForwardIterator min_element(ForwardIterator first, ForwardIterator last);
ForwardIterator min_element(ForwardIterator first, ForwardIterator last, Comparator comp);
[first, last) 범위에서 가장 작은 원소를 가리키는 반복자를 돌려준다. 반복자가 가리키는 데이터 유형의 operator<를 사용한다.
operator<를 사용하지 않고, 이항 comp 진위함수를 사용하여 [first, last) 범위의 원소를 비교한다.
comp가 false를 가장 많이 돌려준 원소가 반환된다.
#include <algorithm>
#include <iostream>
using namespace std;
class AbsValue
{
public:
bool operator()(int first, int second) const
{
return abs(first) < abs(second);
}
};
int main()
{
int ia[] = {-4, 7, -2, 10, -12};
cout << "The minimum int value is " << *min_element(ia, ia + 5) <<
'\n';
cout << "The minimum absolute int value is " <<
*min_element(ia, ia + 5, AbsValue()) << '\n';
}
/*
출력:
The minimum int value is -12
The minimum absolute int value is -2
*/
<algorithm>
pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, Compare comp);
first1와 first2에서 시작하는 원소들을 비교한다. 비교에 반복자가 가리키는 데이터 유형의 비교 연산자를 사용한다. 비교된 원소가 다르면 (즉, operator==가 false를 돌려주면) 또는 last1에 도달하면 비교가 멈춘다. 마지막 위치를 가리키는 반복자를 담은 pair가 반환된다. 두 번째 연속열은 첫 번째 연속열보다 원소가 더 많을 수 있다. 두 번째 원소가 첫 번째 원소보다 더 적을 경우 알고리즘의 행위는 정의되어 있지 않다.
first1와 first2에서 시작하는 두 연속열을 비교한다. operator== 대신에 comp로 정의된 이항 비교 연산을 사용한다. comp 함수가 false를 돌려주거나 last1에 도달하면 비교가 멈춘다. 마지막 위치를 가리키는 반복자를 담은 pair가 반환된다. 두 번째 연속열은 첫 번째 연속열보다 원소가 더 많을 수 있다. 두 번째 원소가 첫 번째 원소보다 더 적을 경우 알고리즘의 행위는 정의되어 있지 않다.
#include <algorithm>
#include <string>
#include <cstring>
#include <iostream>
#include <utility>
using namespace std;
class CaseString
{
public:
bool operator()(string const &first, string const &second) const
{
return strcasecmp(first.c_str(), second.c_str()) == 0;
}
};
int main()
{
string range1[] =
{
"alpha", "bravo", "foxtrot", "hotel", "zulu"
};
string range2[] =
{
"alpha", "bravo", "foxtrot", "Hotel", "zulu"
};
pair<string *, string *> pss = mismatch(range1, range1 + 5, range2);
cout << "The elements " << *pss.first << " and " << *pss.second <<
" at offset " << (pss.first - range1) << " differ\n";
if
(
mismatch(range1, range1 + 5, range2, CaseString()).first
==
range1 + 5
)
cout << "When compared case-insensitively they match\n";
}
/*
출력:
The elements hotel and Hotel at offset 3 differ
When compared case-insensitively they match
*/
<algorithm>
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last);
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, Comp comp);
[first, last) 범위의 원소가 주어지면 다음 순열을 결정한다. 예를 들어, 원소가 1, 2 그리고 3인 범위에 next_permutation을 호출하면, 이어서 next_permutation를 호출할 때마다 다음과 같이 순열의 순서가 바뀐다.
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
이 예제는 각 순열이 다음의 더 큰 값을 대표하도록 순서가 바뀌는 것을 보여준다 (132는 123보다 크고, 213은 132보다 크다, 등등.). 비교를 위해 반복자가 가리키는 데이터 유형의 operator< 연산자를 사용한다. 순서가 바뀌면 true 값이 반환된다. 순서가 바뀌지 않으면 false 값이 반환된다. 이 경우는 순열이 가장 큰 (마지막) 값을 나타낸다. 이 경우에 순열 자체도 operator<를 사용하여 정렬된다.
[first, last) 범위의 원소가 주어지면 다음 순열을 결정한다. 비교를 위해 이항 comp 진위함수를 사용한다. 순서가 바뀌면 true가 반환되고, 그렇지 않으면 false가 반환된다. 이 경우 결과 순열이 순서가 바뀔 수 있다. 비교를 위해 이항 comp 진위함수를 사용한다.
#include <algorithm>
#include <iterator>
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
class CaseString
{
public:
bool operator()(string const &first, string const &second) const
{
return strcasecmp(first.c_str(), second.c_str()) < 0;
}
};
int main()
{
string saints[] = {"Oh", "when", "the", "saints"};
cout << "All permutations of 'Oh when the saints':\n";
cout << "Sequences:\n";
do
{
copy(saints, saints + 4, ostream_iterator<string>(cout, " "));
cout << '\n';
}
while (next_permutation(saints, saints + 4, CaseString()));
cout << "After first sorting the sequence:\n";
sort(saints, saints + 4, CaseString());
cout << "Sequences:\n";
do
{
copy(saints, saints + 4, ostream_iterator<string>(cout, " "));
cout << '\n';
}
while (next_permutation(saints, saints + 4, CaseString()));
}
/*
(일부만) 출력:
All permutations of 'Oh when the saints':
Sequences:
Oh when the saints
saints Oh the when
saints Oh when the
saints the Oh when
...
After first sorting the sequence:
Sequences:
Oh saints the when
Oh saints when the
Oh the saints when
Oh the when saints
...
*/
<algorithm>
void nth_element(RandomAccessIterator first,
RandomAccessIterator nth, RandomAccessIterator last);
void nth_element(RandomAccessIterator first,
RandomAccessIterator nth, RandomAccessIterator last, Compare
comp);
[first, last) 범위의 모든 원소들이 nth가 가리키는 원소에 상대적으로 정렬된다. [left, nth) 범위의 모든 원소들은 nth가 가리키는 원소보다 작다. 그리고 [nth + 1, last) 범위의 원소는 nth가 가리키는 원소보다 크다. 두 부분집합 자체는 정렬되지 않는다. 반복자가 가리키는 데이터 유형의 operator<가 원소를 비교하는 데 사용한다.
[first, last) 범위의 모든 원소는 nth가 가리키는 원소에 상대적으로 정렬된다. [left, nth) 범위의 모든 원소는 nth가 가리키는 원소보다 작다. [nth + 1, last) 범위의 모든 원소는 nth가 가리키는 원소보다 크다. 두 부분 집합 자체는 정렬되지 않는다. 원소들을 비교하는 데 comp 함수객체가 사용된다.
#include <algorithm>
#include <iostream>
#include <iterator>
#include <functional>
using namespace std;
int main()
{
int ia[] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
nth_element(ia, ia + 3, ia + 10);
cout << "sorting with respect to " << ia[3] << '\n';
copy(ia, ia + 10, ostream_iterator<int>(cout, " "));
cout << '\n';
nth_element(ia, ia + 5, ia + 10, greater<int>());
cout << "sorting with respect to " << ia[5] << '\n';
copy(ia, ia + 10, ostream_iterator<int>(cout, " "));
cout << '\n';
}
/*
출력:
sorting with respect to 4
1 2 3 4 9 7 5 6 8 10
sorting with respect to 5
10 8 7 9 6 5 3 4 2 1
*/
<algorithm>
void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);
void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp);
#include <algorithm>
#include <iostream>
#include <functional>
#include <iterator>
using namespace std;
int main()
{
int ia[] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
partial_sort(ia, ia + 3, ia + 10);
cout << "find the 3 smallest elements:\n";
copy(ia, ia + 10, ostream_iterator<int>(cout, " "));
cout << '\n';
cout << "find the 5 biggest elements:\n";
partial_sort(ia, ia + 5, ia + 10, greater<int>());
copy(ia, ia + 10, ostream_iterator<int>(cout, " "));
cout << '\n';
}
/*
출력:
find the 3 smallest elements:
1 2 3 7 9 5 4 6 8 10
find the 5 biggest elements:
10 9 8 7 6 1 2 3 4 5
*/
<algorithm>
void partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator dest_first, RandomAccessIterator dest_last);
void partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator dest_first, RandomAccessIterator dest_last, Compare comp);
[first, last) 범위에서 (dest_last - dest_first) 개의 원소만큼만 오름차순으로 정렬하여 [dest_first, dest_last) 범위에 저장한다. 복사할 원소를 결정하기 위해 반복자가 가리키는 데이터 유형의 operator< 연산자를 사용한다.
[first, last) 범위에서 (dest_last - dest_first) 개의 원소를 오름차순으로 정렬하여 [dest_first, dest_last) 범위에 저장한다 (이항 comp 진위함수가 true를 돌려주는지 아닌지에 따라 결정됨). comp 진위함수가 true를 가장 많이 돌려주는 원소들을 [dest_first, dest_last) 범위에 복사한다.
#include <algorithm>
#include <iostream>
#include <functional>
#include <iterator>
using namespace std;
int main()
{
int ia[] = {1, 10, 3, 8, 5, 6, 7, 4, 9, 2};
int ia2[6];
partial_sort_copy(ia, ia + 10, ia2, ia2 + 6);
copy(ia, ia + 10, ostream_iterator<int>(cout, " "));
cout << '\n';
cout << "the 6 smallest elements: ";
copy(ia2, ia2 + 6, ostream_iterator<int>(cout, " "));
cout << '\n';
cout << "the 4 smallest elements to a larger range:\n";
partial_sort_copy(ia, ia + 4, ia2, ia2 + 6);
copy(ia2, ia2 + 6, ostream_iterator<int>(cout, " "));
cout << '\n';
cout << "the 4 biggest elements to a larger range:\n";
partial_sort_copy(ia, ia + 4, ia2, ia2 + 6, greater<int>());
copy(ia2, ia2 + 6, ostream_iterator<int>(cout, " "));
cout << '\n';
}
/*
출력:
1 10 3 8 5 6 7 4 9 2
the 6 smallest elements: 1 2 3 4 5 6
the 4 smallest elements to a larger range:
1 3 8 10 5 6
the 4 biggest elements to a larger range:
10 8 3 1 5 6
*/
<numeric>
OutputIterator partial_sum(InputIterator first, InputIterator last, OutputIterator result);
OutputIterator partial_sum(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation op);
[result, <returned OutputIterator>) 범위의 각 원소마다 [first, last) 범위에서 상응한 범위 만큼의 원소를 더한 값을 얻는다. 결과 범위에서 첫 원소는 first가 가리키는 원소와 동일하다.
[result, <returned OutputIterator>) 범위의 각 원소마다 op 이항 연산자를 결과 범위의 이전 원소와 [first, last) 범위의 상응하는 원소에 적용하여 값을 얻는다. 결과 범위에서 첫 원소는 first가 가리키는 원소와 동일하다.
#include <numeric>
#include <algorithm>
#include <iostream>
#include <functional>
#include <iterator>
using namespace std;
int main()
{
int ia[] = {1, 2, 3, 4, 5};
int ia2[5];
copy(ia2,
partial_sum(ia, ia + 5, ia2),
ostream_iterator<int>(cout, " "));
cout << '\n';
copy(ia2,
partial_sum(ia, ia + 5, ia2, multiplies<int>()),
ostream_iterator<int>(cout, " "));
cout << '\n';
}
/*
출력:
1 3 6 10 15
1 2 6 24 120
*/
<algorithm>
BidirectionalIterator partition(BidirectionalIterator first, BidirectionalIterator last, UnaryPredicate pred);
[first, last) 범위의 원소 중에서 단항 pred 진위함수가 true로 평가한 원소는 모두 false로 평가된 원소들보다 앞에 배치한다. 반환 값은 구획된 범위에서 pred가 true로 평가한 마지막 원소 다음을 가리킨다.
#include <algorithm>
#include <iostream>
#include <string>
#include <iterator>
using namespace std;
class LessThan
{
int d_x;
public:
LessThan(int x)
:
d_x(x)
{}
bool operator()(int value) const
{
return value <= d_x;
}
};
int main()
{
int ia[] = {1, 3, 5, 7, 9, 10, 2, 8, 6, 4};
int *split;
split = partition(ia, ia + 10, LessThan(ia[9]));
cout << "Last element <= 4 is ia[" << split - ia - 1 << "]\n";
copy(ia, ia + 10, ostream_iterator<int>(cout, " "));
cout << '\n';
}
/*
출력:
Last element <= 4 is ia[3]
1 3 4 2 9 10 7 8 6 5
*/
<algorithm>
bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last);
bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Comp comp);
[first, last) 범위의 원소가 주어지면 이전 순열을 결정한다. 범위 안의 원소는 먼저 오는 순서대로 더 작은 값을 나타내도록 순서가 바뀐다 (반대 순서와 관련된 예제는 next_permutation 참조 (19.1.32항)). 순서가 바뀌면 true 값을 돌려주고 그렇지 않으면 false 값을 돌려주다. 이 경우는 제공된 연속열이 이미 정렬되어 있는 경우이다. 반복자가 가리키는 데이터 유형의 operator< 연산자를 사용한다.
[first, last) 범위의 원소가 주어지면 이전 순열을 결정한다. 비교를 위해 이항 comp 진위함수를 사용한다. 범위 안의 원소들의 순서가 바뀐다. 순서가 바뀌면 true 값이 반환되고 그렇지 않으면 false 값이 반환된다. 이 경우는 이미 원래 연속열이 정렬되어 있는 경우이다. 비교를 위해 이항 comp 진위함수를 사용한다.
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <iterator>
using namespace std;
class CaseString
{
public:
bool operator()(string const &first, string const &second) const
{
return strcasecmp(first.c_str(), second.c_str()) < 0;
}
};
int main()
{
string saints[] = {"Oh", "when", "the", "saints"};
cout << "All previous permutations of 'Oh when the saints':\n";
cout << "Sequences:\n";
do
{
copy(saints, saints + 4, ostream_iterator<string>(cout, " "));
cout << '\n';
}
while (prev_permutation(saints, saints + 4, CaseString()));
cout << "After first sorting the sequence:\n";
sort(saints, saints + 4, CaseString());
cout << "Sequences:\n";
while (prev_permutation(saints, saints + 4, CaseString()))
{
copy(saints, saints + 4, ostream_iterator<string>(cout, " "));
cout << '\n';
}
cout << "No (more) previous permutations\n";
}
/*
출력:
All previous permutations of 'Oh when the saints':
Sequences:
Oh when the saints
Oh when saints the
Oh the when saints
Oh the saints when
Oh saints when the
Oh saints the when
After first sorting the sequence:
Sequences:
No (more) previous permutations
*/
<algorithm>
void random_shuffle(RandomAccessIterator first, RandomAccessIterator last);
void random_shuffle(RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator rand);
[first, last) 범위의 원소의 순서를 무작위로 바꾼다.
[first, last) 범위의 원소의 순서를 무작위로 바꾼다. rand 난수 발생기를 사용한다. [0, remaining) 범위의 정수(int)가 반환된다. remaining이 인자로 rand 함수객체의 operator()에 건네어진다. 대안으로, 난수 발생기는 int remaining 매개변수를 기대하고 [0, remaining) 범위의 무작위 정수(int) 값을 돌려주는 함수가 될 수 있다. 함수객체를 사용할 때 익명 객체가 될 수 없다는 사실에 주목하라. 예제의 함수는 다음에 제시된 절차를 사용한다. Press et al. (1992) Numerical Recipes in C: The Art of Scientific Computing (New York: Cambridge University Press, (2nd ed., p. 277)).
#include <algorithm>
#include <iostream>
#include <string>
#include <time.h>
#include <iterator>
using namespace std;
int randomValue(int remaining)
{
return rand() % remaining;
}
class RandomGenerator
{
public:
RandomGenerator()
{
srand(time(0));
}
int operator()(int remaining) const
{
return randomValue(remaining);
}
};
void show(string *begin, string *end)
{
copy(begin, end, ostream_iterator<string>(cout, " "));
cout << "\n\n";
}
int main()
{
string words[] =
{ "kilo", "lima", "mike", "november", "oscar", "papa"};
size_t const size = sizeof(words) / sizeof(string);
cout << "Using Default Shuffle:\n";
random_shuffle(words, words + size);
show(words, words + size);
cout << "Using RandomGenerator:\n";
RandomGenerator rg;
random_shuffle(words, words + size, rg);
show(words, words + size);
srand(time(0) << 1);
cout << "Using the randomValue() function:\n";
random_shuffle(words, words + size, randomValue);
show(words, words + size);
}
/*
(예를 들어) 출력:
Using Default Shuffle:
lima oscar mike november papa kilo
Using RandomGenerator:
kilo lima papa oscar mike november
Using the randomValue() function:
mike papa november kilo oscar lima
*/
<algorithm>
ForwardIterator remove(ForwardIterator first, ForwardIterator last, Type const &value);
[first, last)가 가리키는 범위의 원소의 순서가 재배치된다. value와 같지 않은 모든 값들이 범위의 시작 위치에 배치된다. 반환된 정방향 반복자는 순서 재배치 후에 제거가 가능한 첫 원소를 가리킨다. [returnvalue, last) 범위를 알고리즘의 잔재(leftover)라고 부른다. 잔재에 value와 다른 원소가 들어 있을 수 있음을 유의하자. 그러나 이런 원소들은 [first, returnvalue) 범위에도 역시 존재하기 때문에 제거해도 안전하다. 그렇게 중복된 이유는 알고리즘이 원소들을 새 위치로 이동했기 때문이 아니라 복사했기 때문이다. 이 함수는 제거할 원소를 결정하기 위하여 반복자가 가리키는 데이터 유형의 operator==를 사용한다.
#include <algorithm>
#include <iostream>
#include <string>
#include <iterator>
using namespace std;
int main()
{
string words[] =
{ "kilo", "alpha", "lima", "mike", "alpha", "november", "alpha",
"alpha", "alpha", "papa", "quebec" };
string *removed;
size_t const size = sizeof(words) / sizeof(string);
cout << "Removing all +NOTRANS(ä)lpha\"s:\n";
removed = remove(words, words + size, "alpha");
copy(words, removed, ostream_iterator<string>(cout, " "));
cout << '\n'
<< "Leftover elements are:\n";
copy(removed, words + size, ostream_iterator<string>(cout, " "));
cout << '\n';
}
/*
출력:
Removing all "alpha"s:
kilo lima mike november papa quebec
Leftover elements are:
alpha alpha alpha papa quebec
*/
<algorithm>
OutputIterator remove_copy(InputIterator first, InputIterator last, OutputIterator result, Type const &value);
[first, last)가 가리키는 범위에서 value에 일치하지 않는 원소들을 [result, returnvalue) 범위에 복사한다. 여기에서 returnvalue는 이 함수가 돌려주는 반환 값이다. [first, last) 범위는 변경되지 않는다. 이 함수는 복사할 원소를 결정하기 위하여 반복자가 가리키는 데이터 유형의 operator==를 사용한다.
#include <algorithm>
#include <iostream>
#include <string>
#include <functional>
#include <iterator>
using namespace std;
int main()
{
string words[] =
{ "kilo", "alpha", "lima", "mike", "alpha", "november", "alpha",
"oscar", "alpha", "alpha", "papa", "quebec" };
size_t const size = sizeof(words) / sizeof(string);
string remaining
[
size -
count_if
(
words, words + size,
bind2nd(equal_to<string>(), string("alpha"))
)
];
string *returnvalue =
remove_copy(words, words + size, remaining, "alpha");
cout << "Removing all +NOTRANS(ä)lpha\"s:\n";
copy(remaining, returnvalue, ostream_iterator<string>(cout, " "));
cout << '\n';
}
/*
출력:
Removing all "alpha"s:
kilo lima mike november oscar papa quebec
*/
<algorithm>
OutputIterator remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, UnaryPredicate pred);
[first, last)가 가리키는 범위에서 단항 pred 진위함수가 true를 돌려주는 원소들을 결과 사본으로부터 제거한다. 다른 모든 원소는 [result, returnvalue) 범위에 복사된다. 여기에서 returnvalue는 이 함수가 돌려주는 반환 값이다. [first, last) 범위는 변경되지 않는다.
#include <algorithm>
#include <iostream>
#include <string>
#include <functional>
#include <iterator>
using namespace std;
int main()
{
string words[] =
{ "kilo", "alpha", "lima", "mike", "alpha", "november", "alpha",
"oscar", "alpha", "alpha", "papa", "quebec" };
size_t const size = sizeof(words) / sizeof(string);
string remaining[
size -
count_if
(
words, words + size,
bind2nd(equal_to<string>(), "alpha")
)
];
string *returnvalue =
remove_copy_if
(
words, words + size, remaining,
bind2nd(equal_to<string>(), "alpha")
);
cout << "Removing all +NOTRANS(ä)lpha\"s:\n";
copy(remaining, returnvalue, ostream_iterator<string>(cout, " "));
cout << '\n';
}
/*
출력:
Removing all "alpha"s:
kilo lima mike november oscar papa quebec
*/
<algorithm>
ForwardIterator remove_if(ForwardIterator first, ForwardIterator last, UnaryPredicate pred);
[first, last)가 가리키는 범위의 원소의 순서를 재배치한다. 단항 pred 진위함수가 false로 평가한 모든 원소들을 범위의 앞에 배치한다. 반환된 정방향 반복자는 순서 재배치 후에 pred가 true를 돌려준 첫 원소를 가리킨다. [returnvalue, last) 범위는 알고리즘의 잔재라고 부른다. 잔재에 pred 진위 함수가 false를 돌려주는 원소들이 담겨 있을 수 있지만 이런 함수들은 [first, returnvalue) 범위에도 존재하기 때문에 제거해도 안전하다. 그렇게 중복되는 이유는 알고리즘이 원소들을 새 위치로 이동하기 때문이 아니라 복사하기 때문이다.
#include <functional>
#include <algorithm>
#include <iostream>
#include <string>
#include <iterator>
using namespace std;
int main()
{
string words[] =
{ "kilo", "alpha", "lima", "mike", "alpha", "november", "alpha",
"oscar", "alpha", "alpha", "papa", "quebec" };
size_t const size = sizeof(words) / sizeof(string);
cout << "Removing all +NOTRANS(ä)lpha\"s:\n";
string *removed = remove_if(words, words + size,
bind2nd(equal_to<string>(), string("alpha")));
copy(words, removed, ostream_iterator<string>(cout, " "));
cout << '\n'
<< "Trailing elements are:\n";
copy(removed, words + size, ostream_iterator<string>(cout, " "));
cout << '\n';
}
/*
출력:
Removing all "alpha"s:
kilo lima mike november oscar papa quebec
Trailing elements are:
oscar alpha alpha papa quebec
*/
<algorithm>
ForwardIterator replace(ForwardIterator first, ForwardIterator last, Type const &oldvalue, Type const &newvalue);
[first, last)가 가리키는 범위에서 oldvalue 같은 원소들을 newvalue의 사본으로 교체한다. 알고리즘은 반복자가 가리키는 데이터 유형의 operator==를 사용한다.
#include <algorithm>
#include <iostream>
#include <string>
#include <iterator>
using namespace std;
int main()
{
string words[] =
{ "kilo", "alpha", "lima", "mike", "alpha", "november", "alpha",
"oscar", "alpha", "alpha", "papa" };
size_t const size = sizeof(words) / sizeof(string);
replace(words, words + size, string("alpha"), string("ALPHA"));
copy(words, words + size, ostream_iterator<string>(cout, " "));
cout << '\n';
}
/*
출력
kilo ALPHA lima mike ALPHA november ALPHA oscar ALPHA ALPHA papa
*/
<algorithm>
OutputIterator replace_copy(InputIterator first, InputIterator last, OutputIterator result, Type const &oldvalue, Type const &newvalue);
[first, last)가리키는 범위에서 oldvalue와 같은 모든 원소들을 새로운 [result, returnvalue) 범위에서 newvalue의 사본으로 교체한다. 여기에서 returnvalue는 이 함수의 반환 값이다. 알고리즘은 반복자가 가리키는 데이터 유형의 operator==를 사용한다.
#include <algorithm>
#include <iostream>
#include <string>
#include <iterator>
using namespace std;
int main()
{
string words[] =
{ "kilo", "alpha", "lima", "mike", "alpha", "november", "alpha",
"oscar", "alpha", "alpha", "papa"};
size_t const size = sizeof(words) / sizeof(string);
string remaining[size];
copy
(
remaining,
replace_copy(words, words + size, remaining, string("alpha"),
string("ALPHA")),
ostream_iterator<string>(cout, " ")
);
cout << '\n';
}
/*
출력:
kilo ALPHA lima mike ALPHA november ALPHA oscar ALPHA ALPHA papa
*/
<algorithm>
OutputIterator replace_copy_if(ForwardIterator first, ForwardIterator last, OutputIterator result, UnaryPredicate pred, Type const &value);
[first, last)가 가리키는 범위의 원소를 [result, returnvalue) 범위에 복사한다. 여기에서 returnvalue는 이 함수가 돌려주는 값이다. 단항 pred 진위함수가 true를 돌려주는 원소를 value로 교체한다. [first, last) 범위는 변경되지 않는다.
#include <algorithm>
#include <iostream>
#include <string>
#include <functional>
#include <iterator>
using namespace std;
int main()
{
string words[] =
{ "kilo", "alpha", "lima", "mike", "alpha", "november",
"alpha", "oscar", "alpha", "alpha", "papa"};
size_t const size = sizeof(words) / sizeof(string);
string result[size];
// Note: the comparisons are: "mike" > word[i]
replace_copy_if(words, words + size, result,
bind1st(greater<string>(), string("mike")),
string("ALPHA"));
copy (result, result + size, ostream_iterator<string>(cout, " "));
cout << '\n';
}
/*
출력 (words[]에서 'mike'보다 작은 단어들은 ALPHA로 교체됨):
ALPHA ALPHA ALPHA mike ALPHA november ALPHA oscar ALPHA ALPHA papa
*/
<algorithm>
ForwardIterator replace_if(ForwardIterator first, ForwardIterator last, UnaryPredicate pred, Type const &value);
[first, last)가 가리키는 범위에서 단항 pred 진위함수가 true로 평가하는 원소들을 value로 교체한다.
#include <algorithm>
#include <iostream>
#include <string>
#include <functional>
#include <iterator>
using namespace std;
int main()
{
string words[] =
{ "kilo", "alpha", "lima", "mike", "alpha", "november", "alpha",
"oscar", "alpha", "alpha", "papa"};
size_t const size = sizeof(words) / sizeof(string);
replace_if(words, words + size,
bind1st(equal_to<string>(), string("alpha")),
string("ALPHA"));
copy(words, words + size, ostream_iterator<string>(cout, " "));
cout << '\n';
}
/*
출력:
kilo ALPHA lima mike ALPHA november ALPHA oscar ALPHA ALPHA papa
*/
<algorithm>
void reverse(BidirectionalIterator first, BidirectionalIterator last);
[first, last)가 가리키는 범위의 원소를 뒤집는다.
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
int main()
{
string line;
while (getline(cin, line))
{
reverse(line.begin(), line.end());
cout << line << '\n';
}
}
<algorithm>
OutputIterator reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result);
[first, last)가 가리키는 원소들을 역순으로 [result, returnvalue) 범위에 복사한다. returnvalue 값은 이 함수가 돌려준 값이다.
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
int main()
{
string line;
while (getline(cin, line))
{
size_t size = line.size();
char copy[size + 1];
cout << "line: " << line << '\n' <<
"reversed: ";
reverse_copy(line.begin(), line.end(), copy);
copy[size] = 0; // 0은 뒤집힌 줄에
// 포함되지 않는다!
cout << copy << '\n';
}
}
<algorithm>
void rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);
[first, middle) 범위의 원소를 컨테이너의 끝으로 이동시킨다. [middle, last) 범위의 원소를 컨테이너의 처음으로 이동시킨다. 두 부분집합의 순서는 그대로 유지한다.
#include <algorithm>
#include <iostream>
#include <string>
#include <iterator>
using namespace std;
int main()
{
string words[] =
{ "kilo", "lima", "mike", "november", "oscar",
"foxtrot", "golf", "hotel", "india", "juliet" };
size_t const size = sizeof(words) / sizeof(string);
size_t const midsize = size / 2;
rotate(words, words + midsize, words + size);
copy(words, words + size, ostream_iterator<string>(cout, " "));
cout << '\n';
}
/*
출력:
foxtrot golf hotel india juliet kilo lima mike november oscar
*/
<algorithm>
OutputIterator rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result);
[middle, last) 범위의 원소와 그리고 [first, middle) 범위의 원소를 범위가 [result, returnvalue)인 목표 컨테이너에 복사한다. 여기에서 returnvalue는 이 함수가 돌려주는 반복자이다. 두 부분집합의 원래 순서는 바뀌지 않는다.
#include <algorithm>
#include <iostream>
#include <string>
#include <iterator>
using namespace std;
int main()
{
string words[] =
{ "kilo", "lima", "mike", "november", "oscar",
"foxtrot", "golf", "hotel", "india", "juliet" };
size_t const size = sizeof(words) / sizeof(string);
size_t const midsize = size / 2;
string out[size];
copy(out,
rotate_copy(words, words + midsize, words + size, out),
ostream_iterator<string>(cout, " "));
cout << '\n';
}
/*
출력:
foxtrot golf hotel india juliet kilo lima mike november oscar
*/
<algorithm>
ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2);
ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
#include <algorithm>
#include <iostream>
#include <iterator>
using namespace std;
class absInt
{
public:
bool operator()(int i1, int i2) const
{
return abs(i1) == abs(i2);
}
};
int main()
{
int range1[] = {-2, -4, -6, -8, 2, 4, 6, 8};
int range2[] = {6, 8};
copy
(
search(range1, range1 + 8, range2, range2 + 2),
range1 + 8,
ostream_iterator<int>(cout, " ")
);
cout << '\n';
copy
(
search(range1, range1 + 8, range2, range2 + 2, absInt()),
range1 + 8,
ostream_iterator<int>(cout, " ")
);
cout << '\n';
}
/*
출력:
6 8
-6 -8 2 4 6 8
*/
<algorithm>
ForwardIterator1 search_n(ForwardIterator1 first1, ForwardIterator1 last1, Size count, Type const &value);
ForwardIterator1 search_n(ForwardIterator1 first1, ForwardIterator1 last1, Size count, Type const &value, BinaryPredicate pred);
[first1, last1) 범위에서 값이 value인 원소가 n 개 연속적으로 발견되면 그 위치를 가리키는 반복자를 돌려준다. 비교를 위해 반복자가 가리키는 데이터 유형의 operator== 연산자를 사용한다. 그런 위치가 존재하지 않으면 last1이 반환된다.
[first1, last1) 범위에서 값이 value인 원소가 n 개 연속적으로 발견되면 그 위치를 가리키는 반복자를 돌려준다. 비교를 위해 제공된 이항 pred 진위 함수를 사용한다. 그런 위치가 존재하지 않으면 last1이 반환된다.
#include <algorithm>
#include <iostream>
#include <iterator>
using namespace std;
bool eqInt(int i1, int i2)
{
return abs(i1) == abs(i2);
}
int main()
{
int range1[] = {-2, -4, -4, -6, -8, 2, 4, 4, 6, 8};
copy
(
search_n(range1, range1 + 8, 2, 4),
range1 + 8,
ostream_iterator<int>(cout, " ")
);
cout << '\n';
copy
(
search_n(range1, range1 + 8, 2, 4, eqInt),
range1 + 8,
ostream_iterator<int>(cout, " ")
);
cout << '\n';
}
/*
출력:
4 4
-4 -4 -6 -8 2 4 4
*/
<algorithm>
OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
[first1, last1) 범위의 원소 중에서 [first2, last2) 범위에 없는 원소들을 정렬하여 돌려준다. 그 범위는 result에서 시작하여 함수가 돌려주는 OutputIterator에서 끝난다. 두 범위의 원소는 미리 반복자가 가리키는 데이터 유형의 operator< 연산자를 사용하여 정렬되어 있어야 한다.
[first1, last1) 범위의 원소 중에서 [first2, last2) 범위에 없는 원소들을 정렬하여 돌려준다. 그 범위는 result에서 시작하여 함수가 돌려주는 OutputIterator에서 끝난다. 두 범위의 원소는 미리 comp 함수객체를 사용하여 정렬되어 있어야 한다.
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <iterator>
using namespace std;
bool caseless(string const &left, string const &right)
{
return strcasecmp(left.c_str(), right.c_str()) < 0;
}
int main()
{
string set1[] = { "kilo", "lima", "mike", "november",
"oscar", "papa", "quebec" };
string set2[] = { "papa", "quebec", "romeo"};
string result[7];
string *returned;
copy(result,
set_difference(set1, set1 + 7, set2, set2 + 3, result),
ostream_iterator<string>(cout, " "));
cout << '\n';
string set3[] = { "PAPA", "QUEBEC", "ROMEO"};
copy(result,
set_difference(set1, set1 + 7, set3, set3 + 3, result,
caseless),
ostream_iterator<string>(cout, " "));
cout << '\n';
}
/*
출력:
kilo lima mike november oscar
kilo lima mike november oscar
*/
<algorithm>
OutputIterator set_intersection(InputIterator1 first1, InputIterator1) linebreak() tt(last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
[first1, last1) 범위의 원소 중에서 [first2, last2) 범위에도 있는 원소들을 정렬하여 돌려준다. 그 범위는 result에서 시작하여 함수가 돌려주는 OutputIterator에서 끝난다. 두 범위의 원소는 미리 반복자가 가리키는 데이터 유형의 operator< 연산자를 사용하여 정렬되어 있어야 한다.
[first1, last1) 범위의 원소 중에서 [first2, last2) 범위에도 있는 원소들을 정렬하여 돌려준다. 그 범위는 result에서 시작하여 함수가 돌려주는 OutputIterator에서 끝난다. 두 범위의 원소는 미리 comp 함수객체를 사용하여 정렬되어 있어야 한다.
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <iterator>
using namespace std;
bool caseless(string const &left, string const &right)
{
return strcasecmp(left.c_str(), right.c_str()) < 0;
}
int main()
{
string set1[] = { "kilo", "lima", "mike", "november",
"oscar", "papa", "quebec" };
string set2[] = { "papa", "quebec", "romeo"};
string result[7];
string *returned;
copy(result,
set_intersection(set1, set1 + 7, set2, set2 + 3, result),
ostream_iterator<string>(cout, " "));
cout << '\n';
string set3[] = { "PAPA", "QUEBEC", "ROMEO"};
copy(result,
set_intersection(set1, set1 + 7, set3, set3 + 3, result,
caseless),
ostream_iterator<string>(cout, " "));
cout << '\n';
}
/*
출력:
papa quebec
papa quebec
*/
<algorithm>
OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
[first1, last1) 범위의 원소 중에서 [first2, last2) 범위에 없고 [first2, last2) 범위의 원소 중에서 [first1, last1) 범위에 없는 원소들을 정렬하여 돌려준다. 그 범위는 result에서 시작하여 함수가 돌려주는 OutputIterator에서 끝난다. 두 범위의 원소는 미리 반복자가 가리키는 데이터 유형의 operator< 연산자를 사용하여 정렬되어 있어야 한다.
[first1, last1) 범위의 원소 중에서 [first2, last2) 범위에 없고 [first2, last2) 범위의 원소 중에서 [first1, last1) 범위에 없는 원소들을 정렬하여 돌려준다. 그 범위는 result에서 시작하여 함수가 돌려주는 OutputIterator에서 끝난다. 두 범위의 원소는 미리 comp 함수객체를 사용하여 정렬되어 있어야 한다.
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <iterator>
using namespace std;
bool caseless(string const &left, string const &right)
{
return strcasecmp(left.c_str(), right.c_str()) < 0;
}
int main()
{
string set1[] = { "kilo", "lima", "mike", "november",
"oscar", "papa", "quebec" };
string set2[] = { "papa", "quebec", "romeo"};
string result[7];
copy(result,
set_symmetric_difference(set1, set1 + 7, set2, set2 + 3,
result),
ostream_iterator<string>(cout, " "));
cout << '\n';
string set3[] = { "PAPA", "QUEBEC", "ROMEO"};
copy(result,
set_symmetric_difference(set1, set1 + 7, set3, set3 + 3,
result, caseless),
ostream_iterator<string>(cout, " "));
cout << '\n';
}
/*
출력:
kilo lima mike november oscar romeo
kilo lima mike november oscar ROMEO
*/
<algorithm>
OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
[first1, last1) 범위나 [first2, last2) 범위 또는 두 범위에 있는 원소들을 정렬하여 반환한다. result에서 시작해서 OutputIterator에서 끝난다. 두 범위 안에 있는 원소는 반드시 먼저 정렬해 두어야 한다. 반복자가 가리키도록 데이터 유형의 operator<를 사용해야 한다. 최종 범위에서 각 원소는 오직 한 번만 나타남을 눈여겨보라.
[first1, last1) 범위나 [first2, last2) 범위 또는 두 범위에 있는 원소들을 정렬하여 반환한다. result에서 시작하고 OutputIterator에서 끝난다. 두 범위에 있는 원소들은 반드시 먼저 comp 함수객체를 사용하여 정렬되어 있어야 한다. 마지막 범위에서 각 원소는 한 번만 나타남을 유의하라.
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <iterator>
using namespace std;
bool caseless(string const &left, string const &right)
{
return strcasecmp(left.c_str(), right.c_str()) < 0;
}
int main()
{
string set1[] = { "kilo", "lima", "mike", "november",
"oscar", "papa", "quebec" };
string set2[] = { "papa", "quebec", "romeo"};
string result[8];
copy(result,
set_union(set1, set1 + 7, set2, set2 + 3, result),
ostream_iterator<string>(cout, " "));
cout << '\n';
string set3[] = { "PAPA", "QUEBEC", "ROMEO"};
copy(result,
set_union(set1, set1 + 7, set3, set3 + 3, result, caseless),
ostream_iterator<string>(cout, " "));
cout << '\n';
}
/*
출력:
kilo lima mike november oscar papa quebec romeo
kilo lima mike november oscar papa quebec ROMEO
*/
<algorithm>
void sort(RandomAccessIterator first, RandomAccessIterator last);
void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
#include <algorithm>
#include <iostream>
#include <string>
#include <functional>
#include <iterator>
using namespace std;
int main()
{
string words[] = {"november", "kilo", "mike", "lima",
"oscar", "quebec", "papa"};
sort(words, words + 7);
copy(words, words + 7, ostream_iterator<string>(cout, " "));
cout << '\n';
sort(words, words + 7, greater<string>());
copy(words, words + 7, ostream_iterator<string>(cout, " "));
cout << '\n';
}
/*
출력:
kilo lima mike november oscar papa quebec
quebec papa oscar november mike lima kilo
*/
<algorithm>
BidirectionalIterator stable_partition(BidirectionalIterator first, BidirectionalIterator last, UnaryPredicate pred);
[first, last) 범위에서 단항 pred 진위함수가 true로 평가한 원소들이 false로 평가된 원소들보다 앞에 배치된다. 이런 순서 변경을 제외하고 false로 평가된 모든 원소의 상대적 순서는 유지된다. 그리고 true로 평가된 모든 원소의 상대적 순서도 그대로 유지된다. 반환 값은 구획된 범위에서 pred가 true로 평가한 마지막 원소 다음을 가리킨다.
#include <algorithm>
#include <iostream>
#include <string>
#include <functional>
#include <iterator>
using namespace std;
int main()
{
int org[] = {1, 3, 5, 7, 9, 10, 2, 8, 6, 4};
int ia[10];
int *split;
copy(org, org + 10, ia);
split = partition(ia, ia + 10, bind2nd(less_equal<int>(), ia[9]));
cout << "Last element <= 4 is ia[" << split - ia - 1 << "]\n";
copy(ia, ia + 10, ostream_iterator<int>(cout, " "));
cout << '\n';
copy(org, org + 10, ia);
split = stable_partition(ia, ia + 10,
bind2nd(less_equal<int>(), ia[9]));
cout << "Last element <= 4 is ia[" << split - ia - 1 << "]\n";
copy(ia, ia + 10, ostream_iterator<int>(cout, " "));
cout << '\n';
}
/*
출력:
Last element <= 4 is ia[3]
1 3 4 2 9 10 7 8 6 5
Last element <= 4 is ia[3]
1 3 2 4 5 7 9 10 8 6
*/
<algorithm>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last);
void stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <iterator>
using namespace std;
struct Pss: public pair<string, string> // 1
{
Pss(string const &s1, string const &s2)
:
pair<string, string>(s1, s2)
{}
};
ostream &operator<<(ostream &out, Pss const &p) // 2
{
return out << " " << p.first << " " << p.second << '\n';
}
class Sortby
{
string Pss::*d_field;
public:
Sortby(string Pss::*field) // 3
:
d_field(field)
{}
bool operator()(Pss const &p1, Pss const &p2) const // 4
{
return p1.*d_field < p2.*d_field;
}
};
int main()
{
vector<Pss> namecity { // 5
Pss("Hampson", "Godalming"),
Pss("Moran", "Eugene"),
Pss("Goldberg", "Eugene"),
Pss("Moran", "Godalming"),
Pss("Goldberg", "Chicago"),
Pss("Hampson", "Eugene")
};
sort(namecity.begin(), namecity.end(), Sortby(&Pss::first));// 6
cout << "sorted by names:\n";
copy(namecity.begin(), namecity.end(), ostream_iterator<Pss>(cout));
// 7
stable_sort(namecity.begin(), namecity.end(), Sortby(&Pss::second));
cout << "sorted by names within sorted cities:\n";
copy(namecity.begin(), namecity.end(), ostream_iterator<Pss>(cout));
}
/*
출력:
sorted by names:
Goldberg Eugene
Goldberg Chicago
Hampson Godalming
Hampson Eugene
Moran Eugene
Moran Godalming
sorted by names within sorted cities:
Goldberg Chicago
Goldberg Eugene
Hampson Eugene
Moran Eugene
Hampson Godalming
Moran Godalming
*/
// 1에서 Pss 포장 구조체를 생성해 std::pair<std::string, std::string>을 둘러 싼다. 여기에서 의도는 클래스를 둘러싼 포장 유형을 정의하는 것이다. 이 클래스는 std 이름공간에 정의되고 그에 대하여 삽입 연산자는 정의되어 있지 않다. 이런 식의 구조체 설계는 14.7절에 요약한 원리에 위배된다. 그렇지만 여기에서의 상속은 옹호할 만하다. 여기에서 그 의도는 `빠진 특징'을 추가하는 것이 아니고 pair 자체가 본질적으로 그저 평범한 구형 데이터이기 때문이다.
// 2), operator<< 연산자를 Pss 객체에 대하여 중복정의한다. 컴파일러가 불평하지는 않겠지만 pair<string, string> 유형에 대하여 std 이름공간에 이 연산자를 정의했다면 이 역시 나쁜 스타일이 될 것이다.
std 이름공간에 보통의 프로그램은 진입이 금지되어 있기 때문이다. pair<string, string> 둘레에 포장 유형을 정의하면 나쁜 스타일을 방지할 수 있다.
// 3), Sortby 클래스를 정의한다. 익명 객체를 생성하여 정렬에 사용되는 Pss 데이터 멤버 중 하나를 가리키는 포인터를 받을 수 있다. 이 경우, 두 멤버 모두 string 객체이므로 생성자를 쉽게 정의할 수 있다. 이 생성자는 Pss 클래스의 string 멤버를 포인터로 기대한다.
Sortby의 operator() 멤버는 (// 4) Pss 객체에 대하여 두 개의 참조를 받는다. 그리고 그 멤버를 가리키는 포인터를 이용하여 Pss 객체의 적절한 필드를 비교한다.
main에서 약간의 데이터를 vector에 저장한다 (// 5).
// 6) 첫 번째 정렬이 일어난다. 가장 중요도가 낮은 기준이 먼저 정렬되어야 하며 이를 위해서는 sort면 충분하다. 이름을 도시 안에서 정렬하고 싶으므로 이름이 가장 중요도가 낮은 기준을 대표한다. 그래서 이름으로 정렬한다. Sortby(&Pss::first).
// 7). stable_sort에서 이름에 상대적인 순서는 절대로 바뀌지 않으므로 도시를 정렬할 때 순위가 같다면 기존의 순서를 깨지 않는 방식으로 해결된다. 그래서 다음과 같은 순서대로 얻게 된다 (Goldberg in Eugene, Hampson in Eugene, Moran in Eugene). 도시를 기준으로 정렬하기 위해 또다른 익명 Sortby 객체를 사용한다. Sortby(&Pss::second).
<algorithm>
void swap(Type &object1, Type &object2);
object1 원소와 object2 원소가 값을 서로 교환한다.
(가능하면) 순환 복사 할당 또는 순환 이동 할당을 사용한다.
#include <algorithm>
#include <iostream>
#include <string>
#include <iterator>
using namespace std;
int main()
{
string first[] = {"alpha", "bravo", "charley"};
string second[] = {"echo", "foxtrot", "golf"};
size_t const n = sizeof(first) / sizeof(string);
cout << "Before:\n";
copy(first, first + n, ostream_iterator<string>(cout, " "));
cout << '\n';
copy(second, second + n, ostream_iterator<string>(cout, " "));
cout << '\n';
for (size_t idx = 0; idx < n; ++idx)
swap(first[idx], second[idx]);
cout << "After:\n";
copy(first, first + n, ostream_iterator<string>(cout, " "));
cout << '\n';
copy(second, second + n, ostream_iterator<string>(cout, " "));
cout << '\n';
}
/*
출력:
Before:
alpha bravo charley
echo foxtrot golf
After:
echo foxtrot golf
alpha bravo charley
*/
<algorithm>
ForwardIterator2 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 result);
[first1, last1)가 가리키는 범위의 원소를 [result, returnvalue) 범위의 원소로 교체한다. 여기에서 returnvalue는 이 함수가 돌려준 값이다. 두 범위는 분리되어 있어야 한다.
#include <algorithm>
#include <iostream>
#include <string>
#include <iterator>
using namespace std;
int main()
{
string first[] = {"alpha", "bravo", "charley"};
string second[] = {"echo", "foxtrot", "golf"};
size_t const n = sizeof(first) / sizeof(string);
cout << "Before:\n";
copy(first, first + n, ostream_iterator<string>(cout, " "));
cout << '\n';
copy(second, second + n, ostream_iterator<string>(cout, " "));
cout << '\n';
swap_ranges(first, first + n, second);
cout << "After:\n";
copy(first, first + n, ostream_iterator<string>(cout, " "));
cout << '\n';
copy(second, second + n, ostream_iterator<string>(cout, " "));
cout << '\n';
}
/*
출력:
Before:
alpha bravo charley
echo foxtrot golf
After:
echo foxtrot golf
alpha bravo charley
*/
<algorithm>
OutputIterator transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperator op);
OutputIterator transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryOperator op);
op 연산자를 [first, last) 범위의 각 원소에 적용한다. 그리고 결과 값을 result에서 시작하는 범위에 저장한다. 반환 값은 마지막으로 생성된 원소 바로 다음을 가리킨다.
op 연산자를 [first1, last1) 범위의 각 원소에 그리고 first2에서 시작하는 두 번째 범위에서 상응하는 원소에 적용한다. 결과 값은 result에서 시작하는 범위에 저장한다. 반환 값은 마지막으로 생성된 원소 바로 다음을 가리킨다.
#include <functional>
#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
#include <cctype>
#include <iterator>
using namespace std;
string caps(string const &src)
{
string tmp;
tmp.resize(src.length());
transform(src.begin(), src.end(), tmp.begin(), ::toupper);
return tmp;
}
int main()
{
string words[] = {"alpha", "bravo", "charley"};
copy(words, transform(words, words + 3, words, caps),
ostream_iterator<string>(cout, " "));
cout << '\n';
int values[] = {1, 2, 3, 4, 5};
vector<int> squares;
transform(values, values + 5, values,
back_inserter(squares), multiplies<int>());
copy(squares.begin(), squares.end(),
ostream_iterator<int>(cout, " "));
cout << '\n';
}
/*
출력:
ALPHA BRAVO CHARLEY
1 4 9 16 25
*/
for_each (19.1.17항)와 transform 총칭 알고리즘 사이의 다음 차이를 꼭 알아야 한다.
transform은 함수객체의 operator() 멤버의 반환 값이 사용된다. operator() 멤버에 건넨 인자 자체는 변경되지 않는다.
for_each는 함수객체의 operator() 멤버가 인자를 참조로 받는다. 이 때문에 변경될 수 있다.
transform 총칭 알고리즘 대신에 범위-기반의 for 회돌이를 사용할 수 있음도 주목하자. 그렇지만 범위-기반의 for-회돌이와 다르게 transform 알고리즘은 부-범위와 역방향 반복자와도 사용될 수 있다.
<algorithm>
ForwardIterator unique(ForwardIterator first, ForwardIterator last);
ForwardIterator unique(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);
operator== 연산자를 사용하여 [first, last) 범위에서 연속적으로 동일한 원소중 첫 원소만 제외하고 모두 범위의 끝으로 재배치한다. 반환된 정방향 반복자는 잔재의 시작을 가리킨다. [first, return-value) 범위의 원소는 모두 다르다. [return-value, last) 범위의 원소는 모두 [first, return-value) 범위의 원소와 동일하다.
[first, last) 반복자 범위에서 잇다르는 원소 중, 이항 pred 진위함수가 true를 돌려주는 첫 원소를 제외하고 모두 범위의 끝으로 재배치한다 (반복자가 가리키는 데이터 유형의 인자를 두 개 기대한다). 반환된 정방향 반복자는 잔재의 첫 원소를 가리킨다. [first, return-value) 범위의 모든 원소 쌍에 대하여 pred는 false를 돌려준다 (즉, 해당 원소들은 유일하다). 반면에 pred는 [return-value, last) 범위의 첫 번째 원소와 [first, return-value) 범위의 두 번째 원소의 쌍에 대하여 true를 돌려준다.
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <iterator>
using namespace std;
bool casestring(string const &first, string const &second)
{
return strcasecmp(first.c_str(), second.c_str()) == 0;
}
int main()
{
string words[] = {"alpha", "alpha", "Alpha", "papa", "quebec" };
size_t const size = sizeof(words) / sizeof(string);
string *removed = unique(words, words + size);
copy(words, removed, ostream_iterator<string>(cout, " "));
cout << '\n'
<< "Trailing elements are:\n";
copy(removed, words + size, ostream_iterator<string>(cout, " "));
cout << '\n';
removed = unique(words, words + size, casestring);
copy(words, removed, ostream_iterator<string>(cout, " "));
cout << '\n'
<< "Trailing elements are:\n";
copy(removed, words + size, ostream_iterator<string>(cout, " "));
cout << '\n';
}
/*
출력:
alpha Alpha papa quebec
Trailing elements are:
quebec
alpha papa quebec
Trailing elements are:
quebec quebec
*/
<algorithm>
OutputIterator unique_copy(InputIterator first, InputIterator last, OutputIterator result);
OutputIterator unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate pred);
[first, last) 범위의 원소를 result에서 시작하는 결과 컨테이너에 복사한다. 연속적으로 동일한 원소들은 한 번만 (동일한 원소 중 첫 번째 원소만) 복사한다 (반복자가 가리키는 데이터 유형의 operator== 연산자를 사용한다). 반환된 출력 반복자는 마지막으로 복사된 원소 바로 다음을 가리킨다.
[first, last) 범위의 원소를 result에서 시작하는 결과 컨테이너에 복사한다. [first, last) 범위에서 연속적으로 동일한 원소들 중 이항 pred 진위함수가 true를 돌려주는 원소를 한 번만 (동일한 원소들 중 첫 번째 원소만) 복사한다. 반환된 출력 반복자는 마지막으로 복사된 원소 바로 다음을 가리킨다.
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <cstring>
using namespace std;
bool casestring(string const &first, string const &second)
{
return strcasecmp(first.c_str(), second.c_str()) == 0;
}
int main()
{
string words[] = {"oscar", "Alpha", "alpha", "alpha",
"papa", "quebec" };
size_t const size = sizeof(words) / sizeof(string);
vector<string> remaining;
unique_copy(words, words + size, back_inserter(remaining));
copy(remaining.begin(), remaining.end(),
ostream_iterator<string>(cout, " "));
cout << '\n';
vector<string> remaining2;
unique_copy(words, words + size,
back_inserter(remaining2), casestring);
copy(remaining2.begin(), remaining2.end(),
ostream_iterator<string>(cout, " "));
cout << '\n';
}
/*
출력:
oscar Alpha alpha papa quebec
oscar Alpha papa quebec
*/
<algorithm>
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, Type const &value);
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, Type const &value, Compare comp);
[first, last) 범위에 저장된 (올림차순으로) 정렬된 원소들 중에서 value보다 큰 첫 번째 원소를 찾는다. 반환된 반복자는 정렬된 순서를 깨지 않고 연속열에 value를 삽입할 수 있는 위치를 가리킨다. 반복자가 가리키는 데이터 유형의 operator< 연산자를 사용한다. 그런 원소를 발견하지 못하면 last가 반환된다.
[first, last) 범위의 원소는 함수객체 또는 comp 함수를 사용하여 정렬되어 있어야 한다. comp 함수를 사용하여 범위 안의 각 원소를 value와 비교한다. 이항 comp 진위함수를 해당 범위와 value에 적용하면 true를 돌려주는 첫 원소를 가리키는 반복자가 반환된다. 그런 원소를 발견하지 못하면 last가 반환된다.
#include <algorithm>
#include <iostream>
#include <functional>
#include <iterator>
using namespace std;
int main()
{
int ia[] = {10, 15, 15, 20, 30};
size_t n = sizeof(ia) / sizeof(int);
cout << "Sequence: ";
copy(ia, ia + n, ostream_iterator<int>(cout, " "));
cout << '\n';
cout << "15 can be inserted before " <<
*upper_bound(ia, ia + n, 15) << '\n';
cout << "35 can be inserted after " <<
(upper_bound(ia, ia + n, 35) == ia + n ?
"the last element" : "???") << '\n';
sort(ia, ia + n, greater<int>());
cout << "Sequence: ";
copy(ia, ia + n, ostream_iterator<int>(cout, " "));
cout << '\n';
cout << "15 can be inserted before " <<
*upper_bound(ia, ia + n, 15, greater<int>()) << '\n';
cout << "35 can be inserted before " <<
(upper_bound(ia, ia + n, 35, greater<int>()) == ia ?
"the first element " : "???") << '\n';
}
/*
출력:
Sequence: 10 15 15 20 30
15 can be inserted before 20
35 can be inserted after the last element
Sequence: 30 20 15 15 10
15 can be inserted before 10
35 can be inserted before the first element
*/
12, 11, 10, 8, 9, 7, 6, 1, 2, 4, 3, 5
다음 설명에서 이 배열에 있는 두 개의 포인터를 눈여겨보라:
node 포인터는 트리의 다음 노드 위치를 나타낸다. child 포인터는 node 포인터의 자손인 다음 원소를 가리킨다. 처음에 node는 첫 원소를 가리킨다. 그리고 child는 두 번째 원소를 가리킨다.
*child++ (11) 과 *child++ (10)이며, 둘 모두 12보다 작다.
*node++ (== 11))는 *child++ (8)과 *child++ (9)를 그의 자손으로 가진다.
*node++ (== 10))는 *child++ (7)과 *child++ (6) 를 그의 자손으로 가진다.
*node++ (== 8))는 *child++ (1)과 *child++ (2)를 그의 자손으로 가진다.
*node++ (== 9))는 자손으로 *child++ (4)와 *child++ (3)를 가진다.
*node++ (== 7))는 하나의 자손 *child++ (5)를 가진다.
child는 이제 배열을 넘어서 가리키기 때문에 나머지 노드는 자손이 없다. 그래서 노드 6, 1, 2, 4, 3 그리고 5는 자손이 없다.
왼쪽 오른쪽 가지에 순서가 없는 것을 눈여겨보라. 8은 9보다 작지만 7은 6보다 크다.
최상단 노드부터 시작하여 이진 트리 레벨 순서로 순회하며 힙이 생성된다. 최상단 노드는 12이고 레벨은 0이다. 첫 레벨에 11과 10이 있다. 두 번째 레벨에 8, 9, 7 그리고 6이 있다 등등.
힙은 무작위 접근을 지원하는 컨테이너 안에 구성할 수 있다. 그래서 리스트는 힙에 적절한 데이터 구조가 아니다. 힙은 (정렬되지 않은) 배열로부터 구성할 수 있다 (make_heap 사용). 최상위-원소를 힙으로부터 제거하고 (pop_heap 사용) 새로운 원소를 힙에 추가하면 (push_heap 사용) 원소들이 재배열된다. 그리고 힙에 있는 원소들을 정렬할 수 있다 (sort_heap를 사용하면 된다. 물론 이렇게 하면 힙은 무효화 된다).
<algorithm>
void make_heap(RandomAccessIterator first, RandomAccessIterator last);
void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
make_heap을 사용하는 프로그램의 작은 예는 19.1.67.5: 힙 함수를 사용한 예제에서 볼 수 있다.
<algorithm>
void pop_heap(RandomAccessIterator first, RandomAccessIterator last);
void pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
[first, last) 범위의 첫 원소를 last - 1로 이동시킨다. 다음, [first, last - 1) 범위의 원소의 순서를 바꾸어서 최대-힙을 형성한다. 비교를 위해 반복자가 가리키는 데이터 유형의 operator< 연산자를 사용한다.
[first, last) 범위의 첫 원소를 last - 1로 이동시킨다. 다음, [first, last - 1) 범위의 원소의 순서를 바꾸어서 최대-힙을 형성한다. 비교를 위해 이항 comp 비교 함수객체를 사용한다.
pop_heap을 사용하는 프로그램의 예는 이 링크를 따라가라.
<algorithm>
void push_heap(RandomAccessIterator first, RandomAccessIterator last);
void push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
[first, last - 1) 범위에 유효한 힙이 담겨 있고, 힙에 추가할 원소가 last - 1 위치에 있다고 가정하고서, [first, last - 1) 범위의 원소의 순서를 바꾸어서 최대-힙을 형성한다. 비교를 위해 반복자가 가리키는 데이터 유형의 operator< 연산자를 사용한다.
[first, last - 1) 범위에 유효한 힙이 담겨 있고, 힙에 추가할 원소가 last - 1 위치에 있다고 가정하고서, [first, last - 1) 범위의 원소의 순서를 바꾸어서 최대-힙을 형성한다. 비교를 위해 이항 comp 비교 함수객체를 사용한다.
push_heap을 사용하는 프로그램의 예는 이 링크를 따라가라.
<algorithm>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last);
void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
sort_heap를 사용하는 작은 프로그램의 예는 다음 링크를 따라가라.
#include <algorithm>
#include <iostream>
#include <functional>
#include <iterator>
using namespace std;
void show(int *ia, char const *header)
{
cout << header << ":\n";
copy(ia, ia + 20, ostream_iterator<int>(cout, " "));
cout << '\n';
}
int main()
{
int ia[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
make_heap(ia, ia + 20);
show(ia, "The values 1-20 in a max-heap");
pop_heap(ia, ia + 20);
show(ia, "Removing the first element (now at the end)");
push_heap(ia, ia + 20);
show(ia, "Adding 20 (at the end) to the heap again");
sort_heap(ia, ia + 20);
show(ia, "Sorting the elements in the heap");
make_heap(ia, ia + 20, greater<int>());
show(ia, "The values 1-20 in a heap, using > (and beyond too)");
pop_heap(ia, ia + 20, greater<int>());
show(ia, "Removing the first element (now at the end)");
push_heap(ia, ia + 20, greater<int>());
show(ia, "Re-adding the removed element");
sort_heap(ia, ia + 20, greater<int>());
show(ia, "Sorting the elements in the heap");
}
/*
출력:
The values 1-20 in a max-heap:
20 19 15 18 11 13 14 17 9 10 2 12 6 3 7 16 8 4 1 5
Removing the first element (now at the end):
19 18 15 17 11 13 14 16 9 10 2 12 6 3 7 5 8 4 1 20
Adding 20 (at the end) to the heap again:
20 19 15 17 18 13 14 16 9 11 2 12 6 3 7 5 8 4 1 10
Sorting the elements in the heap:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
The values 1-20 in a heap, using > (and beyond too):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Removing the first element (now at the end):
2 4 3 8 5 6 7 16 9 10 11 12 13 14 15 20 17 18 19 1
Re-adding the removed element:
1 2 3 8 4 6 7 16 9 5 11 12 13 14 15 20 17 18 19 10
Sorting the elements in the heap:
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
*/
<functional> 헤더를 포함해야 한다.
멤버 함수 어댑터는 표준 템플릿 라이브러리의 일부이다. 총칭 알고리즘과 조합해 사용하면 아주 유용하다. 이 때문에 STL에 할애한 이전 장보다 이 장에 다룬다.
STL에 정의된 멤버 함수 어댑터로 (매개변수 없는) 클래스 객체의 멤버 함수를 마치 비-멤버 함수처럼 호출할 수 있다. 그리고 이항 또는 단일 인자의 함수를 함수객체 안으로 합성해 넣으면 총칭 알고리즘에 결합해 사용할 수 있다.
다음 절에 멤버 함수를 비-멤버 함수처럼 호출하는 방법을 다룬다. 그 다음에 어댑터를 적용할 수 있는 함수를 다룬다.
bind로 쉽게 대체할 수 있기 때문이다. 멤버 함수 어댑터를 간략하게 언급한다. 대신에 bind를 어떻게 사용할 수 있는지 보여준다.
다음 클래스를 연구해 보자:
class Data
{
public:
void display();
};
확실히 display 멤버는 Data 객체에 저장된 정보를 보여준다.
Data 객체를 벡터에 저장할 때 for_each 총칭 알고리즘은 벡터에 저장된 각 객체의 display 멤버를 호출하는 데 사용하기가 쉽지 않다. for_each가 (비-멤버) 함수나 함수객체는 세 번째 인자로 받지만 멤버 함수는 받지 않기 때문이다.
멤버 함수 어댑터 mem_fun_ref와 bind를 사용하면 이 문제를 해결할 수 있다. mem_fun_ref는 매개변수가 정의되어 있지 않은 멤버 함수의 주소를 예상한다. 그리고 mem_fun_ref의 함수 호출 연산자는 자신에게 인자로 건네어진 객체에 대하여 그 멤버 함수를 호출한다. 예제는 그 사용법과 더불어 bind의 또다른 사용법을 보여준다. (std 이름공간과 placeholders 이름공간을 사용한다고 간주한다):
int main()
{
vector<Data> data;
// C++17에서 비추천됨
for_each(data.begin(), data.end(), mem_fun_ref(&Data::display));
// 다른 방식, bind 사용
for_each(data.begin(), data.end(), bind(&Data::display, _1));
}
두 번째 멤버 함수 어댑터는 mem_fun이다. 객체를 가리키는 포인터로부터 멤버 함수를 호출하는 데 사용된다. 여기에서 bind도 사용할 수 있다. data 벡터에 있는 포인터를 (사용된다면 shared_ptr 객체도 역시) 탐지하기 때문이다.
int main()
{
vector<Data *> data { new Data };
// C++17에서 비추천됨
for_each(data.begin(), data.end(), mem_fun(&Data::display));
// 다른 방식, bind 사용
for_each(data.begin(), data.end(), bind(&Data::display, _1));
delete data[0];
}
result_type을 정의하고 있는 함수객체이다.
STL은 pointer_to_unary_function과 pointer_to_binary_function을 어댑터로 정의하고 있다. 각각 단항 함수와 이항 함수를 포인터로 받아서 적용가능한 함수로 변환한다.
ptr_fun에 단일 함수를 건네면 pointer_to_unary_function를 사용하여 적용가능한 단일 함수를 만든다. 이항 함수를 제공하면 pointer_to_binary_function를 사용하여 적용가능한 이항 함수를 만든다.
그렇지만 이 어댑터들은 ptr_fun과 함께 미래의 C++17 표준에서는 비추천되었다. 왜냐하면 쉽게 람다 표현식으로 교체할 수 있기 때문이다.
다음 예제는 ptr_fun의 사용법을 보여준다. 적용가능한 이항 함수를 만든다. main 함수는 검색할 단어를 표준 입력 스트림으로부터 또 string 객체에 저장된 추가 단어들로부터 추출한다. 목표 단어가 발견되면 string 객체의 벡터에서 목표 단어 다음에 있는 단어를 보여준다. 검색은 대소문자를 구별하지 않고 POSIX 함수인 strcasecmp를 사용한다. ptr_fun을 사용한 다음에 동등한 표현식을 람다 표현식을 사용하여 보여준다.
#include <vector>
#include <algorithm>
#include <functional>
#include <cstring>
#include <string>
#include <iterator>
#include <iostream>
using namespace std;
inline int stringcasecmp(string lhs, string rhs)
{
return strcasecmp(lhs.c_str(), rhs.c_str());
}
int main()
{
string target;
cin >> target;
vector<string> v1;
copy(istream_iterator<string>(cin), istream_iterator<string>(),
back_inserter(v1));
auto pos = find_if( // C++17에서 비추천
v1.begin(), v1.end(),
not1( bind2nd(ptr_fun(stringcasecmp), target) )
);
// 더 좋은 대안은
auto pos = find_if(v1.begin(), v1.end(), // 람다 표현식이다.
[&](auto const &str)
{
return not stringcasecmp(str, target);
}
);
if ( pos != v1.end())
cout << "The search for `" << target << "' was successful.\n"
"The next string is: `" << pos[1] << "'.\n";
}
// 입력:
// VERY I have existed for years, but very little has changed
// 프로그램의 출력:
// The search for `VERY' was successful.
// The next string is: `little'.
민감한 독자라면 별로 효율적인 프로그램이 아님을 눈치채셨을 것이다. stringcasecmp 함수는 값 유형의 매개변수를 정의한다. 때문에 stringcasecmp가 호출될 때마다 인자의 사본을 생성해 거기에 건네야 한다. 그러나 매개변수 정의를 다음과 같이 바꾸면
inline int stringcasecmp(string const &lhs, string const &rhs)
컴파일러는 다음과 같은 에러 메시지를 토해 낸다.
In instantiation of 'std::binder2nd<std::pointer_to_binary_function<
const std::string&, const std::string&, int> >':
typename _Operation::result_type std::binder2nd<_Operation>::operator()(
typename _Operation::first_argument_type&) const
cannot be overloaded with:
typename _Operation::result_type std::binder2nd<_Operation>::operator()(
const typename _Operation::first_argument_type&) const
그렇지만 두 번째 find_if는 stringcasecmp의 값 매개변수를 const & 매개변수로 바꾸면 문제없이 컴파일된다. 이 때문에 예제에 람다 표현식을 선호한 것이다.