효과적인 STL에서
벡터는 기본적으로 사용해야하는 시퀀스 유형입니다.
무슨 뜻입니까? 효율성을 무시하면 vector아무것도 할 수 없는 것 같습니다 .
아무도 vector실현 가능한 옵션이 아니지만 list사용해야 하는 시나리오를 제공 할 수 있습니까?
답변
시퀀스의 끝을 제외한 모든 위치에 반복적으로 많은 항목을 삽입하려는 상황.
각기 다른 유형의 컨테이너에 대한 복잡성 보장을 확인하십시오.
답변
벡터:
- 연속 메모리.
- 미래 요소를위한 공간을 미리 할당하므로 요소 자체에 필요한 것 이상의 추가 공간이 필요합니다.
- 각 요소에는 요소 유형 자체에 대한 공간 만 필요합니다 (추가 포인터 없음).
- 요소를 추가 할 때마다 전체 벡터에 대한 메모리를 다시 할당 할 수 있습니다.
- 끝에 삽입은 일정하고 상각 된 시간이지만 다른 곳에서는 삽입에 비용이 많이 드는 O (n)입니다.
- 벡터 끝의 소거는 일정한 시간이지만 나머지는 O (n)입니다.
- 해당 요소에 무작위로 액세스 할 수 있습니다.
- 벡터에 요소를 추가하거나 제거하면 반복자가 무효화됩니다.
- 요소 배열이 필요한 경우 기본 배열을 쉽게 얻을 수 있습니다.
명부:
- 비 연속 메모리
- 사전 할당 된 메모리가 없습니다. 목록 자체의 메모리 오버 헤드는 일정합니다.
- 각 요소에는 목록의 다음 및 이전 요소에 대한 포인터를 포함하여 요소를 보유하는 노드를위한 추가 공간이 필요합니다.
- 요소를 추가한다고해서 전체 목록에 메모리를 다시 할당 할 필요는 없습니다.
- 삽입과 소거는 목록에서 어디서나 발생하더라도 저렴합니다.
- 목록과 스 플라이 싱을 결합하는 것이 저렴합니다.
- 요소에 무작위로 액세스 할 수 없으므로 목록에서 특정 요소를 얻는 데 많은 비용이 듭니다.
- 반복자는 목록에서 요소를 추가하거나 제거하더라도 유효합니다.
- 요소의 배열이 필요한 경우 기본 배열이 없으므로 새 요소를 작성하고 모두 추가해야합니다.
일반적으로 사용중인 순차 컨테이너 유형에 신경 쓰지 않을 때 벡터를 사용하지만 컨테이너 이외의 다른 곳에서 많은 삽입 또는 삭제를 수행하는 경우 벡터를 사용하십시오. 목록을 사용하십시오. 또는 임의 액세스가 필요한 경우 목록이 아닌 벡터를 원할 것입니다. 그 외에는 응용 프로그램에 따라 자연스럽게 하나 또는 다른 것이 필요한 경우가 있지만 일반적으로 좋은 지침입니다.
답변
요소를 자주 삽입 할 필요가 없으면 벡터가 더 효율적입니다. 목록보다 CPU 캐시 지역성이 훨씬 뛰어납니다. 즉, 하나의 요소에 접근하는 것은 그것을 만드는 아주 다음 요소가 캐시에 존재하고 느린 RAM을 읽을 필요없이 검색 할 수 가능성이 높습니다.
답변
여기에있는 대부분의 답변에는 중요한 세부 사항이 하나 없습니다.
컨테이너에 무엇을 보관하고 싶습니까?
ints 모음 인 std::list경우 재 할당 할 수 있는지 여부에 관계없이 모든 시나리오에서 잃어 버릴 수 있습니다. 앞면에서만 제거합니다. list<int>뛰는 예제를 준비하는 것은 매우 어려울 것 vector<int>입니다. 그리고 그렇다하더라도, deque<int>크지 메모리 오버 헤드를해야합니다 목록의 사용을 justyfing, 더 나은 또는 가까운 수 있습니다.
그러나 대량의 추악한 데이터를 처리하고 그중 일부를 처리하는 경우 재 할당으로 인해 삽입 및 복사 할 때 전체적으로 할당하지 않으려는 경우 재앙이 될 수 있습니다. list<UglyBlob>보다 vector<UglyBlob>.
그래도 vector<UglyBlob*>또는로 전환하면 vector<shared_ptr<UglyBlob> >다시-목록이 뒤쳐집니다.
따라서 액세스 패턴, 대상 요소 수 등은 여전히 비교에 영향을 미치지 만 내 견해로는 요소 크기-복사 비용 등이 있습니다.
답변
std :: list의 특별한 기능 중 하나는 스 플라이 싱 (일부 또는 전체 목록을 링크하거나 다른 목록으로 이동)입니다.
또는 내용이 복사하는 데 비용이 많이 드는 경우 일 수 있습니다. 이러한 경우 컬렉션을 목록으로 정렬하는 것이 더 저렴할 수 있습니다.
또한 모음이 작고 내용을 복사하는 데 비용이 많이 들지 않으면 어디에서나 삽입하고 지우더라도 벡터가 여전히 목록보다 성능이 우수 할 수 있습니다. 목록은 각 노드를 개별적으로 할당하며 몇 개의 간단한 객체를 옮기는 것보다 비용이 많이들 수 있습니다.
나는 매우 어려운 규칙이 있다고 생각하지 않습니다. 컨테이너와 관련하여 주로 수행하려는 작업과 컨테이너의 크기 및 포함 된 유형에 따라 다릅니다. 벡터는 일반적으로 그 내용을 단일 연속 블록으로 할당하기 때문에 목록보다 우선합니다 (기본적으로 동적으로 할당 된 배열이며 대부분의 경우 배열은 많은 것들을 보유하는 가장 효율적인 방법입니다).
답변
글쎄, 내 수업의 학생들은 벡터를 사용하는 것이 더 효과적 일 때 나에게 설명 할 수없는 것처럼 보이지만 목록을 사용하도록 조언 할 때 그들은 매우 행복해 보입니다.
이것이 내가 이해하는 방법입니다
목록 : 각 항목에는 다음 또는 이전 요소에 대한 주소가 포함되어 있으므로이 기능을 사용하면 정렬되지 않아도 항목을 무작위로 지정할 수 있습니다. 순서가 변경되지 않습니다. 메모리가 조각난 경우 효율적입니다. 그러나 또 다른 큰 장점이 있습니다. 포인터를 변경하면 항목을 쉽게 삽입 / 제거 할 수 있습니다. 단점 : 임의의 단일 항목을 읽으려면 올바른 주소를 찾을 때까지 한 항목에서 다른 항목으로 이동해야합니다.
벡터 : 벡터를 사용할 때 메모리는 일반 배열처럼 훨씬 더 체계적으로 구성됩니다. 각 n 번째 항목은 (n-1) 번째 항목 바로 뒤에 그리고 (n + 1) 번째 항목 앞에 저장됩니다. 왜 목록보다 낫습니까? 빠른 임의 액세스를 허용하기 때문입니다. 방법은 다음과 같습니다. 벡터에서 항목의 크기를 알고 메모리에서 연속적인 경우 n 번째 항목의 위치를 쉽게 예측할 수 있습니다. 원하는 항목을 읽기 위해 목록의 모든 항목을 찾아 볼 필요는 없습니다. 벡터를 사용하면 목록을 직접 읽을 수없고 목록을 읽을 수 없습니다. 반면에 벡터 배열을 수정하거나 값을 변경하면 속도가 훨씬 느려집니다.
메모리에 추가 / 제거 할 수있는 개체를 추적하는 데 목록이 더 적합합니다. 대량의 단일 항목에서 요소에 액세스하려는 경우 벡터가 더 적합합니다.
목록이 어떻게 최적화되는지는 모르겠지만 빠른 읽기 액세스를 원한다면 벡터를 사용해야합니다 .STL이 목록을 얼마나 잘 작성하면 벡터보다 읽기 액세스가 빠르지 않기 때문입니다.
답변
기본적으로 벡터는 자동 메모리 관리 기능이있는 배열입니다. 데이터가 메모리에 인접 해 있습니다. 중간에 데이터를 삽입하는 것은 비용이 많이 드는 작업입니다.
목록에서 데이터는 관련없는 메모리 위치에 저장됩니다. 중간에 삽입하는 것은 새로운 데이터를위한 공간을 만들기 위해 일부 데이터를 복사하는 것을 포함하지 않습니다.
더 구체적으로 귀하의 질문에 대답하기 위해이 페이지를 인용 하겠습니다
벡터는 일반적으로 요소에 액세스하고 시퀀스의 끝에서 요소를 추가하거나 제거하는 데 가장 효율적입니다. 끝 이외의 위치에 요소를 삽입하거나 제거하는 작업의 경우 deques 및 list보다 성능이 저하되고 목록보다 일관된 반복자 및 참조가 적습니다.