서재

set key만 저장한다는 것을 제외하면 map과 유사한 방식으로 사용한다. #include set s; s.insert(10); s.insert(30); s.insert(20); s.insert(40); s.erase(40); s[4] = 50;// 지원하지 않는다. multimap, multiset 중복 key를 허용한다. 중복 key를 사용할 일이 거의 없기 때문에 잘 사용하지 않는다. multimap mm; multiset ms; mm.insert(make_pair(1, 100)); mm.insert(make_pair(1, 200)); mm.insert(make_pair(2, 300)); mm.erase(1);// key=1은 전부 삭제 mm[1] = 500;// 지원하지 않는다. // ms와 사..

map STL의 연관 컨테이너 중 하나다. 시퀀스 컨테이너(vector, list, deque)의 치명적인 단점은 원하는 조건에 해당하는 데이터를 빠르게 찾을 수 없다는 점이다. 이러한 문제점을 해결하기 위해 연관 컨테이너인 map을 이용할 수 있다. map은 균형 이진 트리( AVL )로 구성된다. 일단 노드 기반인 것만 알아도 된다. // map의 노드 구조 class Node { public: Node* _left; Node* _right; // DATA int _key; int _value; // 또는 pair _data } 노드를 보면 알 수 있듯이 map은 key와 value로 구성된다. map m;// (key, value) map의 데이터 삽입과 삭제 for (int i = 0; i < 1..

deque(double-ended queue) 양방향 큐라는 deque는 vector와 유사하다. vector의 메모리 할당 정책은 기존 메모리 영역이 가득찬다면, 기존 메모리에 들어있던 데이터를 복사한 뒤에 기존 영역을 삭제한다. 그리고 기존 메모리 영역보다 더 큰 새로운 메모리 영역을 생성한다. 여기에 복사한 데이터를 붙여넣는다. deque는 새로운 메모리 영역을 만든 후 해당 메모리에 데이터를 넣는다. 이때 새로운 메모리 영역은 기존 메모리 영역과 용량이 같다. 새로운 메모리 영역과 기존 메모리 영역이 list처럼 연결되어 있지 않다. 특정 테이블에서 각 메모리 위치를 관리한다. 아파트 주소를 생각하면 된다. 코드 아파트(테이블) 1동[..., 1013,...] 2동[..., 2013,...] 3동..

List(연결 리스트) 종류 단일: 노드의 순서가 한 방향이다. 이중: 노드의 순서가 양 방향이다. 원형: 이중 + 첫 노드와 마지막 노드가 연결되어 있다. 이중노드를 기준으로 list의 동작 원리를 알아보자. List STL의 vector와는 달리 list는 노드 단위로 비연속적인 메모리 공간에 존재한다. vector 때 배운 내용을 생각해보면 동작 원리를 유추할 수 있다. 노드의 구조를 잠시 살펴보면, template class Node { public: Node* _next;// 다음 노드의 주소 Node* _prev;// 이전 노드의 주소 T _data; }; 하나의 노드는 다음, 이전 노드의 주소와 데이터를 가지고 있다. list의 중간 삽입/삭제, 처음/끝 삽입/삭제 노드가 가리키는 주소를 수..

STL(Standard Template Library) 프로그래밍을 할 때 필요한 자료구조/알고리즘을 템플릿으로 제공하는 라이브러리이다. 컨테이너(Container) STL의 구성품 중 하나. 데이터를 저장하는 객체이며, 이를 자료구조(Data Structure)라 한다. 즉, 자료구조는 데이터를 저장하는 방식이다. 이제부터 알아볼 vector는 시퀀스 컨테이너( Sequence Container )의 한 종류다. 시퀀스 컨테이너는란 데이터가 삽입 순서대로 나열되는 형태를 지니는 자료구조다. vector, list, deque가 시퀀스 컨테이너에 속한다. Vector vector는 면접에서도 자주 등장하는 개념이다. vector가 동작하는 원리를 아는 것이 좋다. vector는 동적 배열이다. 배열의 단..