벡터에서 요소를 지우는 경우 다른 벡터에도있는 경우

Question

vector a = {"the", "of"} 및 vector b = {"oranges", "the", "of", "apples"}이 있다고 가정 해 보겠습니다.

두 벡터를 비교하고 a에서 요소를 제거하려면 b도 있어야합니다.

for (int i = 0; i < a.size(); i++) { 
    for (int j =0; j < b.size(); j++) { 
     if (a[i] == b[j]) { 
      a.erase(a.begin() + i); 
     } 
    } 
} 

그러나이 루프가 a의 마지막 요소를 제거되지 않은 :이 내가 생각 해낸 것입니다. 기묘한! 당신이 그것을 삭제 한 후

myvector.erase (myvector.begin()+5); 

둘째, ,이 벡터의 색인이 유효하지 않은 것 :

Answer 1

이 삭제 사물의 올바른 구문입니다 벡터를 형성한다.

그래서 2 라운드 스캔을 권장합니다. 첫 번째 라운드에서는 제거 할 요소를 표시합니다. 두 번째 라운드에서 지울 수 있습니다.

귀하의 알고리즘은 O (n^2) 시간 복잡합니다. 가능한 경우 먼저 벡터를 정렬하는 것이 좋습니다. 그런 다음 훨씬 빠른 알고리즘을 사용하여 처리 할 수 ​​있습니다.

Answer 2

a의 첫 번째 요소를 제거하면 인덱스가 0에서 1로 증가합니다. 루프의 다음 반복에서 벡터의 크기는 외부 루프의 조건을 충족시키는 1입니다 끝내다. std::remove_if, std::find 및 람다를 사용하여이 문제를 해결하는 데 필요한 수법을 피할 수 있습니다.

#include <iostream> 
#include <algorithm> 
#include <vector> 
#include <string> 

int main() 
{ 
    std::vector<std::string> a{ "the", "of" }; 
    std::vector<std::string> b{ "oranges", "the", "of", "apples" }; 

    auto pred = [&b](const std::string& key) ->bool 
    { 
     return std::find(b.begin(), b.end(), key) != b.end(); 
    }; 

    a.erase(std::remove_if(a.begin(), a.end(), pred), a.end()); 

    std::cout << a.size() << "\n"; 
} 

더 좋은 테스트는 a 및 b의 내용을 전환하는 것입니다. 이렇게하면 "the"와 "of"이 제거되어 "오렌지"와 "사과"가 남습니다.

Answer 3

는 시도 과정의

#include <iostream> 
#include <string> 
#include <vector> 
#include <algorithm> 
#include <cassert> 

int main() 
{ 
    std::vector<std::string> a = { "the", "of" }; 
    std::vector<std::string> b = { "oranges", "the", "of", "apples" }; 

    for (auto it = a.begin(); it != a.end();) 
    { 
     if (std::find(b.begin(), b.end(), *it) != b.end()) 
     { 
      it = a.erase(it); 
     } 
     else 
     { 
      ++it; 
     } 
    } 

    assert(a.empty()); 
} 

벡터는 주문 될 경우 더 나은 것 다음과 같습니다. 일반적으로

Answer 4

대신 "수동" 선택적으로 해당 항목을 삭제 벡터의 내용을 걷고, 나는 적절하게 결합 STL의 이미 구축 된 알고리즘을 사용하는 것이 좋습니다 것입니다.

당신이 삭제-제거 관용구 사용을 고려할 수하는 std::vector에서 몇 가지 속성을 만족하는 항목을 삭제, 특히

관용구을 지우기가-제거를 사용.
This Q&A on Stackoverflow은 std::vector 사례를 포함하여 STL 컨테이너에서 항목을 지울 수있는 몇 가지 옵션에 대해 설명합니다.

당신은 컴파일 가능한 코드 아래, live here 주석 찾을 수 있습니다

#include <algorithm> // for std::remove_if() 
#include <iostream>  // for std::cout, std::endl 
#include <string>  // for std::string 
#include <vector>  // for std::vector 
using namespace std; 

void print(const char* name, const vector<string>& v); 

int main() 
{ 
    // Input vectors 
    vector<string> a = {"the", "of"}; 
    vector<string> b = {"oranges", "the", "of", "apples"}; 

    print("a", a); 
    print("b", b); 

    // Use the erase-remove idiom 
    a.erase(
     remove_if(
      a.begin(), 
      a.end(), 

      // This lambda returns true if current string 's' 
      // (from vector 'a') is in vector 'b'. 
      [&b](const string& s) 
      { 
       auto it = find(b.begin(), b.end(), s); 
       return (it != b.end()); 
      } 
     ), 

     a.end() 
    ); 

    cout << "\nAfter removing:\n"; 
    print("a", a); 
} 


