음악, 삶, 개발
<algorithm> (C+11 기준) 본문
소개
vector를 떡 주무르듯 편하게 사용하기 위해 반드시 알아야 하는 STL 라이브러리다.
#include <algorithm>위와 같이 include후 std:: 를 붙여 사용한다.
이 포스트는 C++11 기준이며, C++20 이 올해 말 출시한다고 한다.
하지만 C++20이 출시되어도, 바로 내가 사용할수있는것은 아니므로,
내가 사용할수있게 되었을 때 이 포스팅도 업데이트해야 함.
아래 <algorithm> 안에 들어가있는 함수의 총 리스트를 일단 나열하고,
그후 각각을 설명해나간다.
이제 배우겠지만, 이 <algorithm> 안에 함수들은 인자로 iterator 를 받는다.
우리가 vector 에서 index 대신 iteartor 를 쓰는 이유도 이런 표준 라이브러리의 함수들을
가져다 쓰기 위함이다. (index 대신 , iterator 를 인자로 받기때문에)
각각 설명에서 함수 내부를 첨부해놨는데, 이 함수 내부를 기억하는것이
각 함수를 실제로 이해하고 암기하는데에 있어서 매우 주요하게 작용한다.
이 algorithm 안에 함수들은 첫번째와 두번째 인자로 첫번째 iteartor 와 마지막 iterator 를 받으며,
범위는 [first, last) 이다. 이 last 는 어떠한 객체도 가리키지않는다는것을 기억하는것이 중요하다. 마지막 객체 + 1 인것이다.
또한 3번째 인자로 또 다른 함수들을 필요로하는데,
이 함수들은 iterator 의 역참조를 인자로 받아 실행할 함수이다.
이 함수들중 bool 을 return 하면 predicate 라고 하며, 이 함수를 pred 라는 인자로 넘기게된다.
그외에는 Function 이라고하며, fn 이라는 인자로 넘긴다.
pred 는 각 요소(iterator 의 역참조)에 대해 true 인지 false 인지 판별하는 역할을 하고,
fn 은 각 요소를 통해 실행할 함수이다.
Non-modifying sequence operations ; 컨테이너 요소들의 순서를 변경하지않음. 하지만 요소의 값은 변경될수있음.
Modifying sequence operations : 컨테이너 요소들의 순서를 변경함. 요소의 값도 변경될수있음.
Functions in <algorithm>
Non-modifying sequence operations
all_of
any_of
none_of
for_each
find
find_if
find_if_not
find_end
adjacent_find
count
count_if
mismatch
equal
is_permutation
search
search_n
Modifying sequence operations
copy
copy_n
copy_if
copy_backward
move
move_backword
swap
swap_ranges
iter_swap
transform
replace
replace_if
replace_copy
replace_copy_if
fill
fill_n
generate
generate_n
remove
remove_if
remove_copy
remove_copy_if
unique
unique_copy
reverse
reverse_copy
rotate
rotate_copy
random_shuffle
shuffle
Partitions
is_partitioned
partition
stable_partition
partition_copy
partition_print
Sorting
sort
stable_sort
partial_sort
partial_sort_copy
is_sorted
is_sorted_until
nth_element
Binary search (operating on partitioned/sorted ranges)
lower_bound
upper_bound
equal_range
binary_search
Merge (operating on sorted ranges)
merge
inplace_merge
includes
set_union
set_intersection
set_difference
set_symmetric_difference
Heap
push_heap
pop_heap
make_heap
sort_heap
is_heap
is_heap_until
Min/max
min
max
minmax
min_element
max_element
minmax_element
Other
lexicographical_compare
next_permutation
prev_permutation
bool all_of(first, last, pred)
설명
범위 안에, 즉 [first, last) 안의 모든 요소에 대한 pred 가 true 이면, true.
그 외에는 false. 범위가 empty 여도 false.
last는 마지막 요소 그다음을 가리키므로, 아무 요소도 가리키고 있지 않다.
내부적으로 first iterator를 루프로 ++해가면서, 각 iterator 가 가리키는 요소가
pred를 충족(true 또는 false)인지 확인한다.
하나라도 false 라면 바로 false를 return 해버린다. (뒤에 요소들은 확인하지 않고)
일종의 && (And) 이라고 볼수있다.
pred
범위의 요소를 인수로 받아들이고 bool로 변환 가능한 값을 반환하는 단항 함수이다.
foo(x) 처럼 하나의 인자를 받는 것을 단항 함수 (Unary Function) 이라고 부른다.
foo(x,y)처럼 두 개의 인자를 받는 것을 이항 함수 (Binary Function) 이라고 부른다
반환된 값은 요소가 이 함수에서 확인한 조건을 충족하는지 여부를 나타낸다.
함수는 인수를 수정해서는 안된다.
이것은 함수 포인터 또는 함수 객체 일 수 있다.
인자값을 변경해서는 안됨. (ref& 로 받지말라는 소리)
내부
template<class InputIterator, class UnaryPredicate>
bool all_of (InputIterator first, InputIterator last, UnaryPredicate pred) {
while (first!=last) {
if (!pred(*first)) return false;
++first;
}
return true;
}실제 내부
공식 예제
// all_of example
#include <iostream> // std::cout
#include <algorithm> // std::all_of
#include <array> // std::array
int main () {
std::array<int,8> foo = {3,5,7,11,13,17,19,23};
if ( std::all_of(foo.begin(), foo.end(), [](int i){return i%2;}) )
std::cout << "All the elements are odd numbers.\n";
return 0;
}내가 만든 예제
#include <JuceHeader.h>
#include <vector>
#include <algorithm>
#include <iostream>
bool isZero (int n) {
return n == 0;
}
int main () {
std::vector<int> v {2, 3, 2, 1, 0, 2};
// 모든 요소가 0 입니까?
bool allElementsAreZero = std::all_of(v.begin(), v.end(), isZero); // false
}Note
기본적으로 true 를 return 하도록 설계되어있지만,
요소 하나라도 pred 가 false 이면 false 를 return 한다는점을 명심하자.
pred 는 반드시 하나의 인자를 받는 함수여야함. (unary function)
bool any_of(first, last, pred)
설명
all_of 와 비슷하지만, all_of 는 일종의 &&인데 반해,
any_of 는 || (or) 로, pred 가 하나라도 true 이면 곧바로 true 를 return한다.
[first, last) 가 empty 이면 false 를 return 한다.
내부를 살펴보면 기본적으로 false 를 return 하도록 되어있다.
pred
return값이 bool 인 단항함수여야함. (unary function) 인자값을 변경해서는 안됨. (ref& 로 받지말라는 소리)
내부
template<class InputIterator, class UnaryPredicate>
bool any_of (InputIterator first, InputIterator last, UnaryPredicate pred) {
while (first!=last) {
if (pred(*first)) return true;
++first;
}
return false;
}실제내부
공식 예제
// any_of example
#include <iostream> // std::cout
#include <algorithm> // std::any_of
#include <array> // std::array
int main () {
std::array<int,7> foo = {0,1,-1,3,-3,5,-5};
if ( std::any_of(foo.begin(), foo.end(), [](int i){return i<0;}) )
std::cout << "There are negative elements in the range.\n";
return 0;
}내가 만든 예제
bool isZero (int n) {
return n == 0;
}
int main () {
std::vector<int> v {2, 3, 2, 1, 0, 2};
// 0 인 요소를 v 가 가지고있습니까?
bool hasZero = std::any_of(v.begin(), v.end(), isZero); // true
}bool none_of(first, last, pred)
설명
모든 요소에 대한 pred 가 false 이면 true 를 return 한다.
함수의 내부를 보면, pred 가 true 인 iterator 를 만나면, 곧바로 false 를 return 하도록 되어있다.
또한 기본적으로는 true 를 return 한다.
따라서 range 가 empty 라면 true 를 return 한다.
한마디로, 모든 요소가 pred 를 false 로 만들어야만 true 다.
모든 요소가 pred 를 충족하지않아야만 true 다.
"모두다 아프죠? 는 all_of 인 반면,
"아픈 사람 아무도 없죠?" 는 none_of 이며, 역시 일종의 &&.
pred
단항함수여야만함. 인자값을 변경해서는 안됨. (ref& 로 받지말라는 소리)
내부
template<class InputIterator, class UnaryPredicate>
bool none_of (InputIterator first, InputIterator last, UnaryPredicate pred) {
while (first!=last) {
if (pred(*first)) return false;
++first;
}
return true;
}실제 내부
공식 예제
// none_of example
#include <iostream> // std::cout
#include <algorithm> // std::none_of
#include <array> // std::array
int main () {
std::array<int,8> foo = {1,2,4,8,16,32,64,128};
if ( std::none_of(foo.begin(), foo.end(), [](int i){return i<0;}) )
std::cout << "There are no negative elements in the range.\n";
return 0;
}내가 만든 예제
bool isZero (int n) {
return n == 0;
}
int main () {
std::vector<int> v {2, 3, 2, 1, 3, 2};
// 0 인 요소가 없죠?
bool NoZero = std::none_of(v.begin(), v.end(), isZero); // true (네!)
}Function for_each(first, last, fn)
설명
함수 fn 을 모든 요소들에 적용하며, 전달한 함수 객체 fn 을 return 한다.
fn
fn 는 단항 함수여야하며,
iterator 가 const 가 아니거나, fn 이 const 함수가 아니라면, 각 요소를 변경할수있다.
중요한건, 이 fn 이 return 하는 값은 무엇이든간에 무시된다는것이다.
내부
template<class InputIterator, class Function>
Function for_each(InputIterator first, InputIterator last, Function fn) {
while (first!=last) {
fn (*first);
++first;
}
return fn; // or, since C++11: return move(fn);
}실제 내부
공식 예제
// for_each example
#include <iostream> // std::cout
#include <algorithm> // std::for_each
#include <vector> // std::vector
void myfunction (int i) { // function:
std::cout << ' ' << i;
}
struct myclass { // function object type:
void operator() (int i) {std::cout << ' ' << i;}
} myobject;
int main () {
std::vector<int> myvector;
myvector.push_back(10);
myvector.push_back(20);
myvector.push_back(30);
std::cout << "myvector contains:";
for_each (myvector.begin(), myvector.end(), myfunction);
std::cout << '\n';
// or:
std::cout << "myvector contains:";
for_each (myvector.begin(), myvector.end(), myobject);
std::cout << '\n';
return 0;
}위의 예제에서, myobject 라는 구조체를 만들고, 그안에 () 를 오버로딩하여
for_each 의 인자로 넘기는 것이 눈여겨볼 부분이다.
for_each vs for 루프
iterator 를 사용하여 for 루프를 하는 방법은 크게 3가지가있다.
// 방법 1 : 일반적인 for 루프
for(auto it = collection.begin(); it != collection.end() ; ++it) {
foo(*it);
}
// 방법 2 : std::for_each
std::for_each(collection.begin(), collection.end(), [](Element& e) {
foo(e);
});
// 방법 3 : range based for
for(Element& e : collection) {
foo(e);
}
나는 이 세가지중 과연 뭘 써야할지가 궁금해졌다.
이 질문은 결국 Raw Loops vs STL algorithm 에 대한 질문으로 볼수있다.
삶이 그렇듯이, "상황에 따라 적절히 필요한것으로" 가 대답일듯하다.
아래의 글들을 꼭 읽어보길 바란다.
Stackoverflow : Advantages of std::for_each over for loop
Why You Should Use std::for_each over Range-based For Loops
결론
range based for 루프를 사용하라!
for(Element& e : collection) {
foo(e);
}물론, 항상 이렇지만은 않을것이다.
algorithm 의 사용은 가독성을 향상 시켜주고,
적어도 내가 만든 함수보다는 훨씬 안정적일것이다.
find
지금부터는 어느정도 이해도가 생겼을테니,
설명전에 내부를 먼저 보여주겠다. 이것들을 보고 생각을해보라.
내부
template<class InputIterator, class T>
InputIterator find (InputIterator first, InputIterator last, const T& val) {
while (first!=last) {
if (*first==val) return first;
++first;
}
return last;
}실제 내부
설명
3번째 인자인 val 가 동일한 최초 발견된 요소의 iterator 를 return 한다.
순차적으로 first 를 ++ 해나가다가, 내가 넘긴 val 과 동일한 요소를 발견하면 이 요소의 iterator 를 return 한다.
중요한건, 뒤에 val 과 동일한 값이 있다해도 최초 발견 요소의 iterator 를 곧바로 return 해버린다는것을 기억하라.
또 하나 중요한점은 위의 내부를 보면 알수있듯이, == 로 비교를 하고있으므로,
내가 넘긴 val 이 만약 내가 만든 클래스라면 이 클래스는 반드시 == 를 연산자 오버로딩으로 정의하고있어야한다.
또한, 아무것도 일치하는것을 발견하지못하면 last iterator 를 return 한다.
공식 예제
// find example
#include <iostream> // std::cout
#include <algorithm> // std::find
#include <vector> // std::vector
int main () {
// using std::find with array and pointer:
int myints[] = { 10, 20, 30, 40 };
int * p;
p = std::find (myints, myints+4, 30);
if (p != myints+4)
std::cout << "Element found in myints: " << *p << '\n';
else
std::cout << "Element not found in myints\n";
// using std::find with vector and iterator:
std::vector<int> myvector (myints,myints+4);
std::vector<int>::iterator it;
it = find (myvector.begin(), myvector.end(), 30);
if (it != myvector.end())
std::cout << "Element found in myvector: " << *it << '\n';
else
std::cout << "Element not found in myvector\n";
return 0;
}참고자료
cplusplus.com 에는 과거 잘못된 정보가 있었다고한다.
하지만 개인적으로 cppreference 보다 cplusplus 가 난 더 쉽게 느껴진다.
일단 cplusplus 를 공부하고 cppreference 를 참고하는것으로 한다.
씹어먹는 C++ - <10 - 3. C++ STL - 알고리즘(algorithm)>
