[STL] STL Algorithm - sort, nth_element, find, find_if

2024.12.12 (강의), 13 (기록) 이건 조금 할만할지도? 실제로 문제를 풀어봐야겠다

​

Algorithm Library

: data를 처리해나가는 유용하고 다양한 함수들이 모여있는 Library

: 주로 container 반복자(배열 주소 값)로 다양한 작업을 수행하도록 도와줌. (반복자 없이 값으로만 수행되는 함수도 O)

functuin을 인자로 설정해주기도 함.

range는 항상 [ first, last ) ; first포함, last 미포함 (first ~ last -1)

func(iterator first, iterator last, T value)  // finf, count, lower_bound, upper_bound 사용형태
func(iterator first, iterator last)           // sort, max_element, min_element 사용형태
func(iterator first, iterator last, function f) // for-each, find_if, count_if, sort 사용형태
func(T a, T b)                                // swap, max, min 사용형태
func({initializar list})                      // max, min 사용형태

 

 

function f (조건) 설정하기

vector, 절대값 기준, 오름차순 정렬 sort(arr, arr+n, comp)
1. naive function	2. function ogject	3.lambda (별도 공부)
bool comp(int a, int b) {       return abs(a) < abs(b) ; } // return 조건이 참이되게 만들어줌. // 일반적으로 직접 적어야하면 사용하는 방식.	struct Compare { bool operator() (const int a, const int b) const{ return abs(a) < abs(b); } } comp; //Compare<int>{}; 또는 comp 로 사용	auto comp=[](int a, int b){              return abs(a)<abs (b) ;}

​

Algorithm library 주요 함수

https://en.cppreference.com/w/cpp/algorithm (자세한건 여기서 추가적으로 참고)

• • • sort, parital_sort, nth_element, find, find_if (별도 정리**)
    • swap, for_each , fill
    • max, min, minmax, max_element, min_element, minmax_element
    • lower_bound, upper bound
    • count, count_if, remove, remove_if etc

함수에 따라서 허용되는 iterator의 범위가 다름.

​

나머지 함수들은 for문으로도 처리가 가능한 친구들!

​

swap(), max(), min()

void swap (T a, T b)   // swap  =  a,b의 값을 바꾼다

T max(T a, T b, Compare comp)  // max = comp기준 (Compare comp 안쓰면 operator< 기준 큰 값)
T min(T a, T b, Compare comp)  // min = comp기준 (Compare comp 안쓰면 operator< 기준 작은 값)

pair <T,T> minmax(T a, T b, Compare comp) 
// comp기준(Compare comp 안쓰면 operator< 기준 first : 작은값, second : 큰값)

lower_bound(), upper_bound() RandomIt : O(log n), Otherwiae : O(n)

= 정렬된 구간에서만 사용 가능. binary seach 기반

- camp 기준은 Compare requirement 필요 없이 BinaryPredicate만 만족

template <class ForwardIt, Class T>
ForwardIt lower_bound(Forward first, Forward last, const T&value); // comp 명시X = operator< 기준

template <class RandomIt, Class T, class Compare>
ForwardIt lower_bound(Forward first, Forward last, const T&value, Compare comp);

auto it = lower_bound(arr.begin(), arr.end(),5); 
//lower_bound : [first, last) 구간에서 comp 기준으로 value보다 크거나 같은 첫번째 element iterator 반환
auto it = upper_bound(arr.begin(), arr.end(),5); 
//upper_bound : [first, last) 구간에서 comp 기준으로 value보다 큰 첫번째 element iterator 반환

​

min_element(), max_element(), minmax_element()

template <class ForwardIt>
ForwardIt max_element(Forward first, Forward last);

template <class ForwardIt, class Compare>
ForwardIt max_element(Forward first, Forward last, Compare comp);

max_element	min_element	minmax_element
[first,last) 구간에서 comp 기준으로 가장 큰 element iterator 반환. comp 없으면 operator< 기준	max_element와 형식, 사용 방법 동일	pair<ForwardIt, ForwardIt> 반환 first: min iterater second: max iterator

 

for_each()

= [ first, last) 구간의 모든 element에 대해 f를 수행. UnaryFunction

template <class InputIt, class UnaryFunction>
UnaryFunction for each(InputIt first, InputIt last, UnaryFunction f);

vector<int> arr {1,2,3,4,5};
for each(arr.begin(), arr.end(),[](int x){x++;});  // 1,2,3,4,5
for each(arr.begin(), arr.end(),[](int &x){x++;});  // 2,3,4,5,6

 

count(), count_if()

