同时从向量中插入和删除元素

Question

目标

考虑排序 std::vector x。我们想从此向量中删除向量 positionsToErase 指示的位置处的所有元素。我们还想在位置 positionsToInsert.

处插入向量 valuesToInsert 的值

这些删除和插入必须同时发生，因为如果我们先删除，那么它会使我们想要插入值的位置无效（并且反之亦然）。我认为下面的例子会说明这一点

例子

函数定义示例

template<typename T>
void insertEraseAtPositions(
   std::vector<T>& x,                       // vector to modify. Is sorted and must remain sorted
   std::vector<T>& valuesToInsert,          // is not sorted
   std::vector<size_t>& positionsToInsert,  // is not sorted. This could be figured out inside the function but I happen to already know the positions at which values must be inserted
   std::vector<size_t>& positionsToErase    // is not sorted
);

请注意，non 是常量，可以就地进行修改。

参数示例

std::vector<int> x = {0, 10, 20, 21, 30, 50, 60, 70, 81, 90}; // vector to modify
std::vector<int> valuesToInsert = {40, 80, 100}; // Values to insert are '40', '80' and '100'    
std::vector<size_t> positionsToErase  = {3, 8};   // Erase elements '21' and '81'
std::vector<size_t> positionsToInsert = {5, 8, 10};  // Insert where are currently located the elements '50', '81' and past the current last element.

预期输出

x = {0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100};

重要提示

性能非常重要，因此不可能逐个插入和擦除（即使我们相应地逐步修改位置），因为它会涉及太多副本（或移动）。

通常，x 的大小为 1,000 到 100,000。 positionsToInsert（和 valuesToInsert）的大小为 1-20，positionsToErase 的大小为 1-5。 x 通常具有允许插入值而无需重新分配的容量。因此，我期望（但可能是错误的）就地修改会更快。

如果您愿意，我还可以为 positionsToErase 和 positionsToInsert 提供迭代器而不是索引（std::vector<std::vector<T>::iterator> 而不是 std::vector<size_t>）。

当前工作

我写了一个代码来插入位置，但我也没有包括擦除的可能性。这是代码，以防有帮助。

// Return indices representing the order of elements
template <typename T>
std::vector<uint32_t> sort_indices(const std::vector<T> &v) {

  // initialize original index locations
  std::vector<uint32_t> idx(v.size());
  std::iota(idx.begin(), idx.end(), 0);

  // sort indexes based on comparing values in v
  std::sort(idx.begin(), idx.end(),
       [&v](uint32_t i1, uint32_t i2) {return v[i1] < v[i2];});

  return idx;
}

template <typename T>
void reorder(std::vector<T>& v, std::vector<uint32_t>& order)  
{   
    auto v2 = v;
    for (uint32_t i = 0 ; i < v.size() ; i++)
    {
        v[i] = v2[order[i]];
    }
}

//// Insert multiple elements at specified positions into vector
template<typename T>
void insertAtPositions(std::vector<T>& x, std::vector<T>& values, std::vector<size_t>& positions)
{
  // assert values and positions are the same size
  assert(values.size() == positions.size());

  // Special case - values is empty
  if (values.size() == 0) return;

  // Special case - single value to insert
  if (values.size() == 1)
  {
    x.insert(positions.front(), values.front());
    return;
  }

  // sort the values and the positions where those values should be inserted
  auto indices = sort_indices(positions);
  reorder(positions, indices);
  reorder(values, indices);

  // Special case - x is empty
  if (x.size() == 0)
  {
      x.swap(values);
      return;
  }
  
  // Allocate memory to x
  x.resize(x.size() + values.size());
  
  // Move things to make room for insertions and insert
  int pos_index = positions.size()-1;
  for (size_t i = x.size()-1 ; pos_index >= 0 ; --i)
  {
    if (i == positions[pos_index] + pos_index)
    {
      // A new value should go at index i
      x[i] = std::move(values[pos_index]);
      --pos_index;
    } else
    {
      // The value from index 'i-pos_index-1' must go to index 'i'
      x[i] = std::move(x[i-pos_index-1]);
    }
  }
}

Answer 1

原地修改是不行的。

考虑到你必须在每个位置插入一些东西。您需要将每个项目复制到一个临时位置，然后再将它们复制回来。

您可能会争辩说您可以从头开始倒着做。但是如果我们有一些删除，我们还需要在那里存储一些元素，可能会返回到将每个元素复制到某个临时存储中并返回。

我认为最快的方法是分配一个新数组并构建它，使用原始数组作为临时存储。这样你就可以保证每个元素只被复制一次。

现在，根据使用的类型（如整数或指针），这可能比您可能编写的任何其他内容快得多。如果副本很昂贵，请考虑使用移动或指针。

如果您担心性能，您应该对代码进行基准测试并对其进行调整。没有数据就很难准确地争论性能。

同时从向量中插入和删除元素

Inserting and deleting elements from vector at the same time

c++

performance

vector

insert

erase

*同时从向量中插入和删除元素*

Inserting and deleting elements from vector *at the same time*

c++

performance

vector

insert

erase

同时从向量中插入和删除元素

Inserting and deleting elements from vector at the same time