STL 벡터 리스트

벡터

본질적으로 STL 벡터는 동적으로 크기를 변경할 수 있는 배열이다. 정규적인 C++ 표준에는 벡터의 내부적인 자료 구조에 대한 내용이 정의되어 있지 않지만, 수행 성능이나 인터페이스의 요구사항 측면을 고려한다면 구현에 쓰인 자료 구조의 종류는 몇 가지로 압축할 수 있다. 실제로 STL의 모든 버전들은 매우 비슷한 방식으로 구현되어 있으며 차이는 매우 사소한 편이다.

 

 

  벡터는 표준 C 배열과 거의 동일하게 작동한다. 그러나 배열과 달리 벡터는 동적으로 크기가 바뀔 수 있는데, 중요한 것은 그러한 크기 변경의 본성에 대해서 잘 알아두는 일이다.

 

  벡터는 주기적으로 메모리를 재할당하고 새 배열로 데이터를 전송할 수 있는 배열로 구현되어 있다. 여기서 프로그래머가 주목해야 할 부분은 두 가지인데, 첫 번째는 벡터가 현재 필요한 양 이상의 메모리를 할당할 수 있다는 점이다. "크기가 변할 수 있는 배열"이므로 당연하다. 두 번째로는 벡터의 끝에 하나의 요소를 추가하는 것은 상수적 시간으로 간주되나, 이는 상각된(amortized) 상수적 시간이라는 점이다. 즉 어떤 경우(배열이 꽉 찬 상태에서 새 요소를 추가하는 등)에는 새 메모리를 해재하는 데 추가적인 시간과 자원이 소모된다는 뜻이다. 물론 그러한 일이 항상 일어나지는 않는다. 구현에 따라서는 버퍼 용량이 넘치면 벡터가 현재 할당된 메모리의 두 배를 할당하기도 한다.메모리를 재할당하면 현재 벡터 안의 요소를 가리키는 반복자들이 무효화되므로 메모리 재할당이 언제 일어나는지 이해하는 것은 매우 중요하다. 우선 간단한 예제 코드를 본 다음 벡터의 내부 메모리 관리에 대해 좀더 자세히 이야기 하겠다.

 

리스트

 기본 STL 구조체들 중 가장 널리 쓰이는 것은 아마도 STL list 일 것이다. list 는 이중 연결 리스트로 구현되었다.  따라서 어떠한 요소 삽입이나 삭제도 상수적 시간으로 수행된다. 대신 벡터나 테크에서처럼 특정 요소에 임의로 접근하는 것은 불가능하다(요소들은 순차적으로 거쳐가야 원한는 요소에 도달할 수 있다.)

 

  STL 컨테이너의 한 가지 장점은 명명 규약이나 메서드 사용법이 매우 일관적이라는 사실이다. 한 종류의 컨테이너를 다루는 방법만 알면 나머지는 것들은 다루는 방법도 자동적으로 알게 되는 셈이다.

 

  리스트는 벡터보다도 더 다루기가 쉽다. push_front()와 push_back() 은 이름 그대로 행동하며 리스트를 루프로 돌리는 것 역시 벡터 예제에서 본 것과 정확히 동일한 방식으로 이루어진다. 다음 코드는 리스트에 대한 것인데, 벡터 클래스에 쓰인 부분의 기법들이 거의 그대로 적용되어 있다.

 

출처 : http://blog.naver.com/newpog/10001981369