std :: vector 범위의 벡터를 지우는 가장 좋은 방법

Question

내 프로젝트 중 하나에서 std::vector<double> values의 특정 요소를 제거해야합니다. 제거해야하는 인덱스는 간격 벡터로 제공됩니다. 예를 들어, {1,3}은 1에서 3까지의 인덱스를 values에서 제거해야한다는 것을 의미합니다.

주어진 간격은 상호 배타적이라고 가정 할 수 있습니다.

아래 표시된 코드는 원하는 동작을 보여줍니다.

#include <iostream> 
#include <vector> 

int main(int argc, char** args) { 
    // Intervals of indices I have to remove from values 
    std::vector<std::pair<int, int>> intervals = { {1,3},{7,9},{13,13} }; 

    // Vector of arbitrary values. 
    std::vector<double> values = {4.2,6.4,2.3,3.4,9.1,2.3,0.6,1.2,0.3,0.4,6.4,3.6,1.4,2.5,7.5 } 
    removeIntervals(values, intervals); 
    // intervals should contain 4.2,9.1,2.3,0.6,6.4,3.6,1.4,7.5 
} 

이 작업을 수행하는 데 필요한 최단 코드는 무엇입니까?

내 가장 좋은 방법은 지금까지입니다 :

void removeIntervals(std::vector<double>& values, const std::vector < std::pair<int, int>>& intervals) { 
    std::vector<bool> flags(values.size(), true); 
    std::vector<double> ret; 
    for (auto interval : intervals) { 
     std:fill(flags.begin() + interval.first, flags.begin()+interval.second+1, false); 
    } 
    for (auto i = 0; i < values.size(); i++) { 
     if (flags[i]) ret.push_back(values[i]); 
    } 
    values = ret; 
} 

내 간격이 겹치지 연속 것을, 가정 할 수있다. 그것은 뒤에서 앞으로 지우기를 수행하는 것으로 나타났다.

void removeIntervals2(std::vector<double>& values, const std::vector < std::pair<int, int>>& intervals) { 
    auto revIntervals = intervals; 
    std::reverse(revIntervals.begin(), revIntervals.end()); 
    for (auto interval : revIntervals) { 
     values.erase(std::begin(values) + interval.first, std::begin(values) + interval.second + 1); 
    } 
} 

Answer 1

이 솔루션은 (인덱스가 변경되지 않도록) 뒤쪽에서 시작하여 차례로 각각의 범위를 제거하는 것입니다

