Connecting Tech Pros Worldwide Help | Site Map

Map "sorted data"

Newbie
 
Join Date: Apr 2007
Posts: 1
#1: Apr 21 '07
I wanna know if ,the map stores sorted data or not.
JosAH's Avatar
Expert
 
Join Date: Mar 2007
Posts: 10,611
#2: Apr 21 '07

re: Map "sorted data"


Quote:

Originally Posted by Thembi

I wanna know if ,the map stores sorted data or not.

Yup, most, if not all maps are implemented as balanced binary search trees.
(AVL trees or red/black trees). No matter their implementation: the keys are
in ascending order.

kind regards,

Jos
Moderator
 
Join Date: Mar 2007
Location: North Bend Washington USA
Posts: 5,366
#3: Apr 22 '07

re: Map "sorted data"


Not quite true:
Quote:
No matter their implementation: the keys are
in ascending order.
The keys are in the order based on the operator< of the underlying class or the binary predicate supplied to the map. You can have keys in descending order with the appropriate comparator function.
JosAH's Avatar
Expert
 
Join Date: Mar 2007
Posts: 10,611
#4: Apr 22 '07

re: Map "sorted data"


Quote:

Originally Posted by weaknessforcats

Not quite true:


The keys are in the order based on the operator< of the underlying class or the binary predicate supplied to the map. You can have keys in descending order with the appropriate comparator function.

Sure, same with what the operator< tells; we call that ascending: if a < b
that b is considered "larger or equal" than a. It doesn't matter what predicate
one uses, i.e 'a < b' symbolically tells you that a is less than b if the first
predicate happens to be true no matter what the actual comparison (if any)
happens to be.

kind regards,

Jos
Reply