내가 C++로 hashtabe 프로빙 선형을 구현하고 싶었

Question

제네릭 형식에 대한 C++로 프로빙 선형을 구현하지만, 키, 값 쌍은 같은 제네릭 형식이 될 것입니다 키, 값은 제네릭 형식 임).

이제 선형 탐색에서 셀이 사용되면 빈 셀을 찾은 다음 해당 셀에 새 쌍을 배치 할 때까지 벡터를 탐색합니다.

제네릭 형식에서 특정 셀이 가득 차 있는지 여부를 확인할 수있는 방법은 무엇입니까? 나는이 조건을 사용할 수 없습니다 : 벡터에서 paricular 셀이 비어인지 아닌지 어떻게 확인 할 수있을 것이다,

if(key == '\0')//As key is not of type string 

정도

if(key == 0)//As key is not of type int 

를? 개념을 오해 한 경우 수정하십시오.

Answer 1

나는 벡터의 요소가 의미있는 키와 값이있는 경우 그냥 확인 할 수 있다고 생각 : 당신은 단지 키에 대한 관심이 경우

if(vector[i].first == key()) 
    //empty 

이러한 접근 방식이 있다고 가정

if(vector[i] == std::pair<key, value>()) 
    //empty 

를하거나 기본 생성자 key 유형은 "빈"또는 "유효하지 않은"키로 간주 될 객체를 생성합니다.

Answer 2

무료 키 isEmpty을 사용하여 키 유형이 비어 있는지 확인할 수 있습니다. 대부분의 유형에서 작동하는 템플리트 화 된 기본 함수를 정의하고 디폴트로 처리 할 수없는 특수 함수를 작성하십시오.

예.

template<typename T> 
bool isEmpty(const T &t) { 
    return !t; 
} 

bool isEmpty(const std::string &s) { 
    return s.length() == 0; 
} 

bool isEmpty(double d) { 
    return d < 0; 
} 

isEmpty(0); // true 
isEmpty(1); // false 
isEmpty(std::string()); // true 
isEmpty(std::string("not empty")); // false 
isEmpty(1.0); // false 
isEmpty(-1.0); // true 

당신은 단지 operator !가 없거나 다른 로직이 경우 체크

Answer 3

에 필요한 위치를 "가지고 가능성을 배제하지 않으려는 키 종류를 전문으로합니다 당신의 데이터 구조의 최대 크기를 미리 알고 있다면 같은 병렬 데이터 구조를 만들 수 있습니다. std::vector<bool>, 그 다음에 나는 has이라고 부를 것입니다. 은 vector[i]에 유효하고 실제로 삽입 된 요소가 포함되어 있으면 true입니다.그래서 작업으로 수정해야

은 다음과 같습니다 has[i]을 설정

• 삽입가 : 당신이 위치에 has[i] == false
• 제거 요소는 내가 것을 i 같은 위치를 찾을 때까지 벡터 스캔에 대한 이동 to false

희망이 도움이