`std::list::size()`는 항상 O(1)입니까?

list::size()는 정말 O(1)인가요?

한때 std::list::size는 사실이었지만 ()는 구현 전반에 걸쳐 다양한 복잡성을 보였지만 C 11은 해당 동작을 표준화했습니다. 컨테이너 요구 사항의 표 96은 모든 표준 컨테이너의 .size() 작업에 대해 일정한 복잡성(O(1))을 요구합니다.

그러나 주목할 만한 예외는 버전 5.0 이전의 gcc의 libstdc 구현입니다. C 11 표준 요구 사항에도 불구하고 해당 .size() 함수는 다음 발췌문에서 볼 수 있듯이 O(N) 알고리즘을 사용합니다.

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

이 결정은 libstdc 내의 최적화 고려 사항에서 비롯됩니다. 목록을 순회하는 대신 별도의 요소 수를 유지하면 표준 복잡성 요구 사항에 위배되지만 일부 사용 사례의 성능이 향상됩니다.

반면 Libc의 구현은 O(1)을 올바르게 준수합니다. 다음 코드 조각에서 설명한 것처럼 복잡성은 다음과 같습니다.

_LIBCPP_INLINE_VISIBILITY
size_type size() const _NOEXCEPT     {return base::__sz();}

...

__compressed_pair<size_type, __node_allocator> __size_alloc_;

_LIBCPP_INLINE_VISIBILITY
const size_type&amp; __sz() const _NOEXCEPT
    {return __size_alloc_.first();}

결론적으로 C 11 표준에서는 O(1) 복잡성을 요구합니다. std::list::size(), 버전 5.0 이전의 gcc의 libstdc 구현은 예외적으로 남아 있으며 대신 O(N) 알고리즘을 사용합니다.

위 내용은 `std::list::size()`는 항상 O(1)입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!