[ STL 자료구조 unordered_map/set ] unordered_map과 unordered_set은 이름 그대로 순서가 없다. key값과 value값이 연관은 있지만, 순서가 없다? 이 말은 각 key 값마다 해시 번호표가 있어서 원하는 데이터를 즉각 찾을 수 있다는 말이다. 즉, STL unordered 컨테이너는 해시(hash) 자료구조이다. 프로그래밍에서 사용하는 메모리와 성능은 반비례 한다. STL unordered 컨테이너는 빠른 성능을 위해 많은 메모리를 필요로하는 단점이 있다. (내부적으로 vector와 list를 같이 쓰기 때문에 많은 메모리가 필요) 데이터를 담을 때 hash함수를 거쳐서 번호표를 받는다. 해시값을 미리 내부에 vector로 만들어 놓는다. (버킷을 만들어 놓는다..

[ STL 자료구조 map / set ] STL array, vector, list가 연속 컨테이너(Sequential Container)였다면 map과 set은 연관 컨테이너(Associative Container)이다. 연관이라는 말은 저장하려고 하는 자료와 key값이 서로 관련이 있다는 의미이다. map은 pair를 원소로 저장하는데, key를 기준으로 데이터를 정렬한다. set은 key를 기준으로 원소를 정렬 상태로 저장하지만, value가 따로 있지 않다. 즉, set은 key와 value가 같은 데이터를 원소로 저장한다. 연관 컨테이너는 찾고자 하는 원소를 빨리 찾기 위해 사용한다. 여기서 빠르다는 것은 연속 컨테이너보다 빠르다는 의미이다. 연관 컨테이너에서 원소를 찾는 데 걸리는 시간 복잡도..

[ STL 자료구조 list ] STL의 list는 이중 연결 리스트이다. 원소를 한 번에 하나씩 앞 뒤로 순회할 수 있는 양방향 반복자(bidirectional iterator)를 제공한다. 어느 위치에서든 상수 시간에 원소를 삽입 & 삭제할 수 있다.vector와 달리 항상 상수 시간에 원소를 접근할 수 있는 랜덤 반복자를 제공하지는 않지만,많은 알고리즘 함수는 순차적으로 액세스할 수만 있으면 충분하다. [ STL list 원소 추가 ] list는 양방향으로 원소에 접근할 수 있기 때문에 vector와 달리 컨테이너의 앞, 뒤로 원소를 추가할 수 있다. [ STL list 원소 제거 ] 1. 전역함수 remove 4라는 원소가 제거됐지만, remove() 함수는 제거하려는 원소가 어떤 컨테이너의 원소..

[ STL 자료구조 vector] STL vector는 array와 달리 동적 배열이다. 동적이란 무슨 뜻일까? 프로그램이 실행될 때 무엇인가가 변화한다는 의미이다. 배열에서 변할 수 있는 것은 배열의 원소 개수이다. vector는 실행 시 원소의 개수가 변할 수 있다. vector는 반드시 물리적으로 연속된 메모리를 사용하여 원소를 저장한다. vector에 원소가 가득 차면, 메모리는 new로 요청해서 새로 확보한다. 1. 현재 담을 수 있는 원소의 개수(capacity) 보다 더 큰 새 메모리를 요청한다. 2. 새 메모리에 현재 원소를 모두 복사한다. 3. 복사한 원소들의 다음 위치에 새 원소를 추가(push_back)한다. 4. 이전 메모리를 반환(delete)한다. 즉, 메모리를 새로 할당받고 거..