[STL] algorithm

algorithm이란?

STL 컨테이너는 자료구조(데이터를 저장하는 구조)를 의미하고

vector, list, deque, map, set 등이 있었다

STL 알고리즘은 데이터를 어떻게 사용할지에 대한 부분을 의미하고

대표적인 알고리즘은 아래와 같다

#include <algorithm>
using namespace std;

find(InputIterator first, InputIterator last, const T& value);
find_if(InputIterator first, InputIterator last, UnaryPredicate pred);
count(InputIterator first, InputIterator last, const T& value);
count_if(InputIterator first, InputIterator last, UnaryPredicate pred);
all_of(InputIterator first, InputIterator last, UnaryPredicate pred);
any_of(InputIterator first, InputIterator last, UnaryPredicate pred);
none_of(InputIterator first, InputIterator last, UnaryPredicate pred);
for_each(InputIterator first, InputIterator last, Function f);
remove(ForwardIterator first, ForwardIterator last, const T& value);
remove_if(ForwardIterator first, ForwardIterator last, UnaryPredicate pred);

 

 

algorithm 없이 구현이 가능한가?

algorithm 없이 코드를 작성할 수 있긴 하다

하지만,

가독성 떨어지고

특정 컨테이너(ex. vector)에 대한 의존도가 높은 문제가 있다

 

따라서,

STL의 algorithm을 사용하면

위의 문제를 쉽게 해결할 수 있다

 

아래 예시들은

algorithm을 사용하지 않은 버전과

algorithm을 사용한 버전을 동시에 보여준다

#include <iostream>
#include <vector>
#include <list>
#include <deque>
#include <map>
#include <set>
#include <algorithm>

using namespace std;

int main()
{
	srand(static_cast<unsigned int>(time(nullptr)));
	vector<int> v;

	for (int i = 0; i < 100; i++)
	{
		int num = rand() % 100;
		v.push_back(num);
	}


	// Q1) number라는 숫자가 벡터에 있는지 체크하는 기능 구현
	{
		// algorithm 사용하지 않는 버전
		// bool 혹은 처음 등장하는 iterator를 받아서 체크할 수 있다
		int number = 50;
		bool found = false;
		vector<int>::iterator it;//있으면 해당 iterator, 없으면 vector_end

		for (unsigned int i = 0; i < v.size(); i++)
		{
			int data = v[i];
			if (data == number)
			{
				found = true;
				it = v.begin() + i;
				break;
			}
		}


		// algorithm 사용한 버전
		vector<int>::iterator itFind = std::find(v.begin(), v.end(), number);
		if (itFind == v.end())
		{
			cout << "못찾음" << endl;
		}
		else
		{
			cout << "찾음" << endl;
		}
		//vector뿐 아니라 다른 컨테이너도 가능

	}

	// Q2) 11로 나뉘는 숫자가 벡터에 있는지 체크하는 기능 (bool or 첫등장 iterator)
	{
		// algorithm 사용하지 않는 버전
		bool found = false;
		vector<int>::iterator it;

		for (unsigned int i = 0; i < v.size(); i++)
		{
			int data = v[i];
			if ((data % 11) == 0)
			{
				found = true;
				it = v.begin() + i;
				break;
			}
		}


		// algorithm 사용한 버전
		struct CanDivideBy11
		{
			bool operator()(int n)
			{
				return (n % 11) == 0;
			}
		};//함수객체 버전

		vector<int>::iterator itFind = find_if(v.begin(), v.end(), CanDivideBy11());
		//vector<int>::iterator itFind = find_if(v.begin(), v.end(), [](int n) { return (n % 11) == 0; });// 람다 버전
		if (itFind == v.end())
		{
			cout << "못찾음" << endl;
		}
		else
		{
			cout << "찾음" << endl;
		}
	}

	// Q3) 홀수인 숫자의 개수 count에 뱉어주기
	{
		// algorithm 사용하지 않는 버전
		int count = 0;

		for (unsigned int i = 0; i < v.size(); i++)
		{
			int data = v[i];
			if ((data % 2) != 0)
			{
				count++;
			}
		}


		// algorithm 사용한 버전
		struct IsOdd
		{
			bool operator()(int n)
			{
				return (n % 2) != 0;
			}
		};

		int countif = count_if(v.begin(), v.end(), IsOdd());

		// 추가로 유용한 아이들
		bool b1 = all_of(v.begin(), v.end(), IsOdd());// 모든 데이터가 홀수입니까?
		bool b2 = any_of(v.begin(), v.end(), IsOdd());// 홀수인 데이터가 하나라도 있습니까?
		bool b3 = none_of(v.begin(), v.end(), IsOdd());// 모든 데이터가 홀수가 아닙니까?
	}

	// Q4) 벡터에 들어가 있는 모든 숫자들에 3을 곱해라
	{
		// algorithm 사용하지 않는 버전
		for (unsigned int i = 0; i < v.size(); i++)
		{
			int& data = v[i];
			data *= 3;

			// v[i] *= 3; 도 가능
		}


		// algorithm 사용한 버전
		// 이와 같은 경우 뿐아니라 단순히 모든 데이터를 순회할때도 사용 가능
		struct MultiplyBy3
		{
			void operator()(int& n)
			{
				n = n * 3;
			}
		};

		for_each(v.begin(), v.end(), MultiplyBy3());
	}
}

 

 

