C++ベクトル要素の消去と新しいベクトルの作成

Question

ランダムに選択する必要があり、条件を満たすか、すべての要素が選択されるまで効果的に削除する必要がある要素のベクトルを処理しています。しかし、コード実行の後半になるまで実際には削除されないので、有効で有効な要素のリストを維持する必要があります。この2番目のベクトルから要素を消去することができます。または、毎回それを再作成することができます。ベクターは、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

私はまだ機能やアルゴリズムの実際の要件が何であるかわからないので、私は？つまり要素が順序を保持すべき（あなたの問題を解決する最良の方法にコメントすることはできませんでしょう使用できない要素？彼らは、当時とそう

）にかかわら注文する場合はしかし、再び利用できるようになり、最後の質問について：

消去以下「移動」要素のプロセスを作ることができるオーバーヘッドを紹介していそれはすべてのthを繰り返しiterate安い有効なものを指し示す新しいベクトルを作成することによって、毎回要素を追加しますか？

これは、要素の移動に関係するものに完全に依存します。上記のようにポインタであれば、新しいベクトルにメモリを割り当てるコストに近づく前に多くの要素を移動することができます。そして、「たくさんの」によって私は何百、何千ということを考えています。

上記のコードでは、可用性のベクトルが冗長であるかのように見えます。ベクトル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であるかどうかがチェックされます。ループ内でのメモリ割り当ては常にコストがかかるため、避けてください。