왜 std :: inplace_merge_unique가 없습니까?

Question

std::inplace_merge 다음에 수행 할 알고리즘을 찾으려고 시도한 후 std::unique 할 것입니다. 2 패스보다 1 패스에서 더 효율적으로 보입니다. 표준 라이브러리 또는 oogling에서 찾을 수 없습니다.

1. 그래서 어딘가에 다른 이름으로 부스트가 구현 되었습니까?
2. 그런 알고리즘이 가능합니까 (일반적인 inplace_merge와 동일한 복잡성을 보장한다는 의미에서)?

Answer 1

미리 작동하지 않지만 범위가 중복되어 있지 않은 것으로 가정하면 std::set_union은 merge와 동일한 결과를 얻고 고유함을 찾습니다.

Answer 2

알고리즘 섹션에는 많은 흥미로운 알고리즘이 없습니다. STL의 원래 제출은 Stepanov의 관점에서 불완전했으며 일부 알고리즘은 제거되었습니다. Alexander Stepanov와 Meng Lee의 proposal에는 알고리즘 inplace_merge_unique() 또는 그 변형이 포함되어 있지 않습니다.

이러한 알고리즘이없는 이유 중 하나는 요소를 삭제해야하는지 명확하지 않다는 것입니다. 비교는 엄격한 약한 순서이므로 요소의 선택이 중요합니다. 두 번째 범위에서 중복 모든 요소를 ​​제거하기 위해 사용 std::remove_if()

1. 에 inplace_merge_unique()을 구현하는 한 가지 방법이다.
2. inplace_merge()을 사용하면 실제 병합을 수행 할 수 있습니다.

술어를 std::remove_if()으로 병합하면 병합 할 시퀀스의 첫 번째 부분의 현재 위치가 추적됩니다. 아래의 코드는 테스트되지 않았지만 그와 같은 것이 작동해야합니다.

template <typename BiDirIt, typename Comp> 
BiDirIt inplace_merge_unique(BiDirIt begin, BiDirIt middle, BiDirIt end, Comp comp) { 
    using reference = typename std::iterator_traits<BiDirIt>::reference; 
    BiDirIt result = std::remove_if(middle, end, [=](reference other) mutable -> bool { 
      begin = std::find_if(begin, middle, [=](reference arg)->bool { 
        return !comp(arg, other); 
       }); 
      return begin != middle && !comp(other, *begin); 
     }); 
    std::inplace_merge(begin, middle, result, comp); 
    return result; 
}