c++templateshashtablelinear-probing

implement linear probing in c++ for a generic type

I wanted to implement linear probing for hashtabe in c++,but the key,value pair would be of generic type like: vector< pair< key,value> >(where key,value is of generic type).

Now,in linear probing if a cell is occupied we traverse the vector until we find an empty cell and then place the new pair in that cell.

The problem is,that in generic type,how would I be able to check if a particular cell is occupied or not? I cannot use these conditions:

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

OR

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

So,how will be able to check if a paricular cell in the vector is empty or not? Please correct me if I misunderstood the concept.

Solution

  • I think you can just check if the element of the vector has meaningful key and value:

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

    or, if you only care about the keys

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

    This approach assumes that the default constructor of key type constructs an object that would be considered an "empty" or "invalid" key.