현대 C 구현에서 `std::list::size()`는 실제로 O(1)입니까?-C++-php.cn

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

Linda Hamilton

풀어 주다： 2024-11-16 10:57:03

원래의

921명이 탐색했습니다.

Is `std::list::size()` Truly O(1) in Modern C Implementations?

std::list::size()가 현대 구현에서 정말 O(n)인가요?

최근 일부 개발자는 다음과 같이 제안했습니다. std::list::size()는 선형 시간 복잡도(O(n))를 갖습니다. 그러나 C 표준에서는 복잡성이 정의되어 있지 않으며 구현에 따라 달라질 수 있습니다.

이전 버전의 C 표준(C 03)에서는 일정한 복잡성을 유지하기 위해 size() 연산을 권장했습니다. (O(1)). 그러나 C 11이 도입되면서 모든 표준 컨테이너에 대한 요구 사항이 되었습니다. C 11 표준의 표 96에는 .size()가 모든 컨테이너에 대해 일정한 복잡성을 가져야 한다고 명시되어 있습니다.

역사적으로 GCC의 libstdc 라이브러리는 std::distance(begin을 사용하여 복잡도 O(n)의 size()를 구현했습니다. (), end()), 귀하가 인용한 블로그 항목에 설명된 대로입니다. 그러나 C 11 모드에서는 이 동작이 변경되었습니다.

size_type
size() const _GLIBCXX_NOEXCEPT
{ return __size_alloc_.first(); }

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

로그인 후 복사

GCC 5.0 이상에서 size() 함수는 내부 데이터 구조를 사용하여 요소 수를 추적하여 효과적으로 작업을 수행합니다. 오(1). 이는 모든 표준 컨테이너에 대한 C 11 요구 사항에 부합합니다.

일부 틈새 사용 사례에서는 여전히 size()에 대해 O(n) 복잡성이 발생할 수 있지만 대다수 사용자의 경우 작업은 일정한 시간이어야 합니다.

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