알고리즘 - 원소를 수정하지 않는 알고리즘(2)

find()는 특정 원소를 찾는 알고리즘이며, find_if()는 조건에 따라 원소를 찾는 알고리즘이다. 아래는 find()와 find_if()의 예제이다.

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

using namespace std;

bool Pred(int nOperand) { return 35 < nOperand; }

int main()
{
    vector<int> v1;
    v1.push_back(10);
    v1.push_back(20);
    v1.push_back(30);
    v1.push_back(40);
    v1.push_back(50);

    vector<int>::iterator begIter = v1.begin();
    vector<int>::iterator endIter = v1.end();
    while (begIter != endIter)
    {
        cout << *begIter << ' ';
        ++begIter;
    }
    cout << endl;

    begIter = v1.begin();
    vector<int>::iterator iter = find(begIter, endIter, 20);
    if (endIter != iter) { cout << *iter << " has been found." << endl; }

    begIter = v1.begin();
    iter = find_if(begIter, endIter, Pred);
    if (endIter != iter) { cout << *iter << " is bigger than 35." << endl; }

    return 0;
}

find(begIter, endIter, 20)는 iter 구간에서 20값을 찾는 첫 원소의 반복자이다.
find_if(begIter, endIter, Pred)는 iter 구간에서 단항 조건자 pred가 참인 첫 원소의 반복자이다.

순차열 하나에 포함하는 다른 순차열이 있는지 찾아야 한다면 find_end()와 search() 알고리즘을 사용한다. find_end()는 일치하는 순차열이 여래 개라면 마지막 순차열의 반복자를 반환하며 search()는 첫 번째 순차열의 반복자를 반환한다. 아래는 find_end()의 예제이다.

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

using namespace std;

int main()
{
    vector<int> v1;
    v1.push_back(10);
    v1.push_back(20);
    v1.push_back(30);
    v1.push_back(40);
    v1.push_back(50);
    v1.push_back(60);
    v1.push_back(70);
    v1.push_back(30);
    v1.push_back(40);
    v1.push_back(50);

    vector<int> v2;
    v2.push_back(30);
    v2.push_back(40);
    v2.push_back(50);

    vector<int>::iterator begIter = v1.begin();
    vector<int>::iterator endIter = v1.end();
    while (begIter != endIter)
    {
        cout << *begIter << ' ';
        ++begIter;
    }
    cout << endl;

    begIter = v2.begin();
    endIter = v2.end();
    while (begIter != endIter)
    {
        cout << *begIter << ' ';
        ++begIter;
    }
    cout << endl;

    vector<int>::iterator iter = find_end(v1.begin(), v1.end(), v2.begin(), v2.end()) - 1;
    int nOffset = -1;

    while (v1.end() != iter)
    {
        cout << "*(iter " << nOffset++ << ") == " << *iter << endl;
        ++iter;
    }

    return 0;
}

find_end(v1.begin(), v1.end(), v2.begin(), v2.end()) : 구간 v1의 순차열에 구간 v2의 순차열이 일치하는지 판단하여 일치하는 순차열 구간이 여러 개라면 마지막 순차열의 첫 원소 반복자를 반환한다.
그래서 *(iter - 1)은 70이 출력되는 것이다.

find_end()에서도 조건자 버전을 사용하면 원소의 비교를 사용자가 결정할 수 있다. 아래는 조건자 버전의 find_end()이다.

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

using namespace std;

bool Pred(int nLeft, int nRight) { return nLeft <= nRight; }

int main()
{
	vector<int> v1;
	v1.push_back(10);
	v1.push_back(15);
	v1.push_back(20);
	v1.push_back(40);
	v1.push_back(50);
	v1.push_back(60);
	v1.push_back(10);
	v1.push_back(11);
	v1.push_back(12);
	v1.push_back(80);

	vector<int> v2;
	v2.push_back(10);
	v2.push_back(15);
	v2.push_back(25);

	vector<int>::iterator begIter = v1.begin();
	vector<int>::iterator endIter = v1.end();
	while (begIter != endIter)
	{
		cout << *begIter << ' ';
		++begIter;
	}
	cout << endl;

	begIter = v2.begin();
	endIter = v2.end();
	while (begIter != endIter)
	{
		cout << *begIter << ' ';
		++begIter;
	}
	cout << endl;

	vector<int>::iterator iter = find_end(v1.begin(), v1.end(), v2.begin(), v2.end(), Pred) - 1;
	int nOffset = -1;

	while (v1.end() != iter)
	{
		cout << "*(iter " << nOffset++ << ") == " << *iter << endl;
		++iter;
	}

	return 0;
}

ind_end(v1.begin(), v1.end(), v2.begin(), v2.end(), Pred) : v2 순차열 구간이 v1 순차열 구간보다 모두 크거나 같은 구간의 첫 원소를 반환하기 때문에 iter는 10 , (iter -1)은 60이다.

find_first_of() 알고리즘은 두 순차열을 비교하여 모든 원소 중 같은 원소가 하나라도 발견되면 첫 원소의 반복자를 반환한다. 다음은 find_first_of() 알고리즘의 예제이다.

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

using namespace std;

int main()
{
	vector<int> v1;
	v1.push_back(10);
	v1.push_back(15);
	v1.push_back(20);
	v1.push_back(40);
	v1.push_back(50);
	v1.push_back(60);
	v1.push_back(10);
	v1.push_back(11);
	v1.push_back(12);
	v1.push_back(80);

	vector<int> v2;
	v2.push_back(11);
	v2.push_back(20);
	v2.push_back(60);

	vector<int>::iterator begIter = v1.begin();
	vector<int>::iterator endIter = v1.end();
	while (begIter != endIter)
	{
		cout << *begIter << ' ';
		++begIter;
	}
	cout << endl;

	begIter = v2.begin();
	endIter = v2.end();
	while (begIter != endIter)
	{
		cout << *begIter << ' ';
		++begIter;
	}
	cout << endl;

	vector<int>::iterator iter = find_first_of(v1.begin(), v1.end(), v2.begin(), v2.end());
	if (v1.end() != iter) { cout << "*iter == " << *(iter-1) << endl; }

	return 0;
}

• iter = find_first_of() : v1 순차열에서 v2 순차열 원소가 첫 번째로 발견되는 위치는 20이므로 20의 반복자를 반환한다. *(iter-1)은 15이다.