algorithm이란? STL 컨테이너는 자료구조(데이터를 저장하는 구조)를 의미하고 vector, list, deque, map, set 등이 있었다 STL 알고리즘은 데이터를 어떻게 사용할지에 대한 부분을 의미하고 대표적인 알고리즘은 아래와 같다 #include using namespace std; find(InputIterator first, InputIterator last, const T& value); find_if(InputIterator first, InputIterator last, UnaryPredicate pred); count(InputIterator first, InputIterator last, const T& value); count_if(InputIterator first, ..
사용 구현(과제, 면접 등) vector O O list X O deque X X map O X set O X multimap X X multiset X X 직접 구현을 해보는 과제로 등장하는 것은 vector와 list이다 stl 사용 빈도를 정리하면, vector > map > set > deque, multimap, multiset (정말 가끔) > list (거의 사용 안 함)
multimap과 multiset map과 set은 key의 중복이 허용되지 않는다 multimap과 multiset은 key의 중복이 허용되고 사용 빈도수가 다소 낮다 multimap의 간단한 사용법 map에 사용되는 insert, erase, find 등과 같은 대부분의 기능을 사용할 수 있다 다만, [] 문법을 사용할 수 없다 key가 중복되다 보니 어떤 key에 대한 value를 추가하거나 수정할지 명확하지 않을 수 있어서 막아둔 것이다 erase()의 경우는 해당 key를 들고있는 데이터를 모두 삭제하고 삭제된 데이터 개수를 반환한다 find()의 경우는 해당 key를 들고 있는 데이터 중 가장 첫 번째인 iterator만 반환한다 #include #include #include using na..
//map이 뭐였지? https://motivelessstudy.tistory.com/260 set이란? map과 거의 비슷하지만 value가 없이 key만 사용하는 특징이 있다 굳이 key와 value의 두 가지를 저장할 필요가 없을 때 사용한다 map과 같이 균형이진트리(AVL)이기 때문에 데이터의 정렬에서는 시간이 걸리지만 탐색을 매우 빠르게 할 수 있다 간단 사용법 insert, erase, find처럼 map에서 지원하는 대부분의 기능들을 거의 비슷하게 지원해 준다 다만, value가 없어서 쌍(pair)을 사용할 필요가 없고 [] 문법은 지원해주지 않는다 간단 사용법 코드 예시 #include #include using namespace std; void main(void) { set s; /..
연관 컨테이너(Associative Containers) 연관 컨테이너(Associative Containers)는 데이터를 저장할 때 각 요소의 키(key)와 값(value)을 쌍(pair)으로 저장한다 이러한 키와 값의 쌍은 서로 연관되어 있으며, 키를 사용하여 값을 빠르게 검색할 수 있다 대표적으로는 map, set 등이 있다 Sequence Contaioners vs. Associative Containers 시퀀스 컨테이너는 특정한 데이터를 찾고 탐색하는 경우에 모든 데이터를 순회해야 하기 때문에 시간이 오래 걸린다는 단점이 있다 반면에, 연관 컨테이너는 데이터의 삽입과 삭제를 하는 과정에서 정렬을 해야해서 조금 효율이 안 좋더라도 데이터를 찾는, 탐색하는 과정이 매우 빠르다는 장점이 있다 ma..
시퀀스 컨테이너(Sequence Container) 데이터가 삽입 순서대로 나열되는 형태로 vector, list, deque가 있다 deque(double-ended queue)란? 양쪽 끝에서의 삽입과 삭제를 효율적으로 지원하는 자료 구조이다 deque는 큐(queue)와 벡터(vector)의 결합체로, 큐와 마찬가지로 FIFO(First-In-First-Out)의 특성을 가지고 있으면서도 벡터처럼 임의의 위치에서의 접근이 가능합니다. deque는 블록(block)으로 구성되어 있으며, 각 블록은 일정 개수(일반적으로는 4개)의 요소를 저장하고 내부적으로 블록 간의 참조를 조정하여 삽입과 삭제를 효율적으로 수행할 수 있다 deque vs. vector deque는 capacity가 존재하지 않는다 데..
list의 동작원리 단일/이중/원형 등으로 다양한 종류의 링크드리스트가 있다 데이터의 위치가 불연속적이고 하나의 노드가 1) 데이터 2) 이전이나 다음의 데이터 위치 를 알고 있는 형태이다 C++ STL list 동작원리 C++ STL list에서는 마지막 데이터가 포함된 노드에 추가적으로 NULL이 들어가는 end() 노드가 연결되어 있다 주의할 점으로는 1. 마지막 데이터 노드와 end() 노드가 서로 연결돼 있다 따라서, end() 노드에서 마지막 데이터 노트로 접근 가능 마지막 데이터 노드에서 end() 노드로 접근은 가능, 수정은 불가능 2. begin() 노드와 end() 노드가 서로 연결돼 있다 end() 노드의 next 노드로는 begin() 노드가 begin() 노드의 previous 노..
STL과 Container STL은 Standard Template Library이다 프로그래밍할 때 필요한 자료구조/알고리즘을 템플릿으로 제공하는 라이브러리이다 이런 라이브러리에서 자료구조와 관련된 데이터를 저장하는 객체를 컨테이너(Container)라고 부르며 대표적으로 vector, list, map, set 등이 있다 배열 vs. vector(동적배열) vector는 동적배열이다 일반적인 배열은 선언 이후에 capacity를 변경 불가하다 동적배열은 선언 이후에 capacity가 자동으로 변경된다 vector 간단한 사용법 #include #include using namespace std; void main(void) { vector v; v.push_back(1);// 현재 size에서 다음 ..
