stl 크기의 함정

작년에 처음 입사했을 때 회사 기본 라이브러리에 LRUCache가 있었고, 내부 구현에서는 std::list를 사용했습니다. 그러나 std::list를 계산하는 함수는 stl의 size() 메서드를 직접 사용합니다. 그 결과 스트레스 테스트 도중 성능이 여기서 정체됐다.
오늘 동료가 기본 라이브러리에서 std::list를 사용하는 또 다른 대기열 구현을 발견했습니다. 요소 수를 가져올 때도 size() 메서드가 사용되었습니다.
아쉽게도 회사 기본 라이브러리는 헤더 파일만 노출하고 있어, 이 피트가 다른 곳에 있을지는 일일이 확인이 불가능합니다.

stl의 size() 메소드 구현을 살펴보겠습니다.

size_type    
  size() const
      { return std::distance(begin(), end()); }

위 코드의 g++ 버전은 4.2.1입니다

분명히, 복잡도는 O(N)입니다. 목록에 요소가 많으면 계산 속도가 매우 느려집니다. 따라서 std::list를 사용할 때는 개수를 직접 유지해야 한다는 점을 기억해야 합니다.