STL vector vs list : 그래프 인접 목록에서 가장 효율적입니까?

Question

목록은 pushing_back 일 때 메모리를 할당하는 데 대부분의 시간을 소비합니다. 반면에 벡터는 크기 조정이 필요할 때 요소를 복사해야합니다. 따라서 어떤 컨테이너가 인접 목록을 저장하는 데 가장 효율적입니까?

Answer 1

나는 이것이 절대 확실성으로 대답 할 수 있다고 생각하지 않습니다. 그럼에도 불구하고, 나는 벡터가 더 잘할 확률은 90 % 이상이라고 추정 할 수 있습니다. 인접 목록은 인접 목록의 요소 순서가 (일반적으로) 중요하지 않기 때문에 사실 많은 벡터보다 많은 벡터를 선호합니다. 즉, 요소를 추가 할 때는 일반적으로 컨테이너의 끝까지, 요소를 삭제하면 컨테이너의 끝으로 바꿀 수 있으므로 끝에 추가하거나 삭제할 수 있습니다.

그렇습니다. 벡터는 요소가 확장 될 때 요소를 복사해야하지만 실제로는 거의 문제가되지 않습니다. 특히 벡터의 지수 증가율은 요소가 복사되는 평균 횟수가 상수로 향하는 경향이 있다는 것을 의미합니다. 일반적인 구현에서 상수는 약 3입니다.

정직하게 복사하는 것이 실질적인 문제입니다 (예 : 복사 요소가 극도로 비쌉니다). 벡터 이후의 다음 선택은 여전히 ​​목록이 아닙니다. 대신 std :: deque 대신에 std :: deque를 사용하는 것이 좋습니다. 이것은 기본적으로 객체 블록에 대한 포인터의 벡터입니다. 드물게 확장을하기 위해 무엇인가를 복사해야하는 경우는 드물지만 드물지만 복사해야하는 것은 객체가 아니라 포인터입니다. 양 끝점의 다른 고유 한 기능 (양쪽 끝에서 일정 시간에 삽입/삭제)이 필요하지 않은 경우 일반적으로 벡터가 더 나은 선택이지만 이케스는 거의 항상 목록보다 더 나은 선택입니다 (즉 벡터는 일반적으로 첫 번째 선택, 상당히 가까운 두 번째, 그리고 꽤 먼 마지막 목록) deque.

Answer 2

답변은 유스 케이스에 따라 다릅니다. 오후 8시 30 분 P.S. @quasiverse - 암시 적으로 또는 명시 적으로 ":: reserve"하는 메모리가 만기 될 때 벡터가 realloc을 호출합니다.

지속적으로 변경되는 인접성 목록 (삽입 및 삭제)이있는 경우 목록이 가장 적합합니다. 다소 정적 인 인접성 목록이 있고 트래버스/룩업을 수행하는 대부분의 경우 벡터가 최상의 성능을 제공합니다.

Answer 3

STL 컨테이너는 고정적으로 정의되지 않으므로 구현이 다릅니다. 조심하다면 코드를 작성하여 벡터 또는 사용중인 목록인지 여부를 신경 쓰지 않아도되고 더 빠르게 볼 수 있도록 시도 할 수 있습니다. 캐시 효과 등의 복잡성을 감안할 때 어떤 정확도로 상대 속도를 예측하는 것은 거의 불가능합니다.

Answer 4

이 비교에 세 번째 옵션 인 특수 할당자를 사용하여 목록을 추가 할 수 있습니다.

고정 크기의 작은 개체에 할당자를 사용하면 할당/할당 해제 속도가 크게 향상 될 수 있습니다 ...