Using a std::map<int, ...>
how can I ensure at inserting time that iterating over it will take place in ascending order of the integer key?
Yes, a std::map<K,V> is ordered based on the key, K , using std::less<K> to compare objects, by default.
Internally, the elements in a map are always sorted by its key following a specific strict weak ordering criterion indicated by its internal comparison object (of type Compare).
std::map is a sorted associative container that contains key-value pairs with unique keys. Keys are sorted by using the comparison function Compare .
C++ hash map and hash set which preserves the order of insertion. The ordered-map library provides a hash map and a hash set which preserve the order of insertion in a way similar to Python's OrderedDict. When iterating over the map, the values will be returned in the same order as they were inserted.
You don't have to do anything. The map will be in ascending order according to the values of the key.
Internally, the map performs a comparison between keys to order its elements. By default, it uses std::less<KEY>
, which is equivalent to bool operator<(int, int)
for integers. For user defined types, you have to options:
Implement a bool operator<(const MyType&, const MyType&)
implementing a strict weak ordering comparison between your user defined types. Use this if your type has a natural ordering
Provide a binary functor that implements strict weak ordering, which you can pass as the 3rd template parameter to the map. Use this if your type does not have a natural ordering, or if you want to build the map with an ordering different to that used by std::less<Key>
via the bool operator<(...)
from point 1.
What typically happens behind the scenes is that the map is implemented as a self-balancing binary tree, and the strict weak ordering is used to place new elements in the map, and to determine whether two elements are equal. As an aside, the same logic applies to std::set
, where the key and value are one and the same.
std::map
does that itself. You don't have to do anything.
By default it sorts the keys in the increasing order. If you want it to do sorting in decreasing order, then pass std::greater<T>
as third template argument to std::map
.
std::map<int, X> m1; //sorts key in increasing order
std::map<int, X, std::greater<int>> m2; //sorts key in decreasing order
std::map<int, X, std::less<int>> m3; //sorts key in increasing order
The default argument for third template parameter is std::less<T>
, so above m1
and m3
are same types!
Demo:
#include <iostream>
#include <map>
#include <string>
int main()
{
std::cout << "\nkeys are in increasing order: \n";
std::map<int, std::string> m1;
m1[5] = "first insertion but higher key";
m1[1] = "second insertion but lower key";
for(auto const & item : m1)
std::cout << "{" << item.first <<"," << item.second << "}\n";
std::cout << "\nkeys are in decreasing order: \n";
std::map<int, std::string, std::greater<int> > m2;
m2[1] = "first insertion but lower key";
m2[2] = "second insertion but higher key";
for(auto const & item : m2)
std::cout << "{" << item.first <<"," << item.second << "}\n";
}
Output:
keys are in increasing order:
{1,second insertion but lower key}
{5,first insertion but higher key}
keys are in decreasing order:
{2,second insertion but higher key}
{1,first insertion but lower key}
Notice that in both cases the items are ordered as specified by the third template argument of std::map
. The output doesn't depend on the order of insertion, rather the order of the keys!
Live demo
There is also std::unordered_map
which doesn't sort elements.
map
is usually implemented as a binary search tree, therefore iterators would give you sorted keys already.
If you don't care about the order you may use unordered_map
(from c++11 or boost) which would give you some speed in trade of the order.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With