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

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

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