stl map and unordered_map difference

Question

0.00/5 (No votes)

See more:

i want to understand that major difference between map and unordered_map in C++.

which one i suppose to use and which one is best?

Posted 14-Nov-13 20:05pm

ranjithkumar81

Add a Solution

4 solutions

Solution 4

None of these is "best". All of these data structures have their own characteristics. These characteristics are often described by listing the time complexity of the operations (insert, remove, add, ...) provided by the data structure. Here is a relatively brief yet good list of such a list: http://stackoverflow.com/questions/7294634/what-are-the-time-complexities-of-various-data-structures[^]

Each data structure has its own advantages and disadvantages, there is no perfect. Which data structure to use? Analyze the activity of your program, which operations does it use often? Choose a data structure whose advantages include most of the operations you often use. It will have a few slow operations but you know that you won't use those often...

Sometimes reality is different than what you would expect. Often data structures built from arrays are much faster if constructed/organized in a smart way because of better locality / cache-friendliness but this is also a hardware dependent thing (I referred to today's average desktop computers).

Posted 17-Nov-13 2:38am

pasztorpisti

Add a Solution

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

nv3 · Accepted Answer · 2013-11-14T20:21:00

An ordered map is usually implemented on the basis of an ordered tree, for example red-black-tree in STL's case. Tree manipulations are relatively expensive, but the tree uses very little storage.

An unordered map is usually implemented as a hash table; the newer STL implementation offer such a map as well. Hash table are very fast, but have some storage overhead and can only grew to a certain number of nodes before they become inefficient.

So if you have a set of values for which you can estimate the maximum number of nodes and for which you don't need to iterate through the nodes in an ordered fashion, the unordered map is usually the best choice. In all other cases you better use an ordered (tree-based) map.

[AMENDMENT - A comment by pasztorpisti]

Depending on the scenario and the allocators in use trees can extremely fragment memory while a simple yet effective hashmap is only 2 arrays. Most of the time I use only hashmaps and a special kind of ordered map (built on top of an orderedset) that is an array that is always sorted. Depending on the frequency of different operations and the number of items trees may become the better solution but in my opinion that is relatively rare.

CPallini · Accepted Answer · 2013-11-14T21:21:00

Solution 2

What't the difference between using Google[^] or not?

Posted 14-Nov-13 21:21pm

CPallini

Comments

ranjithkumar81 15-Nov-13 3:47am

hello, i could not find the proper answer in Google as per my search.

fkassaie · Accepted Answer · 2013-11-16T21:28:00

Hi,
map:

- Usually implemented using red-black tree.
- Elements are sorted.
- Relatively small memory usage (doesn't need additional memory for the hash-table).
- Relatively fast lookup: O(log N).

unordered_map:

- Usually implemented using hash table.
- Elements are not sorted.
- Requires additional memory to keep the hash-table.
- Fast lookup O(1), but constant time depends on the hash-function which could be relatively slow.

refrence: (http://learninger.com[^])

stl map and unordered_map difference

4 solutions

Solution 1

Solution 2

Solution 3

Solution 4

Add your solution here

Preview 0

stl map and unordered_map difference

4 solutions

Solution 1

Solution 2

Solution 3

Solution 4

Add your solution here

Preview 0

Existing Members

...or Join us