[STL] 알고리즘 Algorithm

알고리즘

컨테이너에서 특정 원소나 위치를 삽입, 삭제, 수정 하기 위한 로직
대부분 알고리즘은 순방향 반복자를 요구하지만, 몇가지 알고리즘은 임의 접근 반복자를 요구합니다.

 

STL의 7가지 알고리즘 범주

1. 원소를 수정하지 않는 알고리즘
2. 원소를 수정하는 알고리즘
3. 제거 알고리즘
4. 변경 알고리즘
5. 정렬 알고리즘
6. 정렬된 범위 알고리즘
7. 수치 알고리즘

 

---

find 알고리즘

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

using namespace std;

int main() {
	vector<int> v;

	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(40);
	v.push_back(50);

	vector<int>::iterator iter;
	iter = find(v.begin(), v.end(), 20); // 벡터 v에서 20인 값 찾기.
	cout << *iter << endl;

	iter = find(v.begin(), v.end(), 100);
	if (iter == v.end()) { //find로 못찾을경우 end()값을 가리킨다.
		cout << "찾는 값이 없습니다." << endl;
	}

	return 0;
}

 

 

Find 함수 들어가보기

 

find는 템플릿으로 구현되어 클래스 2가지를 받고 있고

InIt 으로 First(시작지점)와 Last(끝지점) 매개변수를 받고,

_Ty로 찾을 값을 받는 것을 볼 수 있습니다.

 

그래서 find 사용시 find(v.begin(), v.end(), 찾을값) 으로 하여 사용합니다.

만약 find로 값을 찾지 못하면 find는 Last의 지점을 가리켜 반환합니다.

 

---

 

Vector와 List 컨테이너의 반복자와 sort 알고리즘

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

using namespace std;

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

	list<int> lt;
	lt.push_back(10);
	lt.push_back(20);
	lt.push_back(30);
	lt.push_back(40);
	lt.push_back(50);

	sort(v.begin(), v.end());
	/*
	랜덤 액세스 이터레이터(Random Access Iterator)
	-> 임의의 위치에서 O(1) 시간 안에 접근할 수 있는 반복자를 의미. 즉 배열처럼 메모리에서 연속적인 저장 구조를 가지는 컨테이너에서 지원됨.
	sort(T.begin(), T.end(), findValue)는 랜덤 액세스 반복자를 지원함.
	*/
	//sort(lt.begin(), v.end()); 양방향 반복자라서 에러
	//리스트를 정렬하려면 lt.sort()를 해야함.

	return 0;
}

 

 

 

Sort 코드

 

 

Sort 역시 find과 같이 템플릿으로 만들어졌습니다,

매개변수를 보면 템플릿 클래스 1개를 받아 First(시작지점)과 Last(끝지점)을 받아오고,

정렬 수행시 Less<>로 디폴트가 오름차순으로 정렬되도록 되어 있습니다.

 

근데 Vector는 되는데 List는 이 Sort를 못씁니다.

 

템플릿 함수를 보면 RndIt이라 클래스 명이 적혀있는데

이는 Random Access Iterator로 랜덤(임의) 접근 반복자만을 취급하기 때문입니다.

 

랜덤 액세스 반복자: 임의의 위치에서 O(1) 시간 안에 접근 할 수 있는 반복자

 

List는 양방향 반복자만 제공하기 때문에 저 sort를 못쓰고 정렬 하려면 리스트의 멤버함수인 Lt.sort( )로 해야합니다.