23.02.24 - 반복자, 알고리즘

반복자

1.출력 반복자 2.입력 반복자 3.순방향 반복자 4.양방향 반복자 5.임의 접근 반복자 가 있다.

읽기 가능        쓰기가능          ++가능               --도 가능            +,-,[] 도 가능 

보면 알겠지만 오른쪽으로 갈 수록 기능이 증가한다.

우리가 실제로 많이 사용하는 것은 대부분 양방향 반복자와 임의 접근 반복자이다.

노드 기반 컨테이너 (list,set,map)이 양방향 반복자가 사용 가능하고

배열 기반 컨테이너 (vector, deque)는 임의 접근 반복자가 사용 가능하기 때문이다.

 

 

 

알고리즘

일반화된 기능을 전역 네임스페이스로 선언해 제공하는 함수 템플릿 헤더이다. 

대부분 첫번째, 두번째 인자로 반복자, 세번째 인자로 조건자를 넣는다.

bool 	Greater(int a,int b)
{
	return a > b;
}
template<typename T>
bool	Greater(T a, T b)
{
	return a > b;
}
struct Greater
{
	bool operator(int a,int b)
    {
	     return a > b;
    }
}
...
sort(vec.begin(),vec.end(),Greater); //함수
sort(vec.begin(),vec.end(),Greater<int>); //템플릿
sort(vec.begin(),vec.end(),Greater()) //함수 객체

sort는 정렬을 해주는 알고리즘인데  오름차순 정렬을 하기 위해 조건자에 Greater 함수, 템플릿, 함수 객체를 넣을 수 있다.

greater<자료형>()는 기본적으로 functional헤더에서 지원하는 조건자이기 때문에 일부러 이름을 Greater로 했다.

 

int	iResult = count_if(vecInt.begin(), vecInt.end(), OddFunctor());

for_each(vecPtr.begin(), vecPtr.end(), DeleteHeap());

sort외에 자주 사용되는 알고리즘에는 count_if와 for_each가 있다.

count_if는 조건자가 true를 반환하는 개수를 세고, for_each는 컨테이너를 순회하며 모든 원소에 함수를 실행시킨다.

위 코드는 홀수일 때 true를 반환하는 함수 객체 OddFunctor을 조건자로 넣어 홀수가 컨테이너에 몇개인지 세고,

컨테이너를 순회하며 DeleteHeap() 함수 객체로 컨테이너를 할당 해제하기 전에 원소먼저 할당 해제하는 예시이다.

for루프를 써서 순회하며 함수를 실행하는 것보다 for_each를 쓰는 것이 속도가 더 빠르다고 한다.