void print(const char* name, const vector<string>& v) 
{ 
    cout << name << " = {"; 
    bool first = true; 
    for (const auto& s : v) 
    { 
     if (first) 
     { 
      first = false; 
      cout << s; 
     } 
     else 
     { 
      cout << ", " << s; 
     } 
    } 
    cout << "}" << endl; 
} 

출력 : 또한 this very similar question on Stackoverflow

a = {the, of} 
b = {oranges, the, of, apples} 

After removing: 
a = {} 

PS
참고. std::set_difference()

다른 방법을 사용

는

---

, 예를 std::set_difference()을 사용할 수있다 다음 코드와 같은 것입니다 : live here.
은 (set_difference() 전제 조건에 따라, 입력 벡터가 이미 있어야합니다 이 정렬,이 경우 모릅니다.)

#include <algorithm> // for std::set_difference(), std::sort() 
#include <iostream>  // for std::cout, std::endl 
#include <iterator>  // for std::inserter 
#include <string>  // for std::string 
#include <vector>  // for std::vector 
using namespace std; 

void print(const char* name, const vector<string>& v); 

int main() 
{ 
    // Input vectors 
    vector<string> a = {"the", "of"}; 
    vector<string> b = {"oranges", "the", "of", "apples"}; 

    print("a", a); 
    print("b", b); 

    // Sort the vectors before calling std::set_difference(). 
    sort(a.begin(), a.end()); 
    sort(b.begin(), b.end()); 

    // Resulting difference vector 
    vector<string> c; 
    set_difference(a.begin(), a.end(), 
        b.begin(), b.end(), 
        inserter(c, c.begin())); 

    print("difference(a,b)", c); 
} 


void print(const char* name, const vector<string>& v) 
{ 
    cout << name << " = {"; 
    bool first = true; 
    for (const auto& s : v) 
    { 
     if (first) 
     { 
      first = false; 
      cout << s; 
     } 
     else 
     { 
      cout << ", " << s; 
     } 
    } 
    cout << "}" << endl; 
} 

Answer 5

당신이 발생하는 문제는 당신의 요소를 제거하고 있다는 사실에 기인한다 a 당신은 그것을 반복하고 있지만 보상하지는 않습니다. 이는 지우기가 포함 된 루프를 작성하려고 할 때 자주 발생하는 문제입니다.

벡터의 내용이 어떤 순서인지는 중요하지 않으며 결과를 다른 벡터에 저장해도 괜찮은 경우 두 가지 벡터를 정렬하고 std::set_difference을 호출하는 것이 가장 좋은 방법 중 하나입니다.

#include <algorithm> 
#include <iterator> 
#include <string> 
#include <vector> 

int main() 
{ 
    std::vector<std::string> a = { "the", "of" }; 
    std::vector<std::string> b = { "oranges", "the", "of", "apples" }; 
    std::vector<std::string> res; 

    std::sort(a.begin(), a.end()); 
    std::sort(b.begin(), b.end()); 

    std::set_difference(a.begin(), a.end(), b.begin(), b.end(), 
     std::back_inserter(res)); 
} 

res이 경우 비어 있습니다 b에없는 a의 모든 요소를 ​​포함합니다.

주문이 중요한 경우 또는 완료해야하는 경우 지우기 - 제거 관용구을 사용할 수 있습니다. 필연적으로 O (n^2) 알고리즘이기 때문에 큰 벡터의 경우 속도가 느려질 필요가 없습니다. 당신이 C++ (11) 준수 컴파일러에 액세스 할 일이없는 경우

#include <algorithm> 
#include <iterator> 
#include <string> 
#include <vector> 

struct Pred 
{ 
    const std::vector<std::string>& filter; 
    Pred(const std::vector<std::string>& x) 
     :filter(x){} 

    bool operator()(const std::string& str) const 
    { 
     return std::find(filter.begin(), filter.end(), str) != filter.end(); 
    } 
}; 

int main() 
{ 
    std::vector<std::string> a = { "the", "of" }; 
    std::vector<std::string> b = { "oranges", "the", "of", "apples" }; 

    Pred pred(b); 

    a.erase(std::remove_if(a.begin(), a.end(), pred), a.end()); 
} 

는 Pred 구조는 상당히 좋은 독립의 람다해야한다. 그렇지 않으면,이 람다는 일을 할 것입니다 :

auto pred = [&b](const std::string& str) 
    { 
     return std::find(b.begin(), b.end(), str) != b.end(); 
    };