1

From MDN, javascript provides Map which is C++ equivalent to std::map. Is there a similar equivalent to unordered_map (providing O(1) insertions/lookup/deletion on avg).

Edit: As the answers suggest, std::unordered_map is more closer to javascript Map than std::map.

Abhijeet Khangarot
  • 1,281
  • 1
  • 16
  • 25
  • 2
    I think you're just looking for [Object](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Object). – jsejcksn Aug 03 '21 at 21:49
  • According to [Map Objects](https://262.ecma-international.org/6.0/#sec-map-objects) I wouldn't say a JavaScript Map is equivalent to a C++ `std::map`: _"Map object must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements in the collection."_ A JavaScript Map can be implemented using hash tables providing O(1) insertions/lookup/deletion on avg. It's not ordered by the key but by insertion time. I'd say a JavaScript Map is more of a `std::unordered_map` than a `std::map`. – jabaa Aug 03 '21 at 22:02

1 Answers1

2

The equivalent of a JavaScript Map is the C++ unordered_map, as it provides sub-linear access (i.e. possibly logarithmic but constant in practice) and does not sort its keys. It keeps insertion order of elements for deterministic execution and cross-implementation compatibility, but it is not sorted.

There is no equivalent of the C++ map, which is implemented as a tree with comparable keys, in JavaScript.

Bergi
  • 630,263
  • 148
  • 957
  • 1,375
  • MDN disagrees: "The Map object holds key-value pairs and remembers the original insertion order of the keys. Any value (both objects and primitive values) may be used as either a key or a value." https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map. `std::map` is also sub-linear, by the way (`O(log(N))`): https://stackoverflow.com/questions/9961742/time-complexity-of-find-in-stdmap – River Tam May 16 '23 at 01:28
  • @RiverTam What specifically are you referring to as incorrect? `std::map` does not keep elements in insertion order, it keeps them in comparison (tree) order. – Bergi May 16 '23 at 01:50
  • I wrote far too much, but basically I think the most appropriate thing is to link directly to this blog post (which is indirectly in your links): https://wiki.mozilla.org/User:Jorend/Deterministic_hash_tables. It's _not_ the same as a `std::unordered_map`, but it's also not at all a `std::map`. It seems based on good benchmarking it's basically as good or even better than a normal hash map, but it does have some drawbacks. It would be nice to have an _actual_ `std::unordered_map` just to see if it would work better. It seems one reason not to do that is security, so... ok. – River Tam May 16 '23 at 14:06