清除std :: vector范围向量的最佳方法 [英] Best way to erase vector of ranges from std::vector

问题描述

在我的一个项目中，有必要从 std :: vector< double>中删除某些元素.值.我必须删除的索引以间隔向量的形式给出.例如， {1,3} 意味着我必须从 values 的值中删除索引(从1到3).

我可以假定给定的间隔是互斥的.

下面显示的代码说明了所需的行为.

  #include< iostream>#include< vector>int main(int argc，char ** args){//我必须从值中删除的索引间隔std :: vector< std :: pair< int，int>interval = {{{1,3}，{7,9}，{13,13}};//任意值的向量.std :: vector< double>值= {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(值，间隔);//间隔应包含4.2、9.1、2.3、0.6、6.4、3.6、1.4、7.5} 

实现此目标所需的最短代码量是多少?

到目前为止，我最好的解决方案是:

  void removeIntervals(std :: vector< double&值，const std :: vector< std :: pair< int，int>&间隔){std :: vector< bool>flags(values.size()，true);std :: vector< double>退对于(自动间隔:间隔){std:fill(flags.begin()+ interval.first，flags.begin()+ interval.second + 1，false);}for(auto i = 0; i< values.size(); i ++){如果(flags [i])ret.push_back(values [i]);}值= ret;} 

我可以假设，我的间隔是不重叠且连续的.看来，它可以归结为从后到前执行擦除操作.

  void removeIntervals2(std :: vector< double&值，const std :: vector< std :: pair< int，int>&间隔){auto revIntervals =间隔；std :: reverse(revIntervals.begin()，revIntervals.end());对于(自动间隔:revIntervals){values.erase(std :: begin(values)+ interval.first，std :: begin(values)+ interval.second +1);}} 

解决方案

由于您可以假设间隔不重叠并且按递增顺序排列，所以解决方案是从背面开始(这样索引就不会改变)，然后依次删除每个范围:

因此，您要求的代码最少:

  for(auto&它= interval.rbegin(); it！= interval.rend(); ++ it){values.erase(values.begin()+首先-std :: next(values.begin()+ it->第二)); 

不利的一面是，这将涉及向量的大量改组.实际上，您想要做的就是将向量末尾的最后一个未交换的项与要删除的项交换，然后在完成切除端的操作后调整大小.但这需要更多代码.

In one of my projects it is necessary to remove certain elements from a std::vector<double> values. The indices I have to remove are given as a vector of intervals. For example {1,3} means, that I have to remove indices from 1 to 3 inclusive from values.

I can assume that the intervals given are mutually exclusive.

The code shown below illustrates, what the desired behavior should look like.

#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
}

What might be the shortest amount of code necessary to achieve this?

My best solution so far is:

 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;
 }

I can assume, that my intervals are non-overlapping and consecutive. It seems, that it boils down to perform erase from back to front.

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);
    }
}

解决方案

Since you can assume that the intervals don't overlap and are increasing order, the solution is to start at the back (so that the indexes don't change) and remove each range in turn:

So for the minimum amount of code, which you asked for:

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

The down side of this is that this will involve lots of shuffling of the vector. Really what you would want to do is swap the last unswapped item at the end of the vector, with the item you want to remove, and then resize when you're finished to cut off the end; but this requires more code.

这篇关于清除std :: vector范围向量的最佳方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！