STL) 분할, 정렬, 힙에 대한 추가 연산들 (stable_*, is_*, is_*_until)

<개요>

안정적 연산인 stable_* 함수 ( stable_sort, stable_partition )
현재 이 컨테이너가 정렬, 분할, 힙( 또는 주어진 술어에 대해 ) 적인지 판단하는 연산인 is_* 함수 ( is_sort, is_heap, is_partition )
현재 이 컨테이너가 정렬, 분할, 힙( 또는 주어진 술어에 대해 ) 적인지 그렇지 않다면 어디까지 해당하는지에 대해 반복자를 반환해주는  
is_*_until 함수( is_sorted_until, is_heap_until, is_partitioned_until ) 에 대해 작성합니다.

모든 연산은 vector를 기준으로하며, 사용법이 다 똑같아 간단한 sort에 대해서만 작성합니다.


모든 stable_* 연산은 일반 * 연산보다 비용이 비쌉니다.
is_* 와 is_*_until은 선형 복잡도를 가지고 있습니다.

<std::stable_*> 주어진 연산에 대해 안정적 ( 같은 값일때 그 값의 순서가 바뀌지 않음 ) 인 연산을 합니다. class A { public: A(int _t1, char _t2) : m_n(_t1), m_c(_t2) {} int getint()const { return m_n; } char getchar()const { return m_c; } private: int m_n; char m_c; }; int main() { A aa[10] = { {1,'b'}, {1,'a'}, {2,'c'}, {2,'a'} , {2,'b'}, {5,'a'}, {5,'b'}, {5,'c'}, {10,'a'}, {10,'b'} }; cout << "정렬 전" << endl; for (auto& i : aa) cout << '[' << i.getint() << "," << i.getchar() << "]"; cout << endl; std::stable_sort(aa, aa + 10, [](const A& i, const A& j) { return i.getint() > j.getint(); }); cout << "정렬 후" << endl; for (auto& i : aa) cout << '[' << i.getint() << "," << i.getchar() << "]"; } <std::is_*> 주어진 컨테이너가 정렬, 분할, 힙 ( 또는 주어진 술어에 대해 ) 적인지 확인합니다. vector<int> a = { 1,2,3,4,5 }; vector<int> b = { 1,2,3,4,6 }; vector<int> c = { 2,3,4,5,1 }; is_sorted(a.begin(), a.end()); // true is_sorted(b.begin(), b.end()); // true is_sorted(c.begin(), c.end()); // false is_sorted(a.begin(), a.end(), std::greater<int>()); // false, a 컨테이너는 오름차순임 <std::is_*_until>   주어진 컨테이너가 정렬, 분할, 힙( 또는 주어진 술어에 대해 ) 적인지 그렇지 않다면 어디까지 해당하는지에 대해 반복자를 반환해줍니다. 만약 모두가 적합하다면 end 를 반환합니다. vector<int> a = { 1,2,3,4,5 }; vector<int> b = { 1,2,3,4,6 }; vector<int> c = { 2,3,4,5,1 }; auto iter1 = std::is_sorted_until(a.begin(), a.end()); auto iter2 = std::is_sorted_until(b.begin(), b.end()); auto iter3 = std::is_sorted_until(c.begin(), c.end()); auto iter4 = std::is_sorted_until(a.begin(), a.end(), greater<int>()); cout << (iter1 == a.end()); // true , iter1 의 값은 end cout << (iter2 == b.end()); // true , iter2 의 값은 end cout << (iter3 == c.end()); // false, iter3 의 값은 1 ( 5번째 원소 ) cout << (iter4 == a.end()); // false, iter4 의 값은 2 ( 2번째 원소 )