c++ - C++ vector 元素擦除与新 vector 创建

我正在处理需要随机选择并有效删除的元素 vector ，直到满足条件或选择了所有元素为止。但是，直到执行代码的后期，它们才真正被删除，因此我需要维护一个有效的可用元素列表。我可以从第二个 vector 中删除元素，或者每次都可以重新创建它。请在下面查看我的代码的最低版本，该示例显示在while循环中每次创建 vector 的位置的示例:

    Random mRandom; // Pseudo-random number generator
    std::vector< Element* > mElements;
    for( unsigned index = 0; index < ARBITRARY_VALUE; index++ )
      mElements.push_back( new Element( ) );

    std::vector< bool > removedElements;
    bool condition = true;

    while( condition == true ) {
      std::vector< unsigned > availableIndices;

      for( unsigned index = 0; index < mElements.size( ); index++ ) {
        if( removedElements[ index ] == false )
          availableIndices.push_back( index );
      }

      if( availableIndices.size( ) > 0 ) {
        unsigned maximum = availableIndices.size( ) - 1;
        unsigned randomIndex = mRandom.GetUniformInt( maximum ); // Zero to max
        removedElements[ availableIndices[ randomIndex ] ] = true;
        Element* element = mElements[ availableIndices[ randomIndex ] ];
        condition = element->DoStuff( ); // May change condition and exit while
      } else
        break;
    }

显然，擦除 vector 中间的元素需要基础系统迭代其余元素并将其“移动”到新的有效位置。显然，如果被擦除的元素在 vector 的末端附近，则意味着迭代次数更少。

我已经阅读了几篇有关删除 vector 元素的相关费用的文章，但还没有发现任何可以直接解决我的问题的东西。擦除后“移动”元素的过程是否会产生开销，从而通过创建指向有效元素的新 vector 来使每次迭代所有元素的开销变得更便宜？如上面的代码示例所示。

干杯，菲尔

最佳答案

我无法评论解决问题的最佳方法，因为我不确定函数或算法的实际要求是什么(即元素应该保留顺序吗？不可用元素会再次变得可用吗？如果可以，那么排序会很重要吗？然后？等等)

但是，关于最后一个问题:



这完全取决于移动元素所涉及的内容。如果是如上所述的指针，那么您可以移动很多元素，甚至可以接近在新 vector 中分配内存的成本。通过“很多”，我正在考虑成百上千。

在上面的代码中，可用性 vector 似乎是多余的。如果Element指针位于availableIndicies的 vector 中，则该指针可用。

如果我正确理解了意图，我认为我可以按照以下几行进行重构:

#include <vector>
#include <random>

struct Element
{
  bool doStuff();
};


struct ElementAvailability
{
  ElementAvailability(std::vector<Element*> const& storage)
  : storage_(storage)
  {}

  void resync()
  {
    // will requre an allocation at most once if storage_ does not grow
    available_ = storage_;
  }

  std::size_t availableCount() const {
    return available_.size();
  }

  Element* removeAvailable(std::size_t index) {
    auto pe = available_[index];
    available_.erase(std::begin(available_) + index);
    return pe;
  }

  void makeUnavailable(std::size_t available_i)
  {
    available_.erase(std::next(std::begin(available_), available_i));
  }

private:
  std::vector<Element*> const& storage_;
  std::vector<Element*> available_;
};

// I have used a std random engine because I don't know your library
auto eng = std::default_random_engine(std::random_device()());

void test(std::vector<Element*>const& elems)
{
  auto available = ElementAvailability(elems);

  bool condition = true;
  auto getCount =[&condition, &available] () -> std::size_t
  {
    if (condition) {
      available.resync();
      auto count = available.availableCount();
      return count;
    }
    else {
      return 0;
    }
  };

  while (auto count = getCount()) {
    auto range = std::uniform_int_distribution<std::size_t>(0, count - 1);
    auto index = range(eng);
    auto candidate = available.removeAvailable(index);
    condition = candidate->doStuff();
  }
}