어떻게 std :: vector에서 임의로 삭제하면 std :: list보다 빠릅니까? 내가 속도를 높이려면 무작위 요소를 마지막 요소와 교환 한 다음 마지막 요소를 삭제하는 것입니다. 랜덤 삭제가 생성 된 이후 목록이 더 빠르다고 생각했을 것입니다. (초)std :: vector에서 무작위 삭제가 어떻게 std :: list보다 빠릅니까?
for(int i = 500; i < 600; i++){
swap(vector1[i], vector1[vector1.size()-1]);
vector1.pop_back();
}
for(int i = 0; i < 100; i++){
list1.pop_front();
}
결과 :
VEC 스왑 삭제 : 삭제 정상 0.00000909461232367903
목록 : 0.00011785102105932310
당신이하고있는 것은 비록 임의 삭제되지 않습니다. 끝에서부터 삭제하고있는 것입니다. 이것은 벡터가 무엇을 위해 만들어 졌는지 (다른 것들 중에서)입니다.
스와핑 할 때 임의의 색인 생성 작업을 수행하고 있습니다 (도).
이것은 임의적이지 않습니다. 시도하십시오 vector1.erase (vector.begin() + rand() % vector.size()); 대신.
나는 그것이 사실 무작위로 알고 있지만 목적은 목록이나 벡터가 진정으로 무작위 삭제가 많은 프로그램에 가장 적합한 지 확인하는 것이 었습니다. 나는 그 방법이리스트보다 느리다는 것을 안다. –
목록 erase은 삭제 된 목록 요소를 삭제하게되며 delete 연산자에 대한 호출을 호출합니다. 벡터 지우기는 단지 스왑을 일으킨 다음 정수를 감소시킵니다. 이것은 훨씬 빠릅니다.
지우기를 쓰면 pop_back을 의미합니까? AFAIK pop_back()이 기본 배열을 스와핑하지 않습니다 (즉, 시간이 많이 걸리기 전에이 배열을 만들었습니다). 벡터의 크기를 줄이면 소멸자가 호출됩니다. –
사실, 제가 기억하는 한, 벡터 자체가 결코 자르지 않습니다. 스콧 메이어 (Scott Meyer)에 의해 호출 된 "스왑 트릭"을 구현해야하며 이번에는 다른 벡터 인스턴스와 함께 ** 용량 **을 최대한 줄여야합니다. –
예, 죄송합니다. 나는 pop_back 및 pop_front 호출을 의미했습니다.목록의 경우 지우기 측면에서 구현됩니다 –
실제로 속도를 더 높이려면 이터레이터을 통해 벡터의 요소를 인덱싱해야합니다. 이 아키텍처는 일부 아키텍처에서 더 우수한 성능을 제공하는 것으로 알려져 있습니다.
거기에 정성을 기울이시는 건가요? –
아키텍처에 포인터 + 인덱스 메모리 액세스 모드가없는 경우 및/또는 현재 수행중인 작업에 대한 레지스터가 부족한 경우 인덱스를 통해 액세스 할 때 추가 명령어 나 액세스가 필요한 상황이 발생할 수 있습니다 포인터/반복자. 물론 루프 상태에서 end()를 호출하면 컴파일러가 루프 외부에서 최적화하지 못하거나 잃을 수 있습니다. –
std::list과 std::vector의 차이점은 단순히 성능에 미치지 못합니다. 그들은 또한 다른 반복자 무효화 의미론을 가지고있다. std::list에서 항목을 지우면 목록의 다른 항목을 가리키는 모든 이터레이터가 유효합니다. 따라서 std::vector을 사용하면 항목을 지우면 해당 항목을 가리키는 모든 반복자가 무효화됩니다. (일부 구현에서는 여전히 유효한 반복자 역할을 할 수 있지만 표준에 따르면 현재 사용할 수 없으며 사용하려고하면 검사 구현이 어설 션해야합니다.)
컨테이너 선택은 다음과 같습니다. 당신이 요구하는 의미론으로하십시오.
참으로. 나는 임의적 인 것을 보지 못했다. –
그렇다면 단일 스왑을 사용하면 벡터가 더 빨라지고 임의 액세스가 가능할 때 std :: list의 목적은 무엇입니까? –
벡터를 순서대로 유지하고자하는 경우에 따라 달라집니다. –