본문 바로가기

Old/복습11

STL - next_permutation 현재 탐색하고 있는 순열의 다음 순열을 구하고 true를 반환한다. 만약, 다음 순열이 존재하지 않는다면 false를 반환한다. 즉, 마지막 모든 순열의 경우의 수를 탐색한 뒤, false를 반환한다. template bool next_permutation(BidirIt first, BidirIt last) { auto r_first = std::make_reverse_iterator(last); auto r_last = std::make_reverse_iterator(first); auto left = std::is_sorted_until(r_first, r_last); if (left != r_last) { auto right = std::upper_bound(r_first, left, *left);.. 2024. 2. 1.
STL - set namespace pmr { template using set = std::set; } Time Complexity Red - Black Tree로 구현되어 search에 O(logn)의 시간이 걸리며, 삽입 및 삭제는 O(logn + a)의 시간이 걸린다. Red - Black Tree 자가 균형 이진 탐색 트리로, 다음과 같은 조건들을 만족한다. 모든 노드는 빨간색 또는 검은색이다. 루트 노드는 검은색이다. 모든 리프 노드(NIL)들은 검은색이다. 빨간색 노드의 자식은 검은색이다. (즉, 빨간색 노드가 연속으로 나올 수 없다.) 모든 리프 노드에서 Black Depth는 같다 (즉, 리프 노드에서 루트 노드까지 가는 경로에서 만나.. 2024. 1. 30.
STL - sort sort 범위의 요소 정렬 std::invoke(comp, std::invoke(proj, *(it + n)), std::invoke(proj, *it)) 요소는 주어진 comp 비교 함수를 통해 비교가 진행됨 이때, ranges::begin(r) ~ ranges::end(r)로 범위를 표현할 수 있음 Time Complexity O(Nlog(N)) 이때, N = ranges::distance(first, last)이다. struct sort_fn { template requires std::sortable constexpr I operator()(I first, S last, Comp comp = {}, Proj proj = {}) const { if (first == last) return first.. 2024. 1. 18.
STL - max_element와 min_element max_element template ForwardIt max_element(ForwardIt first, ForwardIt last) { if (first == last) return last; ForwardIt largest = first; while (++first != last) if (*largest < *first) largest = first; return largest; } template ForwardIt max_element(ForwardIt first, ForwardIt last, Compare comp) { if (first == last) return last; ForwardIt largest = first; while(++first != last) if (comp(*largest.. 2024. 1. 18.
C++ - 복사 생성자 : 한 객체가 다른 객체로 복사될 때 호출되는 특별한 멤버 함수 class MyClass { public: // 복사 생성자 MyClass(const MyClass& other) { // 복사 수행 // ... } // 다른 멤버 함수들과 변수들 }; 객체의 복사 생성자는 해당 객체와 동일한 자료형의 다른 객체를 받아들여서, 원본 객체의 내용을 새로 생성된 객체에 복사함 여기서 const MyClass& other는 복사 생성자의 매개변수로 전달되는 객체를 상수 참조로 받음을 나타냄 복사생성자가 호출될 때 복사될 객체를 변경하지 않고 읽기만 한다는 것을 의미 복사 생성자가 호출되는 상황 객체의 복사가 필요한 경우: 객체를 다른 객체로 복사하려고 할 때 함수에 인자로 전달 객체 반환 MyClass obj1.. 2024. 1. 3.
C++ - 범위 기반 for문 구문 for (for-range-declaration : 식) statement 설명 기존의 for문과 달리, 시작과 끝점을 알려주지 않아도 알아서 처음부터 끝까지 순회하는 반복문 index 정보 존재하지 않음 기존의 for문에서는 index를 나타내는 로컬 변수가 존재하는데, 범위기반 for문에는 존재하지 않음 오직 elem이라는 값만 존재 array의 요소를 변경할 수 없음 매 반복문을 돌 때마다 int elem : arr을 통해 하는 일은 다음과 같음 elem = arr[0]; elem = arr[1]; 이런식으로 array의 요소들이 elem이라는 변수에 복사됨 배열의 요소를 내부에서 바꾸려고 해도 복사된 값이므로 요소 값이 바뀌지 않음 reference, const reference 위에서 말한.. 2024. 1. 3.

티스토리툴바