2.2.3 리스트

리스트(list)는 StringBuilder의 작동 방식과 비슷하게 크기가 가변적인 배열처럼 동작한다. 거의 모든 곳에서 배열 대신 리스트를 사용할 수 있지만 불필요한 성능 저하가 발생할 것이다. 배열은 직접 액세스를 사용하는 반면 리스트에서는 인덱스된 액세스를 사용하는데, 이는 가상 함수를 호출하기 때문이다.

객체 지향 프로그래밍에는 다형성이라는 좋은 특징이 있다. 다형성은 객체의 인터페이스 변경 없이도 기본 구현에 따라 객체가 동작할 수 있다는 것을 의미한다. IOpenable 인터페이스 타입을 가진 변수 a가 있다고 하자. 할당된 객체의 유형에 따라 a.Open() 함수는 파일을 열거나 네트워크를 연결할 수 있다. 이는 객체 초반에 해당 유형으로 호출할 가상 함수와 매핑한 테이블을 참조함으로써 이뤄진다. 이때 테이블을 가상 메서드 테이블 또는 줄여서 vtable이라고 한다. 이렇게 하면 Open 함수가 동일한 유형의 모든 객체에 있는 가상 테이블의 동일한 항목으로 매핑되겠지만, 테이블에서 실제 값을 찾을 때까지는 해당 항목이 어디로 이어질지 알 수 없다.

정확히 무엇을 호출할지 모르기 때문에 이를 가상 호출이라고 한다. 가상 호출은 가상 메서드 테이블에서 추가로 조회해야 하므로 일반 함수 호출보다 약간 느리다. 함수 호출 몇 번이 크게 문제가 되는 건 아니지만 알고리즘 내에서 수행되면 오버헤드가 다항적으로 증가할 수 있다. 따라서 초기화 이후 리스트 크기가 증가하지 않는 경우에는 로컬 스코프의 리스트 대신 배열을 사용할 수 있다.