ネストされたループにより、複雑さの効率が低下しますか？

Question

私は別のベクトル（V1）の値に基づいて、ベクトル（V2）から要素を除去する簡単な関数を書いた：

std::vector<int> V1={6,2,3,4}; 
std::vector<int> V2={9,4,8,6,7}; 

for(int i=0; i<V1.size(); i++) 
{ 
    if(!V2.empty()) 
    { 
    V2.erase(std::remove(V2.begin(),V2.end(),V1[i]),V2.end()); 
    } 
} 

私の課題は、上記必要性はO（N）であるということです複雑。現在、これはO（n * m）であり、nはV1であり、mはV2である。

N.B.配列は、元のインデックス値が必要な要素としてソートされておらず、ソートできません。

質問：

1. 私は右の 'V2.eraseは' O（N）であることから、この機能を停止していると言っにいますか？ （forループ内のネストされた反復であるため）。

2. ループの外で消去操作を実行すると、これには方法がありますか？

Answer 1

なぜ使用std::set_difference：方法についてそれでは、

---

OK：このランタイムは大まかにうまくいくv1.size() == nとv2.size() == m場合

std::vector<int> test(
    std::vector<int> v1, 
    std::vector<int>& v2) 
{ 
    // The algorithm we use requires the ranges to be sorted: 
    std::sort (v1.begin(), v1.end()); 
    std::sort (v2.begin(), v2.end()); 

    // our output vector: reserve space to avoid copying: 
    std::vector<int> v3; 
    v3.reserve (v2.size()); 

    // Use std::set_difference to copy the elements from 
    // v2 that are not in v1 into v3: 
    std::set_difference (
     v2.begin(), v2.end(), 
     v1.begin(), v1.end(), 
     std::back_inserter(v3)); 

    return v3; 
} 

this：

void test2(
    std::vector<int> v1, 
    std::vector<int> v2) 
{ 
    // We can still sort this without affecting the indices 
    // in v2: 
    std::sort (v1.begin(), v1.end()); 

    // Replace all the elements in v1 which appear in v2 
    // with -1: 
    std::replace_if (v2.begin(), v2.end(), 
     [&v1] (int v) 
     { 
      return std::binary_search(v1.begin(), v1.end(), v); 
     }, -1); 
} 

リニアではありません。複雑さを見積もることは、OPの練習として残されています。

---

第3の選択肢はこれです：配列がソートされている場合は

void test3(
    std::vector<int> v1, 
    std::vector<int>& v2) 
{ 
    // We can still sort this without affecting the indices 
    // in v2: 
    std::sort (v1.begin(), v1.end()); 

    auto ret = std::stable_partition (
     v2.begin(), v2.end(), 
     [&v1] (int v) 
     { 
      return !std::binary_search(v1.begin(), v1.end(), v); 
     }); 

    v2.erase (ret, v2.end()); 
} 

再び、直線的ではないが、オプション...

Answer 2

std::vector<int> V1={6,2,3,4}; 
std::vector<int> V2={9,4,8,6,7}; 

// must be a truly pathological case to have lookups of O(N) 
std::unordered_set v1_hashed(v1.begin(), v1.end()); 

for(
    size_t v2ix=v2.size()-1; 
    v2ix<v2.size(); // otherwise underflow past zero 
    v2ix-- 
) { 
    // generally, an O(1) is assumed here 
    if(v1_hashed.find(v2[v2ix]) != v1_hashed.end()) { 
    // removal of element will cost quite significant due to 
    // moving elements down. This is why doing the cycle in reverse 
    // (less elements to move down). 
    v2.erase(v2ix); 
    } 
} 

// O(N) searches + O(M) hashing of v1