한 벡터의 값이 다른 벡터의 값과 일치하는지보고 싶습니다.

Question

나는 Bulls & Cows라는 게임 코드를 작성하고 있습니다. 나는 이미 하나의 벡터 (같은 인덱스에있는 경우)의 값이 동일한지를 확인했다. 그러나 두 벡터를 통해 이동하고 하나의 값이 다른 벡터의 다른 인덱스 값과 일치하는지 확인하는 for 루프를 작성하는 방법을 모르겠습니다. 나는 어떤 도움을 주셔서 감사합니다. 고맙습니다!

Answer 1

은 단순한 반복 수행 두 벡터 길이 N의 경우

vector<int> v1, v2; 
//Initialize v1 and v2... 

for (auto& i: v1) //Loop through each element of v1 
    for (auto& j: v2) //Same for v2 
     if (i == j) 
      std::cout << "Ok! They match!" << std::endl; 

Answer 2

무력 접근법

for(auto& x1 : vec1) 
    for(auto& x2 : vec2) 
     if(x1 == x2) 
      return true; 
return false; 

이다 이것은 N² 비교를 수행 발견되지 않은 경우, 평균적으로

O (n)의 2 차 시간입니다. 이것은보기에 좋지 않습니다.

---

더 나은 성능을 위해 당신은 단지 가을 설정 한 벡터의 모든 값을 넣을 수 있습니다. 그런 다음 다른 벡터의 각 값을 집합과 비교하여 확인할 수 있습니다. std::set 각 값의 체크는 로그 ( N) 등 N 값를 검사하면 O (N 로그 N) 시간을 제공한다. std::unordered_set의 경우 검사는 본질적으로 일정 시간이므로 O (n)로 전체 작업을 단축합니다.

그러나 최소 g ++ 버전 (MinGW 5.1)에서 해당 표준 라이브러리 구현이 해시 함수 enum의 해시를 지원하지 않아서 해시 함수를 제공해야한다는 점에서 std::unordered_set에 문제가 있습니다. 코드를 이식성있게 만드는 일반적인 해싱 지원.

그래서,

using Item = decltype(v1)::value_type; 
std::set<Item> v1_values{ v1.begin(), v1.end() }; 
for(auto& x2 : v2) 
    if(v1_values.count(x2) > 0) 
     return true; 
return false; 

면책 조항 : 코드도 컴파일러에 의해 훑어보고하지, 나는이 count 내가 일반적으로 단지 표준 라이브러리 물건을 포장하기 때문에 확인하는 가장 우아한 방법인지에 대해 확신 해요.

---

가장 좋은 성능 현명한 증분 방식, 예를 사용하는 것 v1 또는 v2에 값을 추가 할 때마다 해당 세트를 업데이트하십시오. 이는 코드의 복잡성을 증가시키고 이러한 벡터를 사용하는 것과 독립적입니다. 나는. 이는 더 복잡한 솔루션입니다. 일반적으로 추가 된 복잡성으로 성능에 대한 비용을 지불합니다.

Answer 3

이것은 std::find_first_of의 정의입니다.