Brute force Study

std::deque배열 기반 컨테이너와 리스트 기반 컨테이너 두 가지 방식이 섞여있는 형태각각의 장점을 적당히 가지고 있다vector에서 push_front(), pop_front() 에서 비용이 많이 드는 단점을 극복할 수 있다deque : 양방향 큐(double-ended-queue)의 약자덱의 구조C++ 표준은 덱의 동작에 있어 다음 조건을 만족해야 한다고 규정한다.push_front(), pop_front(), push_back(), pop_back() 동작이 O(1) 시간 복잡도로 동작해야 함모든 원소에 대해 임의 접근 동작이 O(1) 시간 복잡도로 동작해야 함덱 중간에서 원소 삽입 또는 삭제는 O(n) 시간 복잡도로 동작해야 하며, 실제로는 최대 n / 2 단계로 동작하며 여기서 n은 덱의 크..

std::list복습std::forward_list는 기본적인 형태로 구현된 연결 리스트임리스트 끝에 원소 추가, 역방향 이동, 리스트 크기 반환 등의 기능을 제공하지 않음빠른 원소 삽입이 필요한 모든 경우에 어울리는 container는 아니다.std::forward의 단점을 보완하기 위해 c++에서 std::list를 제공한다std::list양쪽 방향으로 연결된 리스트, 즉 이중 연결 리스트(doubly-linked-list) 구조로 되어 있다.따라서 더 많은 기능을 제공한다. (메모리는 조금 더 많이 사용한다)// 이중 연결 리스트 노드 기본 형태struct doubly_linked_list_node{ int data; doubly_linked_list_node* next; doubl..

Iterator(반복자)반복자는 포인터와 비슷하지만, STL container에 대한 공통의 interface를 제공한다.반복자를 이용한 연산은 어떤 컨테이너에서 정의된 반복자인지에 따라 결정된다.배열과 벡터의 경우 연속된 자료 구조를 사용하기 때문에 지정 위치의 원소에 바로 접근할 수 있다.이러한 반복자를 임의 접근 반복자(random access iterator)라고 한다.std::foward_list의 경우 역방향 이동을 제공하지 않으며, 이전 노드로 이동하려면 처음부터 다시 찾아가야 한다.증가 연산만 가능하며, 이러한 반복자를 순방향 반복자(foward iterator) 라고 한다.반복자 타입에 따라 사용할 수 있는 함수advance()반복자와 거리 값을 인자로 받고, 반복자를 거리 값 만큼 증가..