std :: partition을 사용하여 벡터 파티셔닝

Question

나는 피벗을 가로 지르는 배열을 파티셔닝합니다. std :: partition 함수를 사용해 보았습니다.

그러나 두 개의 시퀀스 중간에 피벗을 포함하고 싶습니다. 어떻게하면 std :: partition 또는 다른 방법으로 기본적으로이 작업을 수행 할 수 있습니까? 솔루션이 상대적으로 빠를 수 있도록 성능을 찾고 있습니다.

Answer 1

는 피벗 시퀀스의 마지막 요소 만들기의 마지막 요소를 제외한 모든과 std::partition()를 호출하고, 중간 지점은 분할 끝 swap() 장소의 요소와 다른 경우 :

sequence.push_back(pivot); 
auto mid = std::partition(sequence.begin(), sequence.end() - 1, 
          [&](int value){ return value < pivot; }); 
if (mid != sequence.end() - 1) { 
    std::swap(*mid, sequence.end()[-1]); 
} 

std::partition() 이후에 요소를 먼저 추가하면 std::partition()이 추가되어 적용되지 않고 시퀀스를 추가 할 필요가 없습니다.

pivot이 시퀀스에서 시작된 경우 처음에는 std::swap() 끝까지 읽은 다음 std::partition(), 그 다음은 가운데에 std::swap()이옵니다. 귀하의 목표가 뚱뚱한 파티션 인 경우 (즉, pivot과 같은 모든 요소가 가운데에 있어야 함) 이에 따라 후반부는 std::partition()이되어야합니다. 표준 C++ 라이브러리에는 팻 (fat) 파티션을 직접 수행하는 알고리즘이 없습니다.

Answer 2

나머지 요소에 대해 partition 번만 호출하면됩니다.

auto point = partition(sequence.begin(), sequence.end(), 
    [&](int value) { return value < pivot; }); 
partition(point, sequence.end(), [&](int value) { return value == pivot; }); 

내가 나서서 여기 알고리즘을 기반으로 세 방향 파티션을 구현 : 나는 의심 나는 두 번 파티션을 호출하는 방법에 대해 그것을 테스트 https://en.m.wikipedia.org/wiki/Dutch_national_flag_problem

template<typename IteratorT, typename ValueT> 
std::pair<IteratorT, IteratorT> 
three_way_partition(IteratorT _first, IteratorT _last, ValueT const& value) { 
    auto i = _first; 
    auto j = _first; 
    auto k = _last - 1; 
    while (j <= k) { 
     if (*j < value) { 
      std::swap(*i, *j); 
      ++i; 
      ++j; 
     } else if (*j > value) { 
      std::swap(*j, *k); 
      --k; 
     } else { 
      ++j; 
     } 
    } 

    return {i, j}; 
} 

, 그리고의 차이 성능은 무시할 만하 며 실제로 파티션 두 번 방법은 일반적으로 조금 빠릅니다. 직접 테스트 해보십시오. 가장 쉬운이었다