unordered_map as an hash

[funprogrammer]

I was under the impression that unordered_map could be used as a hash map in c++. But looks like my assumption was wrong. Can someone pointed me in the right direction.

My goal here is to see in constant time if a particular value is in the hash map if not add it to hash map. I tried using unordered_map in c++ and used the find function on it, unfortunately that did not work for complicated test cases(I am running it on a coding challenge on hackerrank). Here is the code I have, I tried using operator[] also and it did not work, Any suggestions?

int main(){
    int n,p,tmp=0,res=0;
    unordered_map<int,int> map;
    
    cin >> n >> p;
    vector<int> a(n);
    for(int a_i = 0;a_i < n;a_i++){
       cin >> a[a_i];
    }
    // your code goes here
    for(int a_i = 0;a_i < n;a_i++){
      tmp=ceil((double) a[a_i]/p);
      while(map.find(tmp) != map.end()){
        tmp++;
      }
      //cout <<"tmp is"<<tmp<<endl;
      map.insert(make_pair(tmp,1));
      res+=tmp;  
    }
    cout<<res<<endl;
    return 0;
}

[Cubbi]

std::unordered_map is exactly the hash map in C++. What does "that did not work" mean?

[funprogrammer]

I think this line of code while(map.find(tmp) != map.end()) is not running in constant time. For large inputs, this is taking more time. I wanted to know if there was any better way to achieve O(1) time for map searches.

[JLBorges]

map.find(tmp) != map.end() is O(1) (average)

The loop while(map.find(tmp) != map.end()) ++tmp ; is O(N) (average). For large N, this would be slow.

[funprogrammer]

yes, that is what I am facing, any work arounds to fix that? I was thinking unordered_map was fastest, but turns out that is the case here.