C++ std :: vector 요소를 사용하여 std :: vector 요소를 재정렬하십시오.

Question

std :: vector 요소를 재정렬하기 위해 새로운 알고리즘을 작성하려고 할 때이 문제가 발생했습니다. 기본적인 생각은 std :: vector를 가리키는 포인터의 목록이 *list.begin() == vector[0], *(++list.begin()) == vector[1] 등등이되도록하는 것입니다. 그러나 목록의 요소 위치를 수정하면 매핑이 중단됩니다. (추가 된 포인터 포함) 매핑이 깨졌을 때 목록의 요소는 임의의 순서로있을 수 있지만 벡터의 올바른 요소를 가리 킵니다. 작업은 벡터의 요소를 재정렬하여 매핑을 수정하는 것입니다.

가장 간단한 방법은 (내가 지금 일을 한 방법)을 수행하는 :

• 새로운 빈 표준 : : 벡터를 생성하고 기존의 벡터의 동일한 크기로 크기를 조정합니다.
• 목록을 반복하고 이전 벡터의 요소를 읽고 새 벡터에 쓰십시오. 새 벡터의 요소를 가리 키도록 포인터를 설정합니다.
• 벡터를 교체하고 이전 벡터를 해제하십시오.

슬프게도이 방법은 벡터에 더 많은 용량이 필요할 때만 유용합니다. 요소를 보유하고있는 현재 벡터가 모든 들어오는 요소를 저장할 수있는 충분한 용량을 가지고 있으면 비효율적입니다. 목록에 추가 된 포인터는 다른 벡터의 storgate를 가리 킵니다. 간단한 방법은 포인터 만 읽으므로이 방법이 효과적입니다.

그래서 일정한 양의 메모리를 사용하여 "적절한 위치에"벡터를 재정렬하고 싶습니다. 현재 벡터의 storgate를 가리키고 있지 않은 포인터는 현재 벡터의 storgate를 가리 키도록 이동됩니다. 요소는 단순한 구조입니다. (PODs) 시간이있을 때 예제 코드를 게시 해 봅니다.

이것을 수행하려면 어떻게해야합니까? 기본 아이디어는 끝났지 만 일정한 양의 메모리로 리오 더링을 수행 할 수 있는지 여부는 확실하지 않습니다.

---

추신 : 게시물에 잘못된 문법과 오타가 생겨서 죄송합니다. 아직도 읽을 수 있기를 바랍니다. :)

Answer 1

먼저 포인터 목록이 있습니까? std::distance(&v[0], *list_iter)으로 계산할 수있는 벡터에 인덱스를 유지할 수도 있습니다. 자, 먼저 인덱스의 벡터를 구축 할 수 있지만, 당신은 쉽게 그 직접 목록을 사용하여 적용 할 수 있습니다 :

std::vector<T> v;  // your data 
std::list<T*> perm_list; // your given permutation list 
std::vector<size_t> perms; 

perms.reserve(v.size()); 
for (std::list<T*>::const_iterator it = perm_list.begin(), end = perm_list.end(); it != end; ++it) 
{ 
    perms.push_back(std::distance(&v[0], *it)); 
} 

을 (한 줄에서이 작업을 수행 할 수 std::transform 및 std::bind, 또는 람다를 사용하는 방법은 아마이있다.)

이제 작업을 수행하십시오.

std::set<size_t> done; 

for (size_t i = 0; i < perms.size(); while(done.count(++i)) {}) 
{ 
    T tmp1 = v[i]; 
    for (size_t j = perms[i]; j != i; j = perms[j]) 
    { 
    T tmp2 = v[j]; 
    v[j] = tmp1; 
    tmp1 = tmp2; 

    done.insert(j); 
    } 
    v[i] = tmp1; 
} 

것은 내가 보조가 인덱스가 이미 순열되어있는 추적 done를 설정 사용하고 있습니다 : 우리가 진행하면서 우리는 단순히 순열의주기 분해를 사용하여, 우리는 perms 벡터를 수정합니다. C++ 0x에서는 이동 가능한 컨테이너에서이 작업을 수행하기 위해 어디서나 std::move을 추가합니다.