Why Can't I Replace Std::Map with Std::Unordered_Map

Why can't I replace std::map with std::unordered_map

I guess that because std::unordered_map needs to rehash, and therefore copy elements, the types need to be complete, whereas a map, only ever working with pointers to elements, will not exhibit that problem.

The solution here is to have an unordered map to a pointer:

std::unordered_map<uint32_t, std::shared_ptr<Test> >. 

In practice, when `std::unordered_map` must be used instead of `std::map`?

I know the difference between them, say internal implementation,time complexity for searching element

In that case, you should know that that the average asymptotic element lookup time complexity of unordered map is constant, while the complexity of ordered map is logarithmic. This means that there is some size of container at which point the lookup will be faster when using unordered map.

But I really can't find a circumstance where std::unordered_map could not be replaced by std::map indeed.

If the container is large enough, and if you cannot afford the cost of ordered map lookup, then you cannot choose to replace the faster unordered map lookup.

Another case where ordered map cannot be used is where there doesn't exist a cheap function to compare relative order of the key.

std::unordered_map insert invalidates only iterators but not references and pointers to the element node

Insertion of unordered_map doesn't invalidate references because it doesn't move the data, however the underlying data structure might change rather significantly. Details of how exactly it is implemented aren't specified and different compilers do it differently. For instance, MSVC has a linked list for data storage and, I believe, a vector for the look-up. And insert can cause rehash, meaning look-up gets changed completely and the linked list gets reorded significantly - but original data is not moved.

The iterators refer to this underlying structure and any changes to it can cause iterators to invalidate. Basically, they contain more info than pointers and references and subsequently can get invalidated.

The confusing passage is about insert of a node_type - nodes that were previously extracted. Checkout the method unordered_map::extract

https://en.cppreference.com/w/cpp/container/unordered_map/extract

For some reason it is forbidden to use pointers/references while the node is extracted. After inserting it is allowed to use them again. I don't know why it is so.

Why this include order causes link error on unordered_map?

I tested the same code in Visual Studio 2022 and got the same error. After my exploration, I found the problem.

Firstly, I copied the contents of A.h and B.h into main.cpp and removed the #include directive. After compiling, I still got the same error.

Then I tested and found that as soon as I moved namespace std {...} after the definition of class B, the error went away.

I read the assembly code generated by the compiler and found that the names generated for GetMap in main.cpp and b.cpp are different:

main.asm:

GetMap@B@@QEBAAEBV?$unordered_map@UA@@HV?$hash@UA@@@std@@U?$equal_to@UA@@@3@V?$allocator@U?$pair@$$CBUA@@H@std@@@3@@std@@XZ

b.asm:

GetMap@B@@QEBAAEBV?$unordered_map@UA@@HU?$hash@UA@@@std@@U?$equal_to@UA@@@3@V?$allocator@U?$pair@$$CBUA@@H@std@@@3@@std@@XZ

I looked up MSVC's name mangling rules and found U for struct and V for class. So I change the definition of template<> class hash<A> to template<> struct hash<A>. Then the error disappeared.

I think it's legal to use class keyword instead in the specialization, but I can't find a description of this in the standard.

However, I think the problem may not be that simple. A key issue here is that the specialization of std::hash in B.cpp appears after the definition of class B, while in main.cpp the order is completely reversed. I think this violates the ODR and should result in undefined behavior. This is also why the program is correct after swapping the order of the header files (making it consistent with the order in B.cpp).

I looked up some sources and couldn't find a standard description of the problem: In B.cpp, the declaration of GetMap does not cause unordered_map to be instantiated, but it is instantiated in the function definition. A specialization of std::hash was inserted in the middle of declaration and definition, which could cause unordered_map to see a different definition of std::hash. Can the compiler see this specialization? Should the compiler choose this specialization? If the compiler can see the specialization, why is the primary template used in the generated assembly code? (The compiler-generated name in B.cpp uses "U", which is for struct)

Modify the value of a std::unordered_map element in C++

If the key isn't in the map, operator [] is required to create one. The expression

points[1]

needs to be able to default-insert a Point in case of lookup failure (regardless of whether lookup failure ever occurs - this is a compile-time requirement not a run-time check). That requirement cannot be satisfied by Point because Point is not default constructible. Hence the compile error. If you want to use unordered_map::operator[] , you'll need to add a default constructor.

If a default constructed Point doesn't make sense for your usage - then you simply cannot use operator[] and will have to use find throughout (or at() if you're okay with exceptions):

auto it = points.find(1);
if (it != points.end()) {
   it->second.x = 20.f;
}

points.at(1).x = 20.f; // can throw

Using std::map or std::unordered_map when storing consecutive indices

Choosing between std::map and std::unordered_map comes down to if you care about ordering or lookup.

If you need ordering, then you want std::map, at the cost of slower lookup (logarithmic).

If you need fast lookup, they you want std::unordered_map, at the cost of no guaranteed ordering when looping.

However, in your case, since the elements have consecutive keys, why not just store the old file paths in a std::vector<std::string> where the elements align with your std::vector<CustomData>? Here you have the same ordering and the lookup is also constant time (and likely better then a hash map, since youre just jumping to an index rather than hashing the key).

Compilation error related to map and unordered_map: attempting to reference a deleted function

Following on from @JohnZwinck's (excellent) answer, I would say that using std::unordered_map with a vector as a key is usually a bad idea, because of the likely high cost of implementing any kind of effective hashing function.

The link John gave expands on this, but, essentially, the hash function has to inspect every element in the vector every time anything needs to be hashed. If the vector is large, well, ouch!

So std::map is likely to be a better choice here, because std::less (-> operator<) is likely to be cheap - as soon as we hit an element of the vector whose value differs between the two operands, we are done. Worst case, it is no more expensive (although it's true that std::unordered_map is more efficient than std::map when a cheap and effective hashing function does exist, especially, for example, if the key is something like an int).

Can you turn std::map into an unordered map with a custom comparator?

Always returning true is invalid. It would mean (for instance) that A < B and B < A would both be true. This contradicts the requirements of a std::map comparator, which are that it imposes a strict weak ordering. It's entirely possible returning true would crash your program.

Always returning false is valid, it effectively means that all keys are considered equal. So only one key could be added to the map (thanks aschepler for the correction).

What stops you writing a sensible comparator?

---

Related Topics