벡터를 일시적으로 정렬하는 좋은 방법은 무엇입니까?

Question

특정 작업에 대해 선택된 알고리즘으로 정렬해야하지만, 원래 상태 (예 : 항목을 입력 할 때 주문한 항목)는 그대로 유지해야하는 std :: vector가 있습니다.

분명히 내가 임시 벡터를 만들고 정렬 할 수있는 std :: copy 사용할 수 있지만 입력 한 항목을 타임 스탬프로 아마도 더 나은 방법이 있는지 궁금하네요.

건배

Answer 1

첫 번째 벡터의 모든 인덱스를 유지하는 표준 : : 벡터를 만들 수 있습니다. 그런 다음 색인 벡터를 원하는대로 정렬 할 수 있습니다. 이것은 가장 빠르며 가장 중요한 것은 첫 번째 벡터를 복사해야한다는 것을 의미하지는 않습니다 (아마도 더 많은 비용이들 것입니다).

Answer 2

주어진 벡터는 항상 한 번에 한 가지 방법으로 정렬됩니다.

임시 벡터 복사 및 종류와 원하는 :

는 두 가지 대안이있다. 벡터가 매우 크지 않고 공간이 제한되어 있지 않다면, 이것이 가장 확실한 방법입니다. 퍼포먼스가 걱정된다고하더라도, 복사본을 만드는 비용은 정렬 비용보다 작을 것이고, 복사 비용이 중요하다면 정렬은 복사보다 훨씬 느릴 것입니다.

또는 벡터를 원래의 순서로 다시 정렬 할 수있는 방법 (사용자가 언급 한 타임 스탬프)을 유지할 수 있습니다. 벡터가 매우 큰 경우에만이 작업을 수행하기를 원하기 때문에이 작업은 느려질 것입니다. 그러나 임시 벡터를 만들 수없는 경우이를 수행하는 유일한 방법입니다.

Answer 3

정렬 할 항목이 무엇이든 여러 정렬 필드가있는 구조로 묶을 수 있습니다.

struct someThing 
{ 
    int sortOrder1; 
    int sortOrder2; 
    ... 
    int sortOrderN; 
    //payload data object here 
} //note: this code may have some sytax errors (I haven't actually tried compiling this ;), but hope the idea is clear 

(또는 어쩌면 기본 구조 자체에 정렬 순서를 추가?)

을 그런 다음 다른 정렬 순서를 계산하고 다시 주문 할 수있는 정렬 순서에 필요한 따라 목록을 필요로 할 때 .

Answer 4

Boost를 조금이라도 신경 쓰지 않는다면 MultiIndex 라이브러리를 사용할 수 있습니다. 나와 예제 코드를 찾을 수있는 this answer을 참조하십시오.

기본적으로 동일한 데이터의 여러 '보기'를 서로 다른 순서로 유지할 수 있습니다. 귀하의 경우에는 데이터가 삽입 순서 (벡터와 같은)와 데이터가 어떤 기준 (예 :지도)에 따라 정렬 된 "정렬 된"보기 인 "시퀀스"보기를 유지할 수 있습니다. .

Answer 5

원본 데이터에 대한 스마트 포인터를 각 vector에 저장하는 것이 좋습니다. std::vector을 사용하면 다양한 정렬 방법을 제공 할 수 있습니다. 또한 스마트 포인터를 사용하면 항목에 대한 모든 참조가 제거 될 때 자동으로 삭제됩니다.