CareerCup

unordered_map is the new data structure added to C++ STL as part of C++11 version (in <unordered_map> library).

Here is the direct quote from cppreference.com:

"Unordered map is an associative container that contains key-value pairs with unique keys. Search, insertion, and removal of elements have average constant-time complexity.

Internally, the elements are not sorted in any particular order, but organized into buckets. Which bucket an element is placed into depends entirely on the hash of its key. This allows fast access to individual elements, since once hash is computed, it refers to the exact bucket the element is placed into."

Original map (<map>) implementation was done using a balanced tree implementation and therefore having the O(log N) time complexity to get/put/delete elements. However, <ordered_map> library is implemented differently as described above and have _amortized_ O(1) time complexity for get/put/delete operations.

Note that, if you go to actual manual page at cppreference.com, you can see the time complexities for each operations and you will see that worst case analysis in certain cases may vary from O(1) to (N), but if I were the interviewer I'd be OK with O(1).

An unsorted Map is a tipicall implementation of a Hashtable or a HashMap, where the keys' hashcode (in Java at least) will make room to the value in a certain bucket in the table.
The difference between the Hashtable Vs HashMap is that the hashtable is thread safe and the HashMap is not.
both run operation in constant time.

the opposite of a unsorted Map would be a SortedMap which a tipical implementation whould be a TreeMap, which Operation such as containsKey(), get(), put() are done on O(log n)