원소를 수정하는 알고리즘은 원소의 값을 변경하거나 목적지 순차열로 원소를 복사하는 알고리즘이다.

copy()

copy() 알고리즘은 순차열에서 다른 순차열로 원소를 복사해야 할 때 사용한다.copy(b,e,t)는 구간 [b,e)의 순차열을 구간 [t,t+(e-b))의 순차열로 모두 복사한다. 여기서 주목할 점은 복사 동작을 수행 할 때 두 가지 모드의 복사 동작이 있는데 하나는 덮어쓰기, 하나는 삽입 모드이다. 모든 알고리즘의 기본 동작은 덮어쓰기 모드로 동작하며 반복자 어댑터등을 사용하여 삽입 모드로 동작하게 할 수 있다.

copy()의 예시를 보자.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

	//size가 5인 vector 생성
	vector<int> v2(5);

	vector<int>::iterator iter;

	//구간 [v.begin(),v.end())의 모든 원소를 [v2.begin(),iter)의 순차열로 복사
	iter = copy(v.begin(), v.end(), v2.begin());
	cout << "v2의 마지막 원소 " << *(iter - 1) << endl;

	cout << "v : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << endl;
	cout << "v2 : ";
	for (vector<int>::size_type i = 0; i < v2.size(); i++) {
		cout << v2[i] << " ";
	}
	cout << endl;
}

여기서 확인이 되는 사실은 우선 copy()알고리즘은 목적지 순차열의 끝 반복자를 반환한다는 것이다. 즉, copy(v.begin(), v.end(), v2.begin());는 구간 [v.begin(),v.end())의 모든 원소를 [v2.begin(),v2.begin()+(v.end()-v.begin())의 순차열로 복사하는데 목적지 순차열의 끝 반복자를 반환하니 목적지 순차열은 [v2.begin(),iter)가 된다. 그리고 이 알고리즘은 덮어쓰기로 동작하기 때문에 목적지 순차열의 원소의 갯수가 원본 순차열의 원소의 갯수 이상이 되어야 한다.

copy_backward()

copy_backward()는 원소의 복사를 순차열의 마지막 원소부터 복사하고자 할 때 사용한다. copy_backward(b,e,t)는 구간 [b,e)의 모든 원소를 [t-(e-b), t)의 순차열로 마지막 원소부터 복사한다. 예시를 보자.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

	//size가 10인 vector 생성
	vector<int> v2(10);

	vector<int>::iterator iter;

	//구간 [v.begin(),v.end())의 모든 원소를 [iter,v2.end())의 순차열로 복사
	iter = copy_backward(v.begin(), v.end(), v2.end());
	cout << "v2의 첫 원소 " << *iter << endl;

	cout << "v : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << endl;
	cout << "v2 : ";
	for (vector<int>::size_type i = 0; i < v2.size(); i++) {
		cout << v2[i] << " ";
	}
	cout << endl;
}

iter = copy_backward(v.begin(), v.end(), v2.end()); : 구간 [v.begin(),v.end())의 순차열을 [v2.end()-(v.end(),v.begin()),v2.end())의 순차열로 마지막 원소부터 복사한다. copy_backward()알고리즘은 목적지 시작 반복자를 반환하므로 목적지 순차열은 [iter,v2.end())가 된다.

fill() , fill_n()

순차열을 특정 값으로 채우고 싶을 때 사용하는 알고리즘들이다. fill(b,e,x)는 구간 [b,e)의 원소를 x로 채우고, fill_n(b,n,x)는 구간 [b,b+n)의 원소를 x로 채운다. 예시를 보자.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

	//구간 [v.begin(),v.end())의 모든 원소를 0으로 채운다.
	fill(v.begin(), v.end(), 0);
	cout << "v : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << endl;
	//구간 [v.begin(),v.begin()+3)의 모든 원소를 55으로 채운다.
	fill_n(v.begin(), 3, 55);
	cout << "v : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
}

for_each()

