C++

List의 특성 List는 Node 기반 컨테이너이다. List는 이중 연결 리스트(Doubly Linked List)로 구현되어 있다. 이중 연결 리스트 구조로 인해 임의의 위치에 있는 요소에 바로 접근할 수 없다. 원소의 시작과 끝 위치만 기억하기 때문에 임의의 위치에 있는 요소에 접근하기 위해서는 링크를 하나씩 따라가야한다. itr++ // itr ++ itr-- // --itr 가능 itr + 5 // 불가능! List는 Vector와 달리 노드 기반으로 서로 연결되어 있어 원소를 삽입하거나 삭제할 때 모든 원소를 밀어내지 않아 속도가 빠르다. 삭제시 반복자가 가리키는 원소 자체를 삭제해야 원소가 사라지며, 동작자체에서 반복자를 무효화 시키지 않는다. List는 이중 연결 리스트로 구현되어 있여 ..

Vector의 특성 Vector는 동적 배열로 구현되어 있다. 동적이란 프로그램이 실행될 때 무언가가 변화한다는 뜻이다. Vector는 실행 시 원소의 개수가 변할 수 있다. 배열에서 변화할 수 있는 것은 원소의 개수이기 때문이다. Vector는 연속된 메모리를 사용하여 원소를 저장한다. 원소가 가득차게되면 메모리를 요청하여 새로 확보한다. 현재 담을 수 있는 원소의 개수보다 더 큰 메모리 공간을 요청 새 메모리에 현재 원소를 모두 복사 복사한 원소들의 다음 위치에 새 원소를 추가한다. 이전에 사용한 메모리는 반환한다. Vector의 메모리 할당 연산은 큰 비용을 요구한다. 장단점 장점 Vector의 크기는 동적으로 조정이 가능하다. Vector는 [] 연산자를 통해 배열과 같이 특정 인덱스의 원소에 바..

Unordered Map의 특성 표준이 아닌 hash map 대신 unordered_map을 표준으로 정의 마이크로소프트에서도 hash_map보다는 unordered_map을 권장하고 API 문서도 제공 hash map은 성능이 보장되지 않기 때문에 권장되지 않는다. 순서있게 자료를 유지하지 않고, 입력받은 Data를 테이블에 저장한다. 입력받은 Data를 Hash 함수를 통해 Hash Table에 저장하는 것이 핵심 Key-Value 쌍으로 데이터를 저장하고, Key를 통해 Data를 빠르게 찾을 수 있다. Hash 함수를 사용하는 이유 많은 양의 Data를 저장할 때, 검색 속도를 O(1) 수준으로 만들어 버리는 강력한 솔루션이다. 시퀀스 기반의 Vector와 list 등의 검색 속도는 데이터 양에 ..

Map의 특성 Map은 Key와 Value 쌍을 특별한 순서로 저장하고 있는 연관 컨테이너(Associative Container)다. 이진 트리(Red-Black Tree)로 구현되어있고, Key를 통해 Value에 접근하고자 할 때, [] 연산자를 사용해서 접근할 수 있다. RB Tree는 쉽게 말하면 자가 균형 이진 트리이다. https://hanseongbugi2study.tistory.com/94 Red-Black Tree (RB Tree) What? Red - Black Tree는 자가 균형 이진 탐색 트리이다. 레드 - 블랙 트리는 아래와 조건을 만족한다. 모든 노드는 빨간색 혹은 검은색이다. 루트 노드는 검은색이다. 모든 리프 노드들은 검은색이다. hanseongbugi2study.tist..

vector 배열에서 중복되지 않는 원소들을 앞에서부터 채워나가는 함수이다. algorithm이라는 헤더에 존재하는 함수이다. unique함수를 사용하면 중복 없는 요소를 채운 후 남은 요소는 원래 배열의 요소를 그대로 넣는다. 즉, 중복되지 않는 원소들을 앞에서부터 채워나가는 역할을 하기때문에 남은 뒷부분은 그대로 vector 원소값이 존재한다. 또한 unique 함수가 끝나면 중복이 없는 요소의 끝 점을 반환한다. 중복을 완전히 제거하지 못하는 문제를 해결하기 위해 erase 함수를 사용해서 남은 뒷부분을 제거야한다. erase 함수는 vector 배열에서 특정 원소를 삭제하는 함수이다. v.erase(v.begin(), v.end()) 명령어를 입력하면 처음부터 끝까지 배열 내 모든 원소가 제거된다..

sort 함수는 C++ STL에서 제공하는 알고리즘이다. sort는 인자에 있는 start와 end의 범위내 요소(element)를 default로 오름차순으로 정렬해 주는 함수이다. sort(array.start(), array.end()); sort는 quick sort(퀵 정렬)을 기반으로 함수가 구현되어있어, 평균 시간복잡도는 O(n log n)이다. 따로 quick sort를 구현할 필요 없이 C++ STL에서 제공해주는 sort 함수를 이용하면 편리하게 정렬 할 수 있다. 함수의 원형은 아래와 같다. template void sort(T start, T end); template void sort(T start, T end, Compare comp); 3번째 인자를 넣지 않으면 default로..