std::list::size()는 모든 구현에서 실제로 O(1)입니까?

std::list::size(): 정말 O(n)?

몇몇 개인은 std: :list::size()는 선형 복잡성을 가지고 있으며 복잡성에 대한 진실은 구현에 따라 다릅니다. C 표준은 이 함수에 대한 복잡성 요구 사항을 지정하지 않습니다.

구현 변형

• Microsoft Visual Studio VC: 이전 버전 (예: VC6), size()는 단순히 내부 데이터 구조에 저장된 크기를 반환했기 때문에 실제로 지속적인 복잡성을 가졌습니다.
• GNU 컴파일러 컬렉션(GCC): 역사적으로(GCC 4.1.0까지) size()는 목록을 반복하여 요소 수를 계산하는 O(n) 접근 방식을 사용했습니다.

GCC의 현재 상태

C 11에서 C 표준은 std::list를 포함한 모든 표준 컨테이너에 대해 size() 작업을 요구합니다. , 일정한 복잡성(O(1))을 가져야 합니다. 이는 플랫폼과 구현 전반에 걸쳐 일관되고 효율적인 런타임 동작을 보장하기 위한 것입니다.

Libstdc의 구현

C 11 명령에도 불구하고 size() 구현은 libstdc(GCC에서 사용하는 표준 라이브러리)의 은 GCC 버전 4.8까지 O(n)으로 유지되었습니다. 이는 성능상의 이유와 목록 구조에서 추가 크기 필드를 유지하는 데 따른 오버헤드를 최소화하기 위해 수행되었습니다.

업데이트: O(1) GCC 5.0의 구현

GCC 5.0이 출시되면서 std::list에 대한 size() 구현이 마침내 C 11 모드에서 O(1) 복잡성을 달성하도록 최적화되었습니다. 이는 목록의 요소 수를 추적하는 내부 크기 필드를 도입하여 크기 정보에 대한 지속적인 액세스를 제공함으로써 달성되었습니다.

결론

std::list::size()의 복잡성은 과거에 논쟁의 주제였지만 현재 C 표준에서는 모든 표준 컨테이너에 대해 O(1) 복잡성을 요구합니다. GCC 5.0 이상 버전의 구현은 이 요구 사항을 준수하여 std::list.에 대한 size()

위 내용은 std::list::size()는 모든 구현에서 실제로 O(1)입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!