Understanding Map in C++ as a Java developer [duplicate]

Question

This question already has answers here:

Can we use a user defined class for the key in a STL map? (6 answers)

Closed 8 years ago.

in Java, we´ve got methods like hashCode() and equals() which are used by the map to identify each object. C++ doesn´t have such basic methods, each object implements by default.

How can a map now use custom objects as the key value?

Edit: No duplicate because it´s especially aiming towards those java specific interface methods, someone who has nothing done before with C++ would look for

Answer 1

First, a std::map in C++ is generally a red black tree, not a hash table. There is also a hash map in C++11 called std::unordered_map. By default it uses operator< to compare elements. You can also plug in a custom comparator which can compare using anything you want. This is done by using the optional 3rd template argument to std::map.

Answer 2

C++ std::map is an ordered map, with requirements that mean that it is implemented as a self-balancing binary search tree (usually red-black tree). This means that the key types must have some kind of strict weak ordering, which can come in the form of a less-than operator, or as a user defined comparison functor.

There are plenty of SO posts on how to use an std::map with user-defined types as keys (see one example here).

C++11 has std::unordered_map, which is a hash table with different requirements on key types (specifically, a hashing function and equality comparison are required)

Answer 3

Map in C++ is not HashMap, but rather an ordered map (implemented usually as a red-black tree). Entries are sorted by keys using the comparator function. In default implementation, keys must have operator< overloaded, but you can specify your own comparator function.

See here for C++ map info: http://en.cppreference.com/w/cpp/container/map

Answer 4

std::map is a templated class. The key has to match a certain concept called strict weak ordering which guarantees:

• Keys are less-than-comparable (overload operator< or give the map a custom comparator)
• If element A is less than B, B can't be less than A
• If element A is less than B and B is less than C, then A is less than C

Here's an example with a custom type as key:

#include <map>
#include <iostream>
struct Custom{ Custom(int c): c(c){} int c; };
bool operator< (Custom const &a, Custom const &b){ return a.c< b.c; }
int main(){ std::map<Custom, int> m; m[Custom(42)]= 42; std::cout<< m[Custom(42)]; }

That said, std::map is not the exact equivalent of Java's hash map. C++11 has std::unordered_map for that. With unordered_map, you can define your own std::hash template for your own type to persist your custom type as hash keys.

Answer 5

Java's Hash map has time complexity of O(1). In C++, red-black tree based map has time complexity of O(logN).

CSLM is hread-safe ,concurrent and TreeMap is not . CSLM was added in JDK 1.6

See Docs:Java equivalent of C++ std::map?

Answer 6

C++ map is an ordered map, not a hash map, templated to use a boolean expression comp(a,b) to compare key values. The default is less which performs the (A < B) comparison, which in C++ can be overloaded by classes. Alternate maps can use different expressions.