for (auto& it = intervals.rbegin(); it != intervals.rend(); ++it) { 
    values.erase(values.begin() + it->first, std::next(values.begin() + it->second)); 

이렇게하면 코드가 많이 뒤섞입니다. 정말로 당신이하고 싶은 것은 벡터의 마지막에 놓여 있지 않은 마지막 아이템과 제거하고 싶은 아이템을 교환 한 다음, 끝날 때 끝낼 때 사이즈를 변경하는 것입니다. 하지만 더 많은 코드가 필요합니다.

Answer 2

생각 나는 조금 더 내결함성이있는 대답을 게시 할 것입니다. 간격이 입력 배열보다 큰 경우 (예 : intervals에 {15, 15}이 포함 된 경우) 이는 여전히 올바르게 작동합니다. 또한이은보다 빠른 UKMonkey's solution는 단일 패스에서 모든 작업 않기 때문에 : 그것은 단지이 코드는 구현 정의되어 내 관심에 와서하고있다

작동 Clang and Visual Studio 2015 Update 3에 :

values.resize(distance(begin(values), remove_if(begin(values), end(values), [i = 0U, it = cbegin(intervals), end = cend(intervals)](const auto&) mutable { return it != end && ++i > it->first && (i <= it->second || (++it, true)); }))); 

Live Example

당신은 비록 for -loop에서 같은 일을 수행 할 수 있습니다

size_t write = 0U; 
auto it = cbegin(intervals); 

for (size_t read = 0U; read < size(values); ++read) { 
    if (it == cend(intervals) || read < it->first) { 
     values[write++] = values[read]; 
    } else if (read == it->second) { 
     ++it; 
    } 
} 

values.resize(write); 

당신이에 푹 경우

Live Example

"이를 달성하기 위해 필요한 코드의 최단 시간,"당신은 너무 for -loop에 람다에서 내 악 ,를 사용할 수 있습니다

이

for (size_t read = 0U; read < size(values); ++read) if (it == cend(intervals) || read < it->first || (read == it->second && (++it, false))) values[write++] = values[read]; 

Answer 3

문제는 vector::erase()에 대한 첫 번째 호출 이후 첫 번째 지워진 요소를 지나치는 모든 요소/이터레이터는 제거 할 추가 간격을 포함하여 무효화됩니다.

따라서 vector::erase()을 사용하면 지울 요소의 내림차순으로 수행해야합니다.

또 다른 불편 함은 간격 경계에 대한 반복자 대신에 int 색인을 사용함에 기인합니다. 마지막으로 vector::erase()은 간격을 메우기 위해 마지막으로 제거 된 요소를지나도록 모든 요소를 ​​복사 (광석 이동)합니다. 이렇게하면 값의 순서가 유지되지만 여러 간격으로 과도한 복사 (이동)가 발생합니다.

더 효율적인 방법은 제거 할 요소 만 바꾸고 마지막으로 벡터 크기를 줄이는 것입니다.그래서

: 당신이 간격이 중복되지 않는 주문 증가한다고 가정 할 수 있기 때문에

Answer 4

확실히 원하는 것은 짧은 코드뿐만 아니라 효율성이 좋은 솔루션을 사용하여 값 벡터의 복사본과 시프트를 최소화하는 것입니다.

저는 솔루션의 첫 번째 부분을 확실히 지키고 있습니다. 즉, 유지하거나 삭제할 위치를 배정하는 것입니다. 두 번째 부분에 대한

std::vector<bool> flags(values.size(), true); 
for (auto interval : intervals) { 
    std:fill(flags.begin() + interval.first, flags.begin()+interval.second+1, false); 
} 

최단 및 erase/remove_if 관용구 것이 가장 효율적인

values.erase(std::remove_if(begin(values), end(values), 
    [&](const auto& v) { return !flags[&v - &(*values.begin())];}), 
    values.end()); 

여기 효율 remove_if 먼저 마크 필요한 요소를 제거 할 것이다에 기인 , 그러면 요소를 처음 머무르게하고 제거 할 첫 번째 요소의 위치를 ​​반환하여 벡터를 압축합니다. 마지막으로 erase은 벡터를 축소합니다. 알고리즘 적 관점에서 보면이 솔루션이 최적 일 수 있습니다. 그것은 큰 벡터를 지불해야합니다.

Answer 5

음, 완전히 새로운 벡터를 만들거나 O (N^2) 시간을 필요로하는 답변은 지금까지 모두 잘못되었습니다.

지우고 싶지 않은 요소를 지우고 나머지 시간을 바꿀 때마다 할 할 올바른 위치로 유지하려면 누른 다음 벡터를 자릅니다.

O (N) 시간과 별도의 공간 :

void removeIntervals(std::vector<double>& values, const std::vector < std::pair<int, int>>& intervals) { 
    if (intervals.size()<=0) 
     return; 

    //keep the part before the first interval 
    auto dest = values.begin()+intervals[0].first; 

    for (size_t i=0; i<intervals.size(); ++i) { 

     //copy the part to keep after each interval 
     auto s = values.cbegin()+intervals[i].second+1; 
     auto e = (i+i >= intervals.size() ? 
        values.cend() : 
        values.cbegin()+intervals[i+1].first); 
     while(s<e) { 
      *dest++=*s++; 
     } 
    } 
    values.erase(dest,values.end()); 
}