stl 목록 - 복잡성

Question

목록의 모든 삽입 (일정)은 일정합니까?

액세스 권한은 무엇입니까?

앞, 뒤로 일정한 시간?

목록 중간에 - 선형 시간?

Answer 1

http://www.sgi.com/tech/stl/List.html

목록은 이중 연결리스트이다. 즉, 순방향 및 역방향 탐색, 시작 또는 끝 또는 중간에 요소의 (상각 된) 상수 시간 삽입 및 제거를 모두 지원하는 시퀀스입니다. 목록은 삽입 및 접합 요소를 나열하는 반복자를 무효화하지 않는 중요한 속성이, 심지어 제거 당신이려고하는 경우에, 액세스에 관해서

을 제거하는 요소를 가리만을 반복자를 무효화하는 것이 가운데 어딘가에서 요소를 검색하면 선형 시간이 걸립니다. 하지만 일단 반복자가 있으면 일정한 시간에 액세스 할 수 있으며 다른 삽입이나 제거로 인해 무효화되지는 않습니다.

Answer 2

삽입물 은 std::list에서 일정 시간 동안 작동합니다.

삽입하기 전에 삽입하려는 위치로 반복자를 가져와야합니다. 앞이나 뒤에 대해 이야기하지 않는 한 선형 시간 작업입니다.

Answer 3

std::list<>에 단일 요소를 삽입하면 삽입 위치에 관계없이 일정한 시간이 걸립니다. std::list<>은 본질적으로 정렬 된 컨테이너가 아니므로 새 요소를 삽입 할 위치를 정확하게 지정해야합니다. 당연히, 시간은 선형이다.

삽입 ("접합") 요소이 하나로 또 다른리스트에서 옮겼 [부] 서열 (즉 std::list<>::splice 법) (삽입 된 소자의 수에 선형) 일정 시간 또는 선형 시간 중 걸린다. std::list<> 경우, 구현은 선택의 여지가 있기 때문에 이러한 문제가 발생 중 하나

(1) 일정한 시간에 std::list<>::size 방법을 구현하고, 선형 시간에 std::list<>::splice, 또는

(2) 구현 std::list<>::splice 방법을 구현하여 비용을 지불

상수 시간을 계산하고 선형 시간으로 std::list<>::size을 구현하여이를 지불해야합니다.

두 가지 중 하나를 가질 수도 있지만 둘 다 가질 수는 없습니다. 특정 접근 방식을 따르는 결정은 구현에 달려 있습니다.

Answer 4

그것이 C++ 표준 23.2.2/(1)에 의해 보장된다

list는 양방향 반복자를 지원 어디 시퀀스 내에 소거 동작을 일정 시간 삽입 가능하고 시퀀스의 일종 스토리지 관리가 자동으로 처리됩니다. 벡터 (23.2.4) 및 deques (23.2.1)와 달리 목록 요소에 대한 빠른 임의 액세스는 지원되지 않지만 많은 알고리즘에만 은 순차적 액세스가 필요합니다.이론적으로는 다른 방법으로 주위해야 심지어 std::vector 종종 빠른 std::list보다 주로 실제로 데이터의 더 나은 지역에,

Answer 5

참고. 따라서 기본 순차 컨테이너는 std::vector이어야합니다. 당신이 의심하는 경우

, 해당 컨테이너는 모든에서 중요 여부를 첫 번째 측정 (그 부분은 전체 시간의 2 %를 사용하는 경우, 코드 조각의도 열 번 속도를 증가에서 아무 소용) std::list과 std::deque으로 측정 값을 비교하여 선택하십시오.