for_each()알고리즘은 원소를 수정하는 알고리즘으로도 사용된다. for_each(b,e,f)는 구간 [b,e)의 반복자가 p라면 모든 원소에 f(*p)를 적용한다. 여기서 중요한건 for_each()를 원소를 수정하는 알고리즘으로 사용할 때에는 f로 사용되는 함수자의 매개변수가 참조형이어야 한다. 예시를 보자.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

//출력 매개변수로 사용하기 위해 & 사용
void Func(int& n) {
	n += 5;
}

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

	cout << "v : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << endl;

	for_each(v.begin(), v.end(), Func);
	cout << "v : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
}

여기서 중요한 점은 사용자 저의 함수의 매개변수가 출력 매개변수로 사용하기 위해 &를 사용했다는 것이다.

for_each()에 함수객체 사용

for_each()알고리즘에 함수객체를 사용하게 되면 함수객체는 샅애 변수를 가질 수 있으므로 함수를 사용하는 것보다 더 다양한 작업을 수행할 수 있다.

예시를 보자.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Accumulation {
	int total;
public:
	explicit Accumulation(int init=0) : total(init) { }
	void operator() (int& r) {
		total += r;
		r = total;
	}
};

void main() {
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);
	// v의 모습 1 2 3 4 5

	cout << "v : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << endl;

	//구간 [v.begin(),v.end())의 모든 원소를 초깃값 0부터 시작해 *p += *(p-1)를 적용
	for_each(v.begin(), v.end(), Accumulation(0));
	cout << "v : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
}

직관적이므로 설명은 생략한다.

generate() , generate_n()

순차열의 모든 원소를 단순한 동작의 값으로 수정하고자 할 때 사용한다. generate(b,e,f) 알고리즘은 구간 [b,e)의 모든 원소를 f()로 채운다. generate(b,n,f) 알고리즘은 구간 [b,b+n)의 모든 원소를 f()로 채운다. 예시를 보자.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Integer {
	int data;
public:
	explicit Integer(int d = 0) : data(d) { }
	int operator()() {
		return data++;
	}
};

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

	cout << "v : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << endl;

	//[v.begin(),v.end())의 원소를 1~5로 채움
	generate(v.begin(), v.end(), Integer(1));
	cout << "v : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << endl;

	//[v.begin(),v.end())의 원소를 100~104로 채움
	generate(v.begin(), v.end(), Integer(100));
	cout << "v : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << endl;

	//[v.begin(),v.begin()+3)의 원소를 1~3로 채움
	generate_n(v.begin(),3, Integer(1));
	cout << "v : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << endl;
}

직관적이므로 위 코드에 대한 설명은 넘어간다.

generate()알고리즘과 for_each()가 다른점은 generate()알고리즘은 순차열의 원소값을 매개변수로 전달받지 않기 때문에 원본의 값을 활용하는 것이 아닌 단순히 일정한 값으로 채운다는 것이다.

swap() , iter_swap()

단순히 값을 교환하거나 반복자가 가리키는 값을 교환하고자 할 때 사용한다.

swap(a,b)는 a와b를 교환하고, swap(p,q)는 *p와 *q를 교환한다. 예시를 보자

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void main() {
	int a = 10, b = 20;

	vector<int> v;
	v.push_back(10);
	v.push_back(20);
	// v의 모습 10 20

	cout << "a : " << a << ", " << "b : " << b << endl;
	swap(a, b);
	cout << "a : " << a << ", " << "b : " << b << endl;

	vector<int>::iterator p = v.begin();
	vector<int>::iterator q = v.begin()+1;

	cout << "v[0] : " << v[0] << ", " << "v[1] : " << v[1] << endl;
	iter_swap(p, q);
	cout << "v[0] : " << v[0] << ", " << "v[1] : " << v[1] << endl;
}

직관적이므로 설명은 생략한다.

merge()

이 알고리즘은 두 순차열을 하나의 정렬된 순차열로 합병할 때 사용한다.

merge(b,e,b2,e2,t)는 구간[b,e)의 순차열과 구간 [b2,e2)의 순차열을 [t,t+(e-b)+(e2-b2))의 순차열로 합병 정렬한다. 예시를 보자

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void main() {
	int a = 10, b = 20;

	vector<int> v1;
	v1.push_back(10);
	v1.push_back(30);
	v1.push_back(50);
	v1.push_back(60);
	v1.push_back(80);
	// v1의 모습 10 30 50 60 80

	vector<int> v2;
	v2.push_back(20);
	v2.push_back(40);
	v2.push_back(70);
	// v2의 모습 20 40 70

	//size가 10인 vector 생성
	vector<int> v3(10);

	vector<int>::iterator iter_end;
	iter_end = merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());

	cout << "v1 : ";
	for (vector<int>::size_type i = 0; i < v1.size(); i++) {
		cout << v1[i] << " ";
	}
	cout << endl;

	cout << "v2 : ";
	for (vector<int>::size_type i = 0; i < v2.size(); i++) {
		cout << v2[i] << " ";
	}
	cout << endl;

	cout << "v3 : ";
	for (vector<int>::size_type i = 0; i < v3.size(); i++) {
		cout << v3[i] << " ";
	}
	cout << endl;

	cout << "v3(합병 순차열)" << *v3.begin() << '~' << *(iter_end - 1) << endl;
}

iter_end = merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin()); :

구간 [v1.begin(),v1.end())의 순차열과 구간 [v2.begin(),v2.end())의 순차열을 합병 정렬하여 구간 [v3.begin(),v3.begin()+(v1.end()-v1.begin())+(v2.end()-v2.begin()))에 합병 정렬한다. 이때 merge()는 끝 반복자를 반환하므로 목적지 순차열은 [v3.begin(),iter)이 된다.

주의) merge()는 정렬된 구간에서만 동작한다. 즉, 합병 할 두 순차열이 정렬되어 있어야 한다.

조건자 버전 merge()

두 순차열이 특정 정렬 기준에 의해 정렬된 상태라면 merge(b,e,b2,e2,t,f)를 사용한다. 일반 버전의 merge()는 기본적으로 less(오름차순)을 전제로 하기 때문에 합병 할 두 순차열이 greater(내림차순)으로 정렬되어 있다면 조건자 버전 merge()를 사용해야 한다. 예시를 보자.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

template <typename T>
class Greater {
public:
	bool operator() (const T& left, const T& right) const {
		return left > right;
	}
};

void main() {
	int a = 10, b = 20;

	vector<int> v1;
	v1.push_back(80);
	v1.push_back(60);
	v1.push_back(50);
	v1.push_back(30);
	v1.push_back(10);
	// v1의 모습 80 60 50 30 10

	vector<int> v2;
	v2.push_back(70);
	v2.push_back(40);
	v2.push_back(20);
	// v2의 모습 70 40 20

	//size가 10인 vector 생성
	vector<int> v3(10);

	vector<int>::iterator iter_end;
	//STL greater 사용
	//iter_end = merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin(),greater<int>());
	iter_end = merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin(),Greater<int>());

	cout << "v1 : ";
	for (vector<int>::size_type i = 0; i < v1.size(); i++) {
		cout << v1[i] << " ";
	}
	cout << endl;

	cout << "v2 : ";
	for (vector<int>::size_type i = 0; i < v2.size(); i++) {
		cout << v2[i] << " ";
	}
	cout << endl;

	cout << "v3 : ";
	for (vector<int>::size_type i = 0; i < v3.size(); i++) {
		cout << v3[i] << " ";
	}
	cout << endl;

	cout << "v3(합병 순차열)" << *v3.begin() << '~' << *(iter_end - 1) << endl;
}

[STL] 원소를 수정하는 알고리즘 (1)

copy()

copy_backward()

fill() , fill_n()

for_each()

for_each()에 함수객체 사용

generate() , generate_n()

swap() , iter_swap()

merge()

조건자 버전 merge()

KSC

copy()

copy_backward()

fill() , fill_n()

for_each()

for_each()에 함수객체 사용

generate() , generate_n()

swap() , iter_swap()

merge()

조건자 버전 merge()

Share this post