개발/C·C++
-
[알고리즘] Quick sort개발/C·C++ 2021. 8. 3. 16:17
종류 분할-정복 알고리즘입니다. 분할-정복 알고리즘은 재귀적으로 자신을 호출하면서 연산 단위를 조금씩 줄여나가는 방법입니다. 재귀 호출이 한 번 진행될 때마다 최소 하나의 원소는 위치가 정해지기 때문에 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있습니다. 장점 재귀호출의 과정에서 임시 메모리를 쓰는 것은 성능 저하를 가져오기 때문에(리턴값을 사용하지 않음) 배열 내부에서 분할 작업을 구현하는 편이 좋습니다. 퀵 정렬은 메모리 참조가 지역화되어 있기 때문에(캐시의 공간 지역성) 캐시 히트률이 높습니다. 이런 이유로 일반적인 경우 퀵 정렬은 다른 O(nlogn) 알고리즘보다 빠르게 작동합니다. 기본 흐름 피벗을 기준으로 왼쪽에는 피벗보다 작은 원소를, 오른쪽에는 피벗보다 큰 원소들을 위치합니다. 개념적으..
-
[자료구조] doubly linked list개발/C·C++ 2021. 8. 2. 19:51
오류가 있을 수 있습니다. 멀티스레드 환경이 고려되지 않았습니다. 템플릿을 사용하지 않았고 int형 데이터만 저장합니다. 표준 라이브러리(std::list)의 멤버 함수를 일부 참고했습니다. DDL.h #pragma once class DDL { private: struct Node { int data; Node* prev; Node* next; public: Node(int data) :data(data) { prev = nullptr; next = nullptr; } }; private: int _size = 0; Node* _head = nullptr; Node* _tail = nullptr; public: DDL() = default; ~DDL(); void push_front(int data);..
-
[overloading] operator <<개발/C·C++ 2021. 7. 28. 14:17
참고 C++ draft 연산자 오버로딩에 적용되는 규칙이 있습니다. 규칙과 관련해서 예제 몇 개를 작성해보겠습니다. Expression @a as member function #include class Position { private: int x; int y; public: Position() = default; Position(int x, int y) :x(x), y(y) {} Position operator-() const { return Position{ -x, -y }; } void print() const { std::cout
-
condition_variable::wait개발/C·C++ 2021. 7. 26. 01:19
condition_variable는 생산자-소비자 모델에 쓰이는 클래스입니다. 멤버 함수인 wait 함수는 첫 번째 인자로 unique_lock을 받습니다. condition_variable 클래스는 오직 std::unique_lock을 통해서만 작동합니다. 이러한 제한은 일부 플랫폼에서 최대 효율을 만들 수 있습니다. 두 번째 인자는 predicate을 넣어주는데, 특정 조건을 만족하기 전까지 해당 스레드는 블록되며 원자적으로 언락됩니다. 블록된 스레드는 notifiy_all()이나 notify_one()이 실행될 때 블록이 풀리는데, 때로는 그냥 풀릴 수도 있습니다(spuriously). 블록이 풀리면, 락이 다시 획득되고 대기가 끝납니다. 예제 코드 #include #include #include ..
-
Default arguments개발/C·C++ 2021. 7. 5. 14:39
사소한 거지만 데 잠시 고민해봤습니다. 왜 디폴트 매개변수는 오른쪽 끝에서부터만 가능한 걸로 제한을 걸었을까. 함수를 호출할 때 왼쪽부터 인수를 채웁니다. 선언된 순서대로 매개변수를 넣어줘야 합니다. 사실 그렇게 하지 않으면 바로 컴파일 에러가 발생해버립니다. 그렇기 때문에 디폴트 매개변수 기능을 만들 때 반대 방향인 오른쪽에서부터 하도록 강제하면 개발자가 실수로라도 함수를 잘못 설계하는 일이 매우 적어지는 것 같습니다. 또한 기본 함수 호출 규약인 __cdcel이 파라미터를 오른쪽부터 전달하기 때문에 파라미터에 디폴트로 값을 넣어야 한다면 오른쪽부터 하는 것이 더 안전해보입니다.
-
[Template] 템플릿 구체화개발/C·C++ 2021. 7. 5. 04:19
STL 컨테이너를 보면 선언과 정의가 분리되어 있지 않습니다. 클래스는 선언부와 정의부를 나누는 경우가 조금 더 일반적일 텐데요. 일반화 프로그래밍이라는 템플릿 라이브리리는 일반적인 방법을 따르지 않는 것처럼 보입니다. 라이브러리를 만드는 사람들이 뭘 몰라서 그런 것은 아닐 테니까, 그럴 만한 이유가 있을 겁니다. 그 이유를 파악해 봅시다. #include int main() { std::vector vec; for (int i = 0; i < 5; ++i) vec.push_back(i); } 간단한 벡터 예제입니다. 연산자를 통해 int형 데이터를 담을 수 있는 컨테이너를 만들어 반복문을 이용해 0부터 4까지 넣었습니다. std::vector을 명시적 구체화라고 합니다. 함수 템플릿에 넣는 인수를 통해..
-
[Priority queue] 간단한 참고개발/C·C++ 2021. 7. 3. 21:34
cppreference를 보면 내부적으로 디폴트로 vector을 이용해 데이터를 저장하며 정렬 방식은 오름차순인 것을 알 수 있습니다. less가 왜 오름차순인 이유는 왼쪽 항을 기준으로 a < b이기 때문에 결과적으로 오름차순이 됩니다. 우선순위 큐는 데이터의 최대값, 최소값을 찾고 싶을 때 유용합니다. 상수 시간으로 찾을 수 있습니다. 그렇다면 다음의 결과가 어떻게 될까요? priority_queue pq; pq.emplace(3); pq.emplace(5); pq.emplace(2); pq.emplace(4); pq.emplace(1); while (!pq.empty()) { cout
-
Guaranteed Copy Elison개발/C·C++ 2021. 6. 27. 18:15
>> 번역글입니다 >> 의역은 있고 오역이 있을 수 있습니다 >> 출처 https://jonasdevlieghere.com/guaranteed-copy-elision/ Copy Elision C++17 표준의 변화를 논의하기 전에, C++14 표준에 정의되어 있던 복사 생략의 기본을 다시 살펴보는 것이 도움이 될 수 있습니다. 복사 생략이 무엇이고 어떻게 동작하는지 안다면 이 파트는 건너뛰어도 됩니다. Foo 구조체는 모든 예제에서 사용됩니다. 생성자와 소멸자가 호출될 때마다 해당 정보들이 출력될 것입니다. struct Foo { Foo() { std::cout