algorithm의 정의

Container의 반복자를 이용해 정렬, 탐색, 삭제 등의 작업을 쉽게 수행할 수 있도록 도와주는 라이브러리

기본 형태

#include <algorithm>

template <typename Iter>
func(Iter begin, Iter end);

or

template <typename Iter, typename Pred>
func(Iter begin, Iter end, Pred pred)

• 첫번째 파라미터는 Iterator의 시작
• 두번째 파라미터는 Iterator의 끝
• 세번째 파라미터는 특정한 조건을 추가인자로 받는 경우가 있으며 이를 서술자(Predicate)라 부른다.
  

Predicate는 보통 bool을 반환하는 함수 객체(Functor)를 전달하게 된다.

find, find_if

std::find(Iter first, Iter last, const T& value

first부터 last까지 순회를 하며 value와 같은 원소가 있는지 확인하고 있다면 이를 가리키는 iterator를 반환한다.
std::find(Iter first, Iter last, Pred pred
first부터 last까지 순회를 하며 pred 조건에 맞는 iterator를 반환한ek.

algorithm 라이브러리의 find 외에도 unordered_set.find(), set.find() 등의 탐색 맴버 함수가 있다.

std::find()의 구조는 for문을 이용한 순회이기 때문에 멤버 함수의 탐색보다 느리다.

• std::find() O(n)
• set.find() O(log n)
• unordered_set.find() O(1)

똑같은 기능의 함수가 있다면 보통 멤버 함수를 쓰는게 유용하다.

예제

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

using namespace std;

struct Func {
	bool operator()(int value) const {
		return value;
	}
};

int main() {
	vector<int> v{ 1, 2, 3 };
	auto iter = std::find_if(v.begin(), v.end(), [](const int& value) {
		return (value == 2);
		});
	// key를 찾는게 아닌 조건을 만족하는 것을 찾아야 하기 때문에 전체를 순회해야함
    // 그렇기 때문에 시간복잡도 O(n)
	set<int> s{ 1, 2, 3 };

	if (iter != v.end())
		cout << *iter << endl;

	auto iter1 = s.find(2);

	if (iter1 != s.end())
		cout << *iter1;
	
}

실행 결과

2
2

remove, remove_if

• std::remove(Iter first, Iter last, const T& value)
value를 제외한 원소들을 앞으로 이동시킨다.
• std::remove_if(Iter first, Iter last, Functor pred)
pred의 조건에 맞는 원소를 제외한 원소들을 앞으로 이동시킨다.

두 함수는 상기한 동작을 수행 후 그 다음의 iterator를 반환한다.

remove는 실제 Container의 원소를 제거할 수 없고 앞으로 이동시키는 연산만 수행한다.
그렇기 때문에 실제로 제거하기 위해서는 erase를 같이 써줘야 한다.

erase

<container>.erase(Iter pos)
pos가 가리키는 iterator를 삭제한다.
<container>.erase(Iter first, Iter last)
first부터 last까지 삭제한다.

vector, set등이 가지고 있는 멤버 함수로 실제 container의 원소들을 제거한다.

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

using namespace std;

int main() {
	vector<int> v{ 1, 2, 3, 4, 3, 2, 1 };
	auto iter = remove(v.begin(), v.end(), 2);

	for (auto num : v)
		cout << num << ' ';
	cout << endl;
	cout << "remove_iter : " << *iter << endl;

	v.erase(iter, v.end());

	for (auto num : v)
		cout << num << ' ';
}

실행 결과

1 3 4 3 1 2 1
remove_iter : 2
1 3 4 3 1

remove가 반환한 iter가 가리키는 2부터 v.end()가 가리키는 1까지 erase가 삭제 작업을 수행하였다.

copy

std::copy(Iter first, Iter last, const T& <dest container>)
first와 last까지 dest container로 복사한다.