count()	count_if()
[first,last) 구간에서 값이 value인 개수를 반환	[first,last) 구간에서 p의 결과가 ture인 element 개수를 반환
template <class InputIt, class T> typename iterator_traits<InputIt>::difference_type count(InputIt first, InputIt last, const T&value);	template <class InputIt, class UnaryPredicate> typename iterator_traits<InputIt>::difference_type count_if(InputIt first, InputIt last, UnaryPredicate p); // UnaryPredicate : bool p (T a)
int cut = count(arr.begin(), arr.end(),1)	int cut = count_if(arr.begin(), arr.end(),[](auto x){return x<10});

​

remove(), remove_if()

count()	count_if()
[first,last) 구간에서 값이 value인 element를 모두 지우고 새로운 past-the-end iterator 반환	[first,last) 구간에서 p를 만족하는 element를 모두 지우고 새로운 past-the-end iterator 반환
template <class ForwardItt, class T> ForwardIt remove(Forward first, Forward last, const T&value); //실제 해당 객체의 end() iterator가 변경되는 건 아니므로 필요하면 erease를 통해 지워야함.	template <class ForwardIt, class UnaryPredicate> ForwardIt remove_if(Forward first, Forward last, UnaryPredicate p); // UnaryPredicate : bool p (T a)
auto it = remove(arr.begin(), arr.end(),1); erase(it,arr.end());	auto it = remove_if(arr.begin(), arr.end(), [](auto x){return x<10}); erase(it,arr.end());

sort() ; O(n log n)

template <class RandomIt>
void sort (RandomIt first, RandomIt last);

template <class RandomIt, class Compare>
void sort (RandomIt first, RandomIt last, Compare comp/*정렬의 기준*/);

= [first, last) 구간을 comp기준에 맞게 정렬 (기본값은 오름차순 (operator<))

bool comp (const T&Ihs, const T&rhs) **bool은 필수 const랑 &은 필수. Compare requirement

오로지 random access iterator만 가능하므로 vector, string, depue는 가능 list, set, map (bidirectional) 불가능

* list의 경우 자체적으로 정렬을 제공함. 대신 기준 설정은 불가능하고 단순 오름차순 정렬만 가능

vector<int>arr{5,3,-2,1,-4};
sort(arr.begin(), arr.end());                   //-4,-2,1,3,5
sort(arr.begin(), arr.end(), greater<int>{});   // 5,3,1,-2,-4 (class를 함수로 만들려면 임시객체 필수)

1. naive function	bool absSort(int l, int r) {return abs(l) < abs(r); } ​ sort(v.begin(), v.end(), absSort);
2. function ogject	struct AbsSort { bool operator() (int l, int r) {return abs(l) < abs(r); } }absSort; ​ sort(arr.begin(), arr.end(), absSort{}); 또는 sort(arr.begin(), arr.end(), absSort);
3.lambda (별도 공부)	sort( arr.begin(), arr.end() [](auto &l, auto &r) {return abs(l) < abs(r); } );

partial_sort() ; O ((L-F) log (M-F)) = O(n log m)

= [first, last) 구간에서 우선순위 기준으로 [first, middle)만 정렬 (middle 포함 x)

: heap sort 기반, degault값과 compare설정은 sort와 동일

template <class RandomIt>
void partial_sort (RandomIt first, RandomIt middle, RandomIt last);

template <class RandomIt, class Compare>
void partial_sort (RandomIt first, RandomIt middle, RandomIt last, Compare comp);

void<int>arr{5,3,-2,1,4};
partial_sort(arr.begin(), arr.begin()+2, arr.end());  // -4, -2, 5,3,1  (시간복잡도 = 5log2)

 

nth_element() ; average O(n) - worst는 O(n²까지 가기도 함.)

= [first, last) 구간에서 comp기준(defult: <)으로 nth 위치의 값을 선택하여 왼쪽, 오른쪽에 기준에 맞게 값 배열

< 기준일 때 (정렬은 아니고 단순 배열), 완쪽 (작거나 같은 값) /// nth값 /// (크거나 같은 값) 오른쪽

: IntroSelect기반, comp 기준은 sort와 동일

template <class RandomIt>
void nth_element (RandomIt first, RandomIt nth, RandomIt last);

template <class RandomIt, class Compare>
void nth_element (RandomIt first, RandomIt nth, RandomIt last, Compare comp);

void<int>v;
nth_element(v.begin(), v.begin()+3, arr.end());  // xxxOyyy (조건 기준으로 n번째 element구할 때)

 

find(), find_if()

• find()

= [first, last) 구간에서 값이 value인 첫번째 element의 iterator(위치)반환

template <class InputIt, class T>
inputIt find(InputIt first, InputIt last, const T& value); // 구간, 값

auto it = find(arr.begin(), arr.end(),1)
​

find_if()

= [first, last) 구간에서 f의 결과가 ture인 첫번째 element의 iterator 반환

template <class InputIt, class UnaryPredicate>
inputIt find_if(InputIt first, InputIt last, UnaryPredicate p); //UnaryPredicate : bool p(T a)

auto it = find_if(arr.begin(), arr.end(),[](auto x){return x<10});