remove와 remove_if의 진실

remove와 remove_if는

이름과는 다르게 특정 데이터를 삭제해주지 않고

필요한 데이터를 앞으로 그거 정렬해서 덮어쓰기만 해주는 역할만 한다

그리고 반환하는 값은 필요하지 않은 데이터의 첫 위치이다

 

따라서

remove와 remove_if를 활용해서 데이터를 삭제하고 싶다면

반드시 erase와 함께 사용해야 한다

 

예를 들어,

아래 그림의 vector에서 3과 6이 remove 된다면

1번 과정을 거치고

삭제를 하고 싶다면, erase를 통해 2번 과정을 거쳐야 한다

 

remove의 내부 원리를 정리하면 아래 그림과 같다

 

예시 코드는 아래와 같다

#include <iostream>
#include <vector>
#include <list>
#include <deque>
#include <map>
#include <set>
#include <algorithm>

using namespace std;

int main()
{
	srand(static_cast<unsigned int>(time(nullptr)));
	vector<int> v;

	for (int i = 0; i < 100; i++)
	{
		int num = rand() % 100;
		v.push_back(num);
	}

	// remove와 remove_if 사용 예시
	// Q) 홀수인 데이터를 일괄 삭제
	{
		// algorithm 사용하지 않는 버전
		for (vector<int>::iterator it = v.begin(); it != v.end();)
		{
			if ((*it % 2) != 0)
				it = v.erase(it);// 반환되는 위치가 다음 데이터를 가리킨다
			else
				++it;
		}
		// 위처럼 하면 되지만 vector에서는 erase와 clear 사용할때 매우 조심해야함
		// erase를 하면 it가 사라지기에 반환하는 위치를 이용해야한다
		// clear를 하면 vector가 다 사라진다
		
		
		// algorithm 사용한 버전
		v.clear();
		v.push_back(1);
		v.push_back(4);
		v.push_back(3);
		v.push_back(5);
		v.push_back(8);
		v.push_back(2);

		struct IsOdd
		{
			bool operator()(int n)
			{
				return (n % 2) != 0;
			}
		};

		vector<int>::iterator it = remove_if(v.begin(), v.end(), IsOdd());

		// remove, remove_if를 사용하면,
		// 필요한 데이터를 앞으로 순서 재조정하고 
		// 필요없는 데이터들의 첫 위치를 return 해준다
		// ex. 1 4 3 5 8 2
		//     4 8 2 5 8 2
		//     4 8 2 iterator가 여기를 가리킴 -> 5 8 2
		// 이처럼 remove는 삭제 기능이 없다

		v.erase(it, v.end()); // erase를 반드시 작성해줘야 삭제한다

		// remove_if를 it자리에 넣어서 한번에 처리하는 방법
		// v.erase(remove_if(v.begin(), v.end(), IsOdd()), v.end());
	}
}