push_back()과 emplace_back() 둘 다 벡터의 뒤쪽에 원소를 추가합니다. 그런데 실제로 구현된 복사/이동 방식은 크게 다르며, 성능에서도 차이가 납니다. push_back()vs.push_back(s)는 문자열을 벡터로 복사합니다. 먼저, char *로 초기화된 새 문자열 객체가 암시적으로 생성됩니다. 그 다음 push_back()이 호출되는데, push_back()은 이동 생성자를 이용해 임시 문자열을 벡터로 복사합니다. 작업이 다 끝나면 임시 객체를 없앱니다.   emplace_back()vs.emplace_back(s)는 임시 문자열을 생성하지 않습니다. emplace_back()이 char *를 인수로 하여 직접 호출합니다. 그런 다음 이 char *로 초기화된 벡터에 저장할 문..

레드 블랙 트리는 균형 이진 탐색 트리로 탐색, 삽입, 삭제 모두 시간 복잡도가 O(logn)입니다. C++ STL의 set, multiset, map, multimap이 이 레드 블랙 트리를 이용해 구현되어 있습니다. 레드 블랙 트리가 균형을 유지하는 비결레드 블랙 트리는 아래의 규칙을 지킴으로써 균형을 유지합니다.모든 노드는 빨간색 또는 검은색의 색을 가진다.루트 노드는 검은색이다.잎 노드(NIL)는 검은색이다. (NIL : null leaf, 데이터를 갖지 않고 트리의 끝을 나타내는 더미 노드)빨간 노드의 자식은 모두 검은색이다, 하지만 검은색 노드의 자식이 빨강일 필요는 없다.루트 노드에서 모든 잎 노드 사이에 있는 검은색 노드의 수는 모두 동일하다. 레드 블랙 트리의 기본 연산회전회전은 부모-자..

C++의 가상 함수 동작 원리가상 함수는 'vtable', 혹은 가상 테이블(virtual table)에 의존한다. 어떤 클래스의 함수가 virtual로 선언되어 있으면, 해당 클래스의 가상 함수 주소를 보관하는 vtable이 만들어진다. 컴파일러는 또한 해당 클래스의 vtable을 가리키는 vptr이라는 숨겨진 변수(hidden variable)를 해당 클래스에 추가한다.하위클래스가 상위 클래스의 가상 함수를 오버라이드(override)하지 않으면 하위 클래스의 vtable은 상위 클래스의 가상 함수 주소를 보관한다. 이 vtable을 사용하여 가상 함수가 호출될 때 어느 주소에 있는 함수가 호출되어야 하는지를 결정한다. c++의 동적 바인딩(dynamic binding)은 이 가상 테이블 메커니즘을 ..

순차 컨테이너(sequential container)는 원소들이 선형으로 배열된 데이터 구조를 나타냅니다. 컨테이너헤더설명array표준 C 언어 스타일 배열vector활용도가 높은 기본 컨테이너list연결 리스트(linked list)deque양방향 큐(queue) 배열(std::array)array는 고정된 크기의 배열을 담는 컨테이너입니다. 인덱스를 이용해 원소에 빠르게 접근할 수 있다는 장점이 있습니다. 배열 컨테이너 선언#include using namespace std;array 객체_이름; array 컨테이너를 초기화하는 방법은 일반 배열과 같습니다. 또한 일반 배열처럼 [] 연산자로 각 원소에 접근할 수 있습니다. 배열의 유효 범위 밖의 인덱스로 접근을 시도하면 런타임 오류가 발생합니다.ar..