자연 정렬 순서가없는 두 표준 :: 벡터의 차이

Question

std::vectors 사이의 차이를 얻는 효율적인 방법을 찾고 있습니다. 포함 된 객체에는 자연 순서가 없습니다. 내가 할 수있는 최선은 평등을 시험하는 것입니다. 이것은 std::set_difference 옵션을 배제하는 것으로 보입니다.

두 개의 중첩 된 반복기 안의 개체를 비교하는 것보다 나은 해결책이 있습니까?

Answer 1

가능한 목표는 가능한 긍정적 인 일치를 그룹화하여 동등성 테스트의 수를 줄이는 것입니다.

내가 생각할 수있는 가장 좋은 점은 첫 번째 벡터로 해시 맵을 작성한 다음 해시 맵에서 두 번째 벡터의 모든 요소를 ​​빼는 것입니다. 즉, 요소에 알맞은 해시 함수를 찾아야합니다.

당신이 포인터를 저장하고 동등한 조건부가 그것을 기반으로한다면, 당신은 해시를 그 포인터 적분 값에 기초 할 수 있습니다.

What is a good hash function?을 참조하십시오.

주석에서 언급했듯이 다른 대안은 요소의 특정 속성에 대한 순서를 설정하고이를 사용하여 평등의 가능성을 줄이는 것입니다. 두 벡터를 먼저 정렬해야 할 수 있습니다.

Answer 2

벡터의 속성을 활용할 수 있습니다. 연속 된 메모리 할당이 있습니다. 즉, 벡터가 하나의 큰 메모리 공간을 예약하고 (더 크고 일반적으로 사용됨) 환상적인 최적화 없이는 메모리 공간을 직접 비교할 수 있습니다. .

C++ 0x에는 해당 메모리 공간의 시작 부분에 직접 액세스 할 수있는 data() 메서드가 있습니다. memcmp을 사용하면 벡터 내부의 모든 데이터를 비교할 수 있습니다.

std::vector<char> vector_1; 
std::vector<char> vector_2; 

// data in to vector_1 
// data in to vector_2 

if(!memcmp(vector1.data(),vector_2.data(),SIZE_OF_BUFFER_TO_COMPARE)) 
{ 
    std::cout <<< "equal vectors" << std::endl; 
}