list :: size () 정말 O (n)입니까?

list :: size () 정말 O (n)입니까?

---

최근에 나는 std::list::size()선형 복잡성이 있다고 언급하는 사람들을 발견했습니다 . 일부 출처
에 따르면 표준이 복잡성이 무엇인지 말하지 않기 때문에 실제로 구현에 따라 다릅니다. 이 블로그 항목 의 댓글 은 다음과 같습니다 .

실제로 사용중인 STL에 따라 다릅니다. Microsoft Visual Studio V6는 size ()를 {return (_Size); } 반면 gcc (적어도 3.3.2 및 4.1.0 버전에서는) {return std :: distance (begin (), end ()); } 첫 번째는 일정한 속도를, 두 번째는 o (N) 속도를 갖습니다.

1. 그래서 제 생각에는 VC ++ 군중의 경우 size()Dinkumware가 VC6 이후로 그 사실을 변경하지 않았기 때문에 지속적인 복잡성이 있습니다. 내가 바로 거기 있습니까?
   
2. 현재 어떤 모습 gcc입니까? 이것이 정말로 O (n)이라면, 개발자들은 왜 그렇게하기로 선택 했습니까?

---

C ++ 11 이전 답변

표준이 list :: size ()의 복잡성이 무엇인지 명시하지 않는다는 것이 맞습니다. 그러나 "일정한 복잡성을 가져야합니다"(표 65의 참고 A)를 권장합니다.

다음은 일부 사람들이 list :: size ()가 O (N) 복잡성을 가져야한다고 생각하는 이유를 설명 하는 Howard Hinnant의 흥미로운 기사입니다 (기본적으로 O (1) list :: size ()가 list :: splice ()가 O (N) 복잡성) 및 O (1) list :: size ()가 좋은 아이디어 인 이유 (저자의 의견) :

• http://howardhinnant.github.io/On_list_size.html

논문의 요점은 다음과 같습니다.

• 내부 카운트를 유지하면 list::size()O (1)이 될 수있는 상황이 거의 없어 접합 작업이 선형이됩니다.
• 누군가가 O (N)을 호출하기 때문에 발생할 수있는 부정적인 영향을 인식하지 못하는 상황이 더 많이있을 수 있습니다 size()(예 : list::size()잠금을 유지하는 동안 호출되는 그의 한 예 ).
• size()'최소한의 놀라움'을 위해 O (N) 을 허용하는 대신 표준은 size()O (1) 방식으로 구현하는 모든 컨테이너를 요구해야합니다 . 컨테이너가이를 수행 할 수 없으면 전혀 구현하지 않아야 size()합니다. 이 경우 컨테이너 사용자 size()는 사용할 수 없음을 인식 하고 컨테이너의 요소 수를 계속 원하거나 가져와야 container::distance( begin(), end())하는 경우 해당 값을 가져 오는 데 사용할 수 있지만 O (N) 연산.

나는 그의 추론의 대부분에 동의하는 경향이 있다고 생각합니다. 그러나 나는 그가 제안한 splice()과부하 에 대한 추가를 좋아하지 않습니다 . 올바른 동작을 얻기 위해 를 전달 n해야하는 것은 distance( first, last)버그를 진단하기 어려운 레시피처럼 보입니다.

변경 사항이 기존 코드에 중대한 영향을 미치기 때문에 앞으로 무엇을해야하는지, 무엇을해야할지 잘 모르겠습니다. 그러나 현존하는 코드는 이미 영향을 받았다고 생각합니다. 잘 정의되어야하는 것에 대한 동작은 구현마다 상당히 다를 수 있습니다. 크기가 '캐시'되고 알려진 / 알 수 없음으로 표시된 것에 대한 onebyone의 의견이 잘 작동 할 수 있습니다.-당신은 상각 된 O (1) 동작을 얻습니다-O (N) 동작을 얻는 유일한 시간은 일부 splice () 작업에 의해 목록이 수정 될 때입니다. . 이것에 대한 좋은 점은 표준을 변경하지 않고 오늘날 구현자가 수행 할 수 있다는 것입니다 (내가 뭔가 빠뜨리지 않는 한).

