C++矢量元素擦除与新矢量创建

Question

我正在处理一个元素矢量，这些元素需要随机选择并有效地移除，直到满足条件或者直到所有元素都被选中。但是，在代码执行的后期阶段之前，它们实际上不会被删除，所以我需要维护一个有效的可用元素列表。我可以从第二个矢量中删除元素，或者每次都可以重新创建它。请参考下面示出的载体在while循环每次创建的例子我的代码最低版本：

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

很明显，擦除矢量中间的元素需要底层系统进行迭代通过其余的元素并将它们移动到新的有效位置。显然这意味着如果擦除的元素接近矢量的末尾，则意味着更少的迭代。

我已经阅读了一些关于擦除矢量元素的相关费用的帖子，但我还没有看到任何直接解决我的问题的东西。在擦除之后“移动”元素的过程是否会引入开销，从而可以通过创建指向有效元素的新向量来遍历所有元素，从而使其更便宜？正如我在上面的代码示例。

干杯，菲尔

Answer 1

我不能在最好的办法评论，因为我还没有确定的函数或算法的实际需要是什么来解决问题（即应保留元素顺序？请问无法显示的元素再次变得可用。如果他们这样做，将此事订货，然后依此类推）

然而，关于最后一个问题：？？

是否的“移动”元素之后的擦除介绍的开销，可以使过程遍历整个过程更便宜e元素每次创建一个指向有效元素的新向量？

这完全取决于移动元素所涉及的内容。如果它是一个指针，如上所述，那么即使接近在新矢量中分配内存的开销，也可以移动很多元素。通过“很多”我想到了数百乃至数千。

在上面的代码中，看起来好像可用性的向量是多余的。 Element指针可用，如果它在availableIndicies的向量中。

如果我理解正确的意图，我想我可能大意如下的重构：

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

Answer 2

元素的随机消除你所提出的问题，在我看来，解决的只是在O(n^2)时间和O(n)空间复杂度。因为你必须通过所有元素一次和每次传递，你必须在一系列仍然存在的元素中找到一个随机索引并保持这个顺序。使用不同算法原语的方法可能很少。下面我以CPU /内存操作友好的方式呈现我的解决方案，以此来存档此目标。

void runRandomTasks() { 
    Random mRandom; // Pseudo-random number generator 
    std::vector<Element*> mElements; 
    for (unsigned index = 0; index < ARBITRARY_VALUE; ++index) { 
    mElements.push_back(new Element); 
    } 
    size_t current_size = mElements.size(); 
    if (!current_size) 
    return; 
    std::vector<Element*> current_elements(current_size, nullptr); 
    for (unsigned index = 0; index < current_size; ++index) { 
    current_elements[index] = mElements[index]; 
    } 
    Element** last_ptr = &current_elements[0] + current_size - 1; 

    bool condition = true; 

    while (condition && current_size) { 
    unsigned random_size = mRandom.GetUniformInt(current_size - 1) + 1; // Zero to max 
    Element** ptr = last_ptr; 
    while (true) { 
     random_size -= (bool)(*ptr); 
     if (random_size) { 
     --ptr; 
     } else { 
     break; 
     } 
    } 

    condition = (*ptr)->DoStuff(); // May change condition and exit while 
    *ptr = nullptr; 
    --current_size; 
    } 
} 

关于你的矢量元素删除的问题，你可以在我的解决方案，有找到一个随机指数的环发现，即相当于元素擦除的载体，时间复杂性，但具有更小的常数，因为元素移位被省略，而元素值被检查为0或不是。在循环中执行任何内存分配总是很昂贵，所以要避免这种情况。