从 std::vector 擦除范围向量的最佳方法

Question

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

中删除从 1 到 3 的索引

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

下面显示的代码说明了所需的行为应该是什么样子。

#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

我想我会 post 一个更容错的答案。如果您的间隔大于输入数组，例如如果 intervals 包含 {15, 15} 这仍然会正常运行。此外，这比更快，因为它一次完成所有工作：

~~我注意到这段代码是实现定义的，并且只适用于 :~~

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 循环中完成同样的事情：

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

如果你迷上了"the shortest amount of code necessary to achieve this,"，你也可以在for-loop中使用lambda中的邪恶,：

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 2

这个问题很重要，因为在第一次调用 vector::erase() 之后，第一个擦除元素之后的所有 indices/iterators 元素都将失效，包括要删除的进一步间隔。

因此，使用vector::erase()必须按照要擦除的元素的降序进行。

另一个不便源于使用 int 索引而不是区间边界的迭代器。最后，vector::erase() 复制（或移动）最后删除的元素之后的所有元素以填补空白。这保留了值的顺序，但在多个间隔的情况下会导致过度复制（移动）。

一种更有效的方法是只交换要删除的元素，最后缩小向量的大小。

Answer 3

既然你可以假设间隔不重叠并且是递增的顺序，解决方案是从后面开始（这样索引就不会改变）并依次删除每个范围：

因此，对于您要求的最少代码量：

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

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

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) 次并且没有额外的 space:

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

Answer 6

作为 Matt Timmermans 回答的补充：这不是问题，但如果您只想保留区间内的值，在 C++17 中，您可以这样写：

void remove_if_not_in_interval(std::vector<double>& result, const std::vector<std::pair<int,int> >& intervals)
    {
      if (intervals.size() == 0)
        result.clear();

      auto dest = result.begin();
      for (auto [first, last] : intervals)
        {
          while(first!=last+1)
            {
              *dest++ = *(result.begin() + first++);
            }
        }

      result.erase(dest,result.end());
    }

从 std::vector 擦除范围向量的最佳方法

Best way to erase vector of ranges from std::vector

c++

algorithm

stl

stdvector

std-pair