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

원소를 수정하지 않는 알고리즘은 원소의 순서나 원소의 값을 변경하지 않고 원소를 읽기만 하는 알고리즘이다.

1. adjacent_find()
   adjacent_find() 알고리즘의 예제로 vector의 순차열에서 현재 원소와 다음 원소가 같아지는 첫 원소의 반복자를 반환한다.

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

using namespace std;

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

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

	begIter = v.begin();
	vector<int>::iterator iter = adjacent_find(begIter, endIter);
	if (v.end() != iter) { cout << *iter << endl; }

	while (iter != endIter)
	{
		cout << *iter << ' ';
		++iter;
	}

	return 0;
}

vector::iterator iter = adjacent_find(begIter, endIter)에 시작과 끝 반복자를 인자에 넣어주면 현재 원소와 다음 원소가 같아지는 첫 원소의 반복자를 반환한다. 즉 30의 첫 원소를 반환한다. 찾기 관련 알고리즘은 찾는 원소를 발견하지 못하면 찾는 구간의 끝 반복자를 반환한다.

2. adjacent_find() 특정 조건
   adjacent_find()는 디폴트로 값이 같은 원소의 첫 반복자를 반환하지만 조건을 넣을 수도 있다. 아래 예제를 먼저 보겠다.

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

using namespace std;

bool Pred(int op1, int op2)
{
    return abs(op1 - op2) > 10;
}

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

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

    begIter = v.begin();
    vector<int>::iterator iter = adjacent_find(begIter, endIter, Pred);
    if (endIter != iter) { cout << "첫 원소: " << *iter << " -> 다음 원소: " << *(iter + 1) << endl; }
    else { cout << "없음." << endl; }

    return 0;
}

adjacent_find() 함수의 3번째 인자에 함수 포인터를 넣으면 된다. 여기선 b-a 차이가 10 이상 나면 true이고 10,20에서는 false, 20,80에서는 true이므로 iter에는 20을 가키는 반복자를 반환한다.

3. count(), count_if()
   순차열에서 원소의 개수를 구하려면 간단하게 count() 알고리즘을 사용한다. count는 이전에도 다뤘고 너무 간단하므로 count_if()에 대해 적어보려고한다. 조건자 버전의 count_if(b,e,f) 알고리즘을 사용하여 조건에 맞는 원소의 개수를 구할 수 있다. f는 단항 조건자로 원소를 가리키는 반복자 p에 대해 f(*p)가 참인 원소의 개수를 반환한다. 아래는 count_if()의 예제이다.

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

using namespace std;

bool Pred(int op)
{
    return 25 < op;
}

int main(void)
{
    vector<int> v;
    v.push_back(10);
    v.push_back(25);
    v.push_back(30);
    v.push_back(30);
    v.push_back(40);
    v.push_back(40);
    v.push_back(50);

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

    size_t uCount = count_if(v.begin(), v.end(), Pred);
    cout << "25 초과인 원소의 개수: " << uCount << endl;

    return 0;
}

4. equal(), 조건자 equal()
   equal() 알고리즘을 사용하여 두 순차열의 원소가 모두 같은지 판단할 수 있다. 두 개의 순차열을 필요로하는 대부분의 알고리즘은 두 순차열의 길이가 같을 떄 동작하므로 첫 번째 순차열은 구간을 필요로하지만 두 번째 순차열은 시작 반복자만 필요하다.아래는 equal() 예제이다.

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

using namespace std;

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

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

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

    vector<int>::iterator begIter2 = v2.begin();
    vector<int>::iterator endIter2 = v2.end();
    while (begIter2 != endIter2)
    {
        cout << *begIter2 << ' ';
        ++begIter2;
    }
    cout << endl;

    begIter1 = v1.begin();
    begIter2 = v2.begin();
    if (equal(begIter1, endIter1, begIter2)) { cout << "두 순차열은 같다." << endl; }
    else { cout << "두 순차열은 다르다." << endl; }

    return 0;
}

여기서 v1의 길이가 3이므로 v2.begin()+3의 순차열을 비교한다.

아래는 조건자 버전 equal()알고리즘 예제이다

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

using namespace std;

bool Pred(int nLeft, int nRight) { return abs(nLeft - nRight) < 5; }

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

	vector<int> v2;
	v2.push_back(13);
	v2.push_back(23);
	v2.push_back(33);

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

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

	begIter = v1.begin();
	endIter = v1.end();
	if (true == equal(begIter, endIter, v2.begin(), Pred))
	{
		cout << "두 순차열은 같다." << endl;
	}

	return 0;
}

모든 원소가 Pred 함수에서 참이면 참을 반환한다.