effective stl item2 : Beware the illusion of container-independent code

item2의 주제는 컨테이너의 사용에 있어 코드의 독립적일 수 있을 거라는 환상을 조심하라 입니다.

우선 모든 STL은 템플릿이 가능하도록 설계되어 있습니다.

다시말해 STL로부터 얻을 수 있는 pointer,iterator, function 역시 템플릿되어 사용이 가능합니다.

때문에 이를 기초로 클래스등을 설계하면서 사용하는 STL을 선택하는데 주의를 필요로 합니다.

가령 라이브러리를 만들고 나서 개발자들이 이를 사용한다고 가정합니다.

하지만 추후에 라이브러리를 수정하면서 내부에서 사용하는 STL을 vector에서 map으로 바꿉니다.

물론 인터페이스는 그대로 이기에 사용자가 라이브러리의 클래스를 사용하거나 함수를 호출하는데

변경은 없습니다. 하지만 내부의 자료구조가 위 처럼 sequence container에서 associative container로 변경되면서 

바뀔 시간,공간 복잡도는 어떻게 될까요?

insert를 예로 들어봅시다.

vector에서 insert와 map의 insert는 시간복잡도로나 구현이 천치자치입니다.

vector의 insert는 시간복잡도가 O(N)입니다. 또한 삽입 되는 position의 뒤의 원소를 모두 한칸씩 뒤로 미뤄야합니다.

이때마다 type의 copy constructor가 발생합니다. 또 만약 이미 할당된 공간이 꽉 차있으면 reallocation이 발생하는건 어떻구요?

(게다가 이떈 iterator invalidation이 발생합니다.)

하지만 map의 insert는 어떨까요. 우선 시간 복잡도는 일반적으로 O(logN)입니다. 또 map은 내부적으로 

balancing tree를 이용하기때문에 원소들의 위치가 항상 바뀔 수 있습니다. 

또한 vector에 비해 iterator invalidation이 발생하지 않구요.

이렇듯 시간, 공간복잡도가 크게 달라집니다. 이러한 상황은 라이브러리의 사용에 있어 사용자에게 책임을 전가 시키는 일이 될 수 있습니다.

때문에 STL은 코드에 독립하여 사용되기는 불가능하게 됩니다.

다시말해, 사용자는 어떤 container를 사용하느냐에 따라 성능이 종속적이게 된다는 점입니다.