(TIL) C++ List, Sequence …

오늘은 벡터, 리스트 등에 대해서 배웠다.

먼저 벡터는 다음과 같은 연산을 지원하는 배열 리스트이다.

• at(i), i번째 인덱스에 있는 원소를 반환한다.
• set(i, e) i번째 인덱스에 있는 원소를 e로 대체한다.
• insert(i, e) i번째 인덱스에 원소 e를 삽입한다. (만약에 기존 원소가 있으면 원소들을 오른쪽으로 한 칸씩 밀고 삽입한다.)
• erase(i) i번째 인덱스에 있는 원소를 삭제한다.

구현을 단순 배열로 할 수 있다. 다만 배열의 특성상 insert 연산이나 erase 연산이 있을 때에는 자리를 만들거나 빈 자리를 메우기 위해 모든 원소들을 다 움직여 줘야 한다. 그래서 이 두 연산의 시간복잡도는 O(N)이다.

STL에서도 vector라는 자료구조를 이미 제공한다. 사실 C++에서는 array보다 더 많이 쓰일 텐데 array와 비슷하게 동작하면서도 몇 가지 특징이 있다.

• array처럼 [] 연산자를 쓸 수 있다.
• array와 다르게 크기가 동적으로 변한다.
• array와 다르게 vector 객체가 소멸하면 저절로 소멸자를 호출해 메모리에서 제거한다. array는 프로그래머가 명시적으로 제거해주어야 한다.

리스트란 벡터나 배열처럼 인덱스를 기반으로 원소의 위치를 정하는 것이 아닌 ‘노드’를 기반으로 원소의 위치를 탐색하는 자료구조이다. 이미 이전에 배운 여러 종류의 연결리스트들이 그 예이다. 인덱스 기반의 탐색은 처음부터 훑어 올라가야 하는 반면 노드 기반의 탐색은 위치만 정해주면 즉시 그 위치에 접근하여 연산을 수행할 수 있기 때문에 비교할 수 없이 빠르다. 하지만 논할 문제점이 있다. 이런 노드 기반의 연산을 수행하기 위해 얼마나 많은 구현에 관한 정보가 노출되어야 하는지에 관한 문제이다. 직접 노드의 포인터를 노출시키면 사용자가 자료구조를 직접 수정할 수도 있게 된다. 그래서 ‘position’이라는 개념을 도입하고 원소에 단순히 접근하는 것뿐만이 아니라 모든 원소들을 나열하기 위해 반복자라는 개념을 도입한다.

position은 위치를 가리키는 추상 데이터 타입이고 position.element()라는 연산을 통해 그 위치에 있는 원소를 얻을 수 있다. 그리고 C++에서 * 연산자 오버로딩을 통해 position.element()가 아니라 *position 이런 식으로 원소를 조회하도록 할 수 있다.

반복자는 이 position의 확장 개념이다. 반복자는 next()나 prev() 연산을 통해 바로 다음 혹은 이전 원소로 이동할 수 있다. 이런 연산을 통해 반복자로 이루어진 리스트를 차례대로 탐색할 수 있다. 이 경우 탐색의 시작과 끝을 알기 위해 begin()과 end()를 지정해주어야 한다.

STL에서 vector를 제외한 나머지 container 클래스들은 iterator 클래스를 정의하고 있다. 이 container들을 순회하기 위해서는 array를 탐색하는 것처럼 인덱스를 통한 반복문으로는 할 수 없고 ++ 연산자를 사용해야 한다.

C++에서 Iterator를 통해 순회를 할 때 어떤 순회 함수의 인자로 container 자체를 넘길 수 있다. 그러나 managed 언어들과 다르게 이런 식으로 하면 container의 깊은 복사가 이루어져 함수의 인자로 넘어간다. 이럴 때 container 자체 대신에 container의 참조를 넘길 수 있는데 이것을 C++에서는 허용하지 않는다. 위에서 말했다 시피 포인터에 사용자가 접근하게 되면 자료구조 자체를 변형시킬 수도 있기 때문이다. 이때 사용할 수 있는 것이 상수 참조(constant reference)이다.

오늘은 여기까지… 251쪽까지 했다.