뇌를 자극하는 C++ STL 8장) 알고리즘_원소를 수정하지 않는 알고리즘

누워서 낮잠 좀 많이 자고 일어났다ㅎㅎ 오늘은 알고리즘 중에서 원소를 수정하지 않는 알고리즘에 대해 정리해보려고 한닷~!

 

(혹시 저작권에 문제가 있다면 수정하겠습니다!! 개인적인 공부용으로 정리함을 알려드립니당)

 

https://m.hanbit.co.kr/store/books/book_view.html?p_code=B5912645820

뇌를 자극하는 C++ STL

 

adjacent_find, count, equal, find, for_each, lexicographical_compare

max / min, mismatch, search, find_end

 

1. p = adjacent_find(b, e)

반복자 p는 구간 [b, e)에서 연속되는 원소가 있을 때 그 첫 원소를 가리키는 반복자로 찾는 원소를 발견하지 못하면 찾는 구간의 끝 반복자를 반환한다.(end()가 아닐 수 있음에 주의한다!)

 

2. n = count(v.b, v.e, m)

정수 n은 v의 구간 [b,e)에서 원소 m의 갯수를 카운트한다.

count_if를 이용하면 단항 조건자를 추가해서 원하는 원소의 갯수를 카운트할 수 있다.

//단항 연산자
bool Pred_1(int n){
	return n < 25}
//이항 연산자
bool Pred_2(int a, int b){
	return abs(b-a) > 10;
}

// vector v = {10, 20 , 30, 50, 90}이라고 가정

vector<int>::iterator iter;
iter = adjacent_find(v.begin(), v.end(), Pred);  // iter은 30을 가리킴
int n = count(v.begin(), v.end(), 30);           // n = 1
n = count_if(v.begin(), v.end(), Pred_1);        // n = 2

 

3. equal(v1.b, v1.e, v2.b)

equal함수는 bool의 값을 반환하며(True, False) v1의 [b,e) 구간과 v2의 [b, b + (v1.e - v1.b))구간을 비교한다. 

이항 조건자 Pred를 포함해서 equal(v1.b, v1.e, v2.b, Pred)와 같이 사용 가능하다.

 

4.p =  find(b, e, 찾고 싶은 원소)

반복자 p는 구간 [b, e)에서 찾고 싶은 원소의 첫번째 반복자를 나타내며, find_if를 이용해 단항 조건자를 추가할 수 있다. 

find_end(v1.b, v1. e, v2.b, v2.e) : v1의 [b, e) 속에 v2의 [b, e)가 포함될 경우 가장 마지막 반복자를 반환해준다.

find_first_of( v1.b, v1. e, v2.b, v2.e) : v1의 [b, e) 속에 v2의 [b, e) 속 원소 중 하나라도 포함될 경우 v1의 v2과 같은 원소를 반환한다. 

//v1 = {10, 20, 30, 40, 50, 60, 70, 30, 40, 50}
//v2 = {30, 40, 50}
bool Pred(int left, int right){
	return left <= right;}
    
iter = find_end(v1.begin(), v1.end(), v2.begin(), v2.end()); //iter : 뒤에서 세번째 30을 가리킴
iter = find_end(v1.begin(), v1.end(), v2.begin(), v2.end(), Pred); //iter : 뒤에서 세번째 30을 가리킴
iter = find_first_of(v1.begin(), v1.end(), v2.begin(), v2.end()); // iter : 앞에서 세번째 30을 가리킴
iter = find_first_of(v1.begin(), v1.end(), v2.begin(), v2.end(), Pred); // iter : 앞에서 세번째 30을 가리킴

 

5. for_each(b,e, f)

for_each()함수는 순차열의 모든 원소에 사용자 동작f를 적용하고자 사용한다. 

f에는 함수 뿐만 아니라 함수자도 사용할 수 있다. 

class PrintFunctor{
	char fmt;
public:
	explicit PrintFunctor(char c= ' ') : fmt(c) {}
    void operator()(int n) const{
    	cout << n << fmt;
    }
};

//v = {10, 20, 30, 40, 50}
for_each(v.begin(), v.end(), PrintFunctor()); // 원소 구분 ' '로
for_each(v.begin(), v.end(), PrintFunctor(',')); // 원소 구분 ','로
for_each(v.beign(), v.end(), PrintFunctor('\n')); // 원소 구분 '\n'로

 

6. lexicographical_compare(b, e, b2, e2)

순차열의 사전순 비교(기본 비교 less< )하여 bool(True, False)로 반환한다. 

이항 조건자를 사용할 수도 있다.

 

7. max(a, b), max(a, b, f), min(a, b), min(a, b, f)

max(a, b)는 a와 b를 비교해 값이 더 큰 원소를 반환한다.

max_element(b, e)는 [b, e) 중 가장 큰 원소의 반복자를 반환한다. 

 

8. mismatch(b, e, b2)

v의 [b, e)와 v2의 [b2, b2+ (e-b))구간을 비교해 원소가 다른 첫번째 반복자 쌍(v1.p, v2.q)를 반환한다. 

이항조건자를 이용해 이항조건자 조건에 맞지 않는 첫번재 반복자 쌍(v1.p, v2.q)를 반환할 수도 있다. 

 

9. search(b, e, b2, e2), find_end(b, e, b2, e2)

search()와 find_end() 모두 하나의 순차열에 여러 순차열이 일치하는지를 확인하는 함수이지만 일치하는 순차열이 여러 개라면 find_end()는 마지막 순차열의 반복자를, search()는 첫 번째 순차열의 반복자를 반환한다. 

 

10.search_n(b, e, n, x)

순차열[b, e)에서 원소x 가 n번 연속한 첫원소의 반복자를 반환한다. 

이항 조건자를 사용해 search_n(b, e, n, x, f)와 같이 사용할 수 있다.

bool Pred(int left, int right){
	return abs(right - left) <= 5;
}

// v = {10, 20, 32, 28, 33, 40, 50}

iter = search_n(v.begin(), v.end(), 3, 30, Pred);
// 30과 값 차이가 5 이하인 숫자가 3개 이상 연속한 첫 원소의 반복자 반환
// iter = 32를 가리킴