기본적인 자료구조와 STL 이해.
프로그램에서 데이터를 처리하기 위해서는 데이터를 어떤 방식으로 활용할것인가 생각해야 하는데, 이런 방식은 프로그램의 종류나 작업 빈도에 따라 달라진다.
응용 프로그램에서 중요한것은 제대로 동작한다는 건 기본이고, 동시에 지연 시간, 사용 메모리 또는 기타 매개 변수의 최적화된 성능을 제공해야 한다.
어떤 자료 구조를 선택함에 따라 적합한 지표, 알고리즘 복잡도, 시간 복잡도가 있다.
여기서 시간복잡도란, 작업을 수행하는 데 걸리는 시간을 수식으로 표현하는 것이며 데이터 크기가 변경되면 연산 시간이 떠허게 변하는지 보여준다. 자료 구조는 크게 연속된 자료 구조와 연결된 자료 구조로 구분할 수 있다.
연속된 자료 구조.
연속된 자료 구조는 모든 원소를 단일 메모리 청크에 저장한다.
BA = 시작 주소.
sizeof(type) = 원소 하나에 필요한 메모리 크기.
그림에서 보면 알다시피 BA는 시작주소에 sizeof(type)은 데이터 유형의 크기만큼의 공간을 갖는것이다(예로 int = 4byte, short = 2byte의 크기를 말하는거다).
수식은 BA는 현재 시작 주소에 해당 배열의 데이터 유형의 크기만큼 i번째 배열로 이동 하는것이다. (BA + i * sizeof(type))
예로 자신이 정수형 배열에 2번째 배열에 이동하고 싶으면
BA + 2 * sizeof(int)가 되는것이다.
이러한 자료 구조에서는 배열의 전체 크기에 상과없이 앞서 설명한 수식을 이용하여 모든 원소에 곧바로 접근할 수 있다.
따라서 데이터 접근 시간은 항상 일정하다. 이러한 경우를 빅오(Big-O) 표기법으로 나타내면 O(1)로도 표시한다.
이런 배열 유형에서도 정적 배열, 동적 배열이 존재하며 단어에서 알 수 있듯이
정적배열은 해당 영역에서의 선언으로 만약 해당 함수안에서 선언을 하고 종료될 경우 소멸되어 휘발성을 가지고 있으며,
동적배열은 생성과 해제 할 방식은 자신이 어떻게 호출하냐에 따라 생성되거나 소멸한다.
이러한 연속된 배열은 똑같은 유형 데이터의 반복적인 배열을 가졌기때문에 다양한 연산에서 동일한 성능을 보여주며, 이런 배열들은 C 언어에서부터 도입되었기 때문에 C 스타일 배열이라고도 한다고 한다.
차이점이라고 말하면
정적 배열은 스택(stack) 메모리 영역에 할당되기 때문에 함수를 벗어날 때 자동으로 해제되고,
동적 배열은 힙(heap) 영역에 할당되기 떄문에 사용자가 직접 해제하기 전까지 유지된다.
배열 같은 연속된 자료 구조에서 각 원소는 서로 인접해 있기 때문에 하나의 원소에 접근할 때 그 옆에 있는 원소 몇 개도 함계 캐시(cache)로 가져온다. 그렇게 가져온 캐시로 작업은 매우 빠르게 동작한다. 이러한 속성을 캐시 지역성(cache locality)이라고 한다.
어떤 연산의 점근적 시간 복잡도(asymptotic time complexity)계산에는 영향을 주지 않지만 실제 동작에서 배열처럼 연속된 원소에 매우 빠르게 접근할 수 있다는 점은 큰 장점이 된다.
배열에서 모든 원소에 순차적으로 접근하는 경우, 첫 번째 원소를 가져온 후 다음 원소는 캐시에서 바로 참조할 수 있으므로 배열은 캐시 지역성이 좋다고 말할 수 있다.
연결된 자료 구조.
연결된 자료 구조는 노드(node)라고 하는 여러 개의 메모리 청크에 데이터를 저장하며, 이 경우 서로 다른 메모리 위치에 데이터가 저장된다.
위와 같은 형태를 연결 리스트(linked list)라고 한다.
이런 연결 리스트는 메모리의 연속적인 형태가 아닌 해당 방문하고 있는 위치의 노드에는 다음 노드로 향하는 포인터가 저장되어 있는거다.
그래서 만약 자신이 원하는 i번째 원소로 이동하기 위해서는 포인터로 계속 이동하며 i번쨰 만큼 이동하는 것이다.
그러므로 원소 접근 시간은 노드 개수에 비례하기때문에, 시간 복잡도로 표현하면 O(n)으로 표현한다.
연결리스트는 포인터를 사용하기 때문에 배열과 달리 원소 삽입 또는 삭제를 빠르게 수행할 수 있다.
새로운 노드를 삽입하기 위해서 해당 삽입하고자 하는 노드를 포인터로 가르치는 위치의 데이터를 지운후에 그 위치에 삽입하고자 하는 위치에 노드를 넣어준다. 그 다음에는 새로 삽입된 노드의 포인터를 전에 있던 노드를 다시 가리키며 연결리스트로 만들어 주는것이다.
연결 리스트에서는 원소가 메모리가 연속적으로 저장되지 않기 때문에 캐시 지역성을 기대할 수 없다. 즉, 현재 노드가 다음 노드에 직접 방문하지 않는한 다음 원소 캐시를 가져올 방법이 없다.
따라서 배열과 연결 리스트에서 모든 원소를 차례대로 방문하는 작업은 이론적으로 같은 시간 복잡도를 가지지만, 실제로는 연결 리스트의 성능이 조금 떨어진다.
비교.
| 파라미터 | 배열 | 연결 리스트 |
| 임의 접근 | O(1) | O(n) |
| 맨 뒤에 원소 삽입 | O(1) | O(1) |
| 중간에 원소 삽입 | O(n) | O(1) |
| 캐시 지역성 | 있음 | 없음 |
배열과 연결 리스트는 매우 범용적이며 많은 응용 프로그램에서 데이터를 저장하는 용도로 사용되고 있다.
그러므로 자료 구조 구현과정에서 버그가 없어야 하며, 최대한 효율적으로 동작해야 한다.
그래서 C++에서는 std::array, std::vector, std::list 등 다양한 자료 구조 클래스를 제공한다.
단점.
C 스타일 배열은 배열 역할을 제대로 수행하기도 하지만 그다지 실용성이 없다고 한다. 그에 준한 단점 몇 가지가 있다.
- 메모리 할당과 해제를 수동으로 처리해야 한다. 메모리를 해제하지 못하면 메모리 릭(memory leak)이 발생할 수 있고, 이 경우 해당 메모리 영역을 사용할 수 없다.
- [ ] 연산자에서 배열 크기보다 큰 원소를 참조하는 것을 검사하지 못한다. 잘못 사용하면 세크멘테이션 결함(segmentation fault) 또는 메모리 손상으로 이어질 수 있다.
- 배열을 중첩해서 사용할 경우, 문법이 너무 복잡해서 코드를 이해하기 어렵다.
- 깊은 복사(deep copy)가 기본으로 동작하지 않는다. 이러한 동작은 수동으로 구현해야 한다.