What is the difference between these STL containers std :: map and std :: unorderedmap, also when looking for an element which is more efficient.
What is the difference between these STL containers std :: map and std :: unorderedmap, also when looking for an element which is more efficient.
Both with associative containers ; associate a value, T , with a certain keyword , Key . In other languages they are called dictionaries or maps .
std::map< Key, T, Compare, Allocator > The elements are stored following a certain order: the one determined by the parameter Compare of the template. They are covered in that same order.
Search, delete, and insert operations have logarithmic complexity OR (log n).
That is, the time it takes to perform those operations depends on the number of elements in the map . The more elements, the slower.
std::unordered_map< Key, T, Hash, KeyEqual, Allocator > The elements are stored in a particular order, using a hash or signature ( wikipedia ). It is almost impossible to run them in any kind of order, being this random and dependent on the hash function used.
Search, insert, and delete operations have media , constant complexity OR (1).
That is, the time it takes to perform operations is independent of the number of elements; it takes approximately the same thing exists 1, 10, or 10000 elements.
Here, the standard does indicate that they are implemented using buckets (sorry for the term, I did not find a suitable word in Spanish. English Wikipedia ).
It's those buckets responsible for that approach in the times.
Keep in mind that these indications are minimum requirements .
That is, you can find implementations of std::unordered_map
that are faster than the standard indicates,
become as fast as std::map . It does not happen that way
std::map It's not that the standard prevents it, it's not possible
make it faster than O (1).
Also note that complexity of the operation is indicated, NO times. It can be, although unlikely, that a std::map with few elements is faster than a std::unordered_map .
By playing with the additional arguments, you can customize the behavior. For example, in the case of std::unordered_map , it is possible to go through them in a specific order, although it is complicated . For this, you can use a custom hash function.
To avoid repeating the comments about trauma ...
std::map implements a tree of nodes which is ordered. The depth of the different branches tends to be the same which forces repositioning nodes in many inserts. Due to this, this map provides very good access times but greatly penalizes the insertion of new values. It is recommended for very stable maps with a large number of queries.
std::unordered_map uses the hash concept to group the different keys. This mechanism allows inserting elements in a fairly fast way in exchange for significantly penalizing searches. Short-lived maps or those that regularly receive inserts usually have a better response time with this type of map.