내가 아는 한 C ++ 0x는이 영역에서 아무것도 변경하지 않습니다.

---

C ++ 11에서는 모든 표준 컨테이너에 대해 .size()작업이 "일정한"복잡성으로 완료되어야합니다 (O (1)). (표 96-컨테이너 요구 사항). 이전 C ++ 03 에서는 복잡도가 일정 .size() 해야 하지만 필수는 아닙니다 ( std :: string size ()가 O (1) 작업입니까? 참조 ).

표준 변경은 n2923 : Specifying the complex of size () (Revision 1)에 의해 도입되었습니다 .

그러나 .size()libstdc ++ 의 구현은 gcc에서 최대 4.8까지의 O (N) 알고리즘을 계속 사용합니다.

  /**  Returns the number of elements in the %list.  */
  size_type
  size() const _GLIBCXX_NOEXCEPT
  { return std::distance(begin(), end()); }

c ++ 11에서 std :: list가 더 큰 이유 도 참조하십시오 . 왜 이런 식으로 유지되는지 자세히 알아보십시오.

업데이트 :std::list::size()이다 적절히 O (1) GCC 사용시 5.0 (또는 위) 모드 (11)에서 C ++.

---

그건 그렇고, .size()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& __sz() const _NOEXCEPT
    {return __size_alloc_.first();}

---

이전에 gcc 3.4의 list :: size를 살펴 봐야했기 때문에 다음과 같이 말할 수 있습니다.

1. std :: distance (head, tail)를 사용합니다.
2. std :: distance에는 두 가지 구현이 있습니다. RandomAccessIterator를 충족하는 유형의 경우 "tail-head"를 사용하고 InputIterator 만 충족하는 유형의 경우 "iterator ++"에 의존하는 O (n) 알고리즘을 사용하여 주어진 값에 도달 할 때까지 계산합니다. 꼬리.
3. std :: list는 RandomAccessIterator를 포화시키지 않으므로 크기는 O (n)입니다.

As to the "why", I can only say that std::list is appropriate for problems that require sequential access. Storing the size as a class variable would introduce overhead on every insert, delete, etc., and that waste is a big no-no per the intent of the STL. If you really need a constant-time size(), use std::deque.

---

I personally don't see the issue with splice being O(N) as the only reason why size is permitted to be O(N). You don't pay for what you don't use is an important C++ motto. In this case, maintaining the list size requires an extra increment/decrement on every insert/erase whether you check the list's size or not. This is a small fixed overhead, but its still important to consider.

Checking the size of a list is rarely needed. Iterating from begin to end without caring the total size is infinitely more common.

---

I would go to the source (archive). SGI's STL page says that it is permitted to have a linear complexity. I believe that the design guideline they followed was to allow the list implementation to be as general as possible, and thus to allow more flexibility in using lists.

---

This bug report: [C++0x] std::list::size complexity, captures in excruciating detail the fact that the implementation in GCC 4.x is linear time and how the transition to constant time for C++11 was slow in coming (available in 5.0) due to ABI compatibility concerns.

The manpage for the GCC 4.9 series still includes the following disclaimer:

Support for C++11 is still experimental, and may change in incompatible ways in future releases.

---

The same bug report is referenced here: Should std::list::size have constant complexity in C++11?

---

If you are correctly using lists you aren't probably noticing any difference.

Lists are good with big data structures that you want to rearrange without copying, of for data you want to keep valid pointers after insertion.

In the first case it makes no difference, in the second i would prefer the old (smaller) size() implementation.

Anyway std is more about correctness and standard behavious and 'user friendlyness' than raw speed.

참고URL : https://stackoverflow.com/questions/228908/is-listsize-really-on