[A Tour of C++] Chapter 12. Algorithms

이 글은 <A Tour of C++ Second Edition, Bjarne Stroustrup>를 참고하여 작성하였습니다.

 

[A Tour of C++] Chapter 12. Algorithms

C++ 표준 라이브러리에서 제공하는 알고리즘은 컨테이너와 함께 사용하여 데이터 처리와 변형을 효율적으로 수행할 수 있도록 돕습니다. 이번 포스트에서는 C++ 표준 라이브러리의 알고리즘과 반복자, 그리고 알고리즘의 다양한 활용 방법에 대해 살펴보겠습니다.

 

12.2. Iterators

반복자란?

컨테이너나 다른 데이터 구조의 요소들에 대한 순차적인 접근을 제공하는 객체(e.g. begin(), end())

 

1. 많은 알고리즘이 반복자를 사용한다.

예시: find - 주어진 시퀀스에서 값을 찾고 찾아낸 요소를 가리키는 반복자를 반환한다

auto p = find(s.begin(), s.end(), c);

 

2. 반복자를 이용하면, 알고리즘과 컨테이너를 분리할 수 있다.

template<typename C, typename V>
vector<typename C::iterator> find_all(C&c, V v)
{
	// ...
}

• 알고리즘은 반복자를 이용해서 데이터에 적용되기 때문에 컨테이너를 몰라도 되고,
• 컨테이너도 요소에 적용되는 알고리즘에 대해 아무것도 모른다

 

12.3 Iterator Type

반복자는 어떻게 구현되어 있나?

반복자는 일반적으로 두 가지 방식으로 구현됩니다:

1. 포인터 기반 반복자: 메모리 주소를 직접 사용하는 방식
2. 포인터 + 인덱스: 포인터와 인덱스를 결합하여 요소를 접근

 

const_iterator

const_iterator는 요소를 읽을 수만 있고 수정할 수는 없는 반복자입니다.

std::vector<int>::const_iterator cit = vec.cbegin();

 

12.4  Stream Iterators

값의 시퀀스를 만들어내는 stream에도 아래 목적을 위해 반복자를 사용할 수 있습니다.

• stream의 요소를 차례로 읽거나
• stream에 요소를 차례로 쓰기 위해

// 파일을 읽고, 읽은 단어의 중복된 값을 제거한 후, 결과를 다른 파일에 쓰는 연산
int main() {
	string from, to; // 파일명
	cin >> from >> to;

	ifstream is {from};
	ofstream os {to};
	
	// 스트림 속 각 요소를 읽어 set으로 담거나
	istream_iterator<string> is_start{is}
	istream_iterator<string> is_end{};
	set<string> b {is_start, is_end};
	
	// 출력된 시퀀스들을 다시 stream에 쓰거나
	copy(b.begin(),b.end(), ostream_iterator<string>{os,"\n"});

	return !is.eof() || !os;
}

 

12.5 Predicates

Predicates란?

주로 조건을 평가하여 참 또는 거짓으로 반환하는 함수나 함수 객체를 가리키는 용어입니다. 예를 들면,  std::find_if, std::remove_if와 같은 알고리즘 함수들은 조건을 만족하는 원소들만을 대상으로 연산을 수행하기 위해 predicate를 사용합니다.

auto p = find_if(m.begin(), m.end(), [](const auto& r) { 
	return r.second>42; 
});

 

12.9 Parallel Algorithms

C++17부터는 병렬 알고리즘을 지원합니다. 병렬 실행을 통해 대량의 데이터를 더 빠르게 처리할 수 있습니다. std::sort와 같은 알고리즘은 다음과 같이 병렬로 실행할 수 있습니다:

• 순차 실행: std::sort(v.begin(), v.end());
• 병렬 실행: std::sort(std::execution::par, v.begin(), v.end());
• 병렬 또는 벡터화: std::sort(std::execution::par_unseq, v.begin(), v.end());

병렬 알고리즘은 멀티스레드를 활용하여 성능을 개선하며, 벡터화는 단일 스레드에서 SIMD 명령어를 사용하여 성능을 높입니다.