<p>This is something that has slightly annoyed me for a while. A map as a mathematical object (function) is by default &quot;unordered&quot;, and the same is for maps as a data structure AKA associative arrays or dictionaries (python). So why did they choose to name the ordered map (usually a binary search tree) <code>std::map</code> and the map data structure (usually a hashmap) <code>std::unordered_map</code>, when <code>std::ordered_map</code> for the ordered map and <code>std::map</code> for the map data structure makes more sense?</p>
<p>For comparison, I'm not sure how browsers implement ES6 <code>Map</code> objects (the standard only seems to require sub-linear time operations), but they only preserve insertion order, so aren't &quot;ordered&quot; in the usual sense.</p>

<standard-library><c++><history><javascript>
Why did C++ standard library name the containers map and unordered_map instead of map and ordered_map?
CC BY-SA 4.0
2024-07-30T12:14:01.327Z
*" A map as a mathematical object (function)"* ─ This assumes that mathematical functions are the correct model for maps/dictionaries; but functions must define a result for all inputs, whereas dictionaries need not have a value associated with every key. Even then, other mental models such as "a table with two columns" are also viable, and tables naturally have their rows in some order.
kaya3
CC BY-SA 4.0
2024-07-30T13:10:57.447Z
@kaya3 every map/dictionary implementation I've seen has to have key-value pairs, even if the value is a null value. The table example is interesting too because the relational model for data doesn't have any concept of row order.
qwr
CC BY-SA 4.0
2024-07-30T13:14:08.823Z
I didn't mean the relational model, I meant actual tables, as in two-dimensional grids with actual rows and columns. The relational model is an abstraction of that; it's more natural to ask why the relational model is unordered, than to ask why table rows are ordered.
kaya3
CC BY-SA 4.0
2024-07-30T13:28:29.917Z
Yes, that's true. Map in every other language I've used has not imposed any kind of key order.
qwr
<p>Historical accident.  <code>map</code> was part of the original Standard Template Library approved by <a href="https://en.wikipedia.org/wiki/Standard_Template_Library" rel="nofollow noreferrer">ANSI/ISO in 1994</a>.  <code>std::unordered_map</code> was added to the C++ standard library with <a href="https://en.wikipedia.org/wiki/C%2B%2B11" rel="nofollow noreferrer">C++ 11</a>.</p>

CC BY-SA 4.0
2024-07-19T03:24:31.950Z
2024-07-19T03:24:31.950Z
Mark
<p>I think a major reason is that a <code>std::map</code> is not <em>ordered</em>, so calling it a ordered_map would be confusing.  The term <em>ordered map</em> usually refers to a data structure that preserves items in an <em>order</em> (like a <code>list</code> or <code>vector</code>) and ALSO supports fast lookup by key.  The order is independent of the key type (and different ordered maps may contain the same keys and values in a different order).</p>
<p>Maybe you could call <code>std::map</code> a <code>sorted_map</code> (as it stores items sorted by key)</p>

CC BY-SA 4.0
2024-07-19T11:54:42.877Z
2024-07-19T12:05:20.287Z
2024-07-19T12:05:20.287Z
Chris Dodd
CC BY-SA 4.0
2024-07-19T14:22:38.633Z
I'd say it is ordered, given that the total order maintained is on the keys. Python calls one of its collections objects OrderedDict that preserves insertion order like your terminology. (Apparently to support insertion order and key lookup, it has a doubly linked list and *second dict* for that linked list...) I'm totally fine with the name sorted_map and it's probably clearer, but the main point is that a unqualified "map" is  unordered/unsorted.
qwr
CC BY-SA 4.0
2024-07-19T22:29:19.847Z
std::map entries are absolutely ordered. They may not be linear in memory, but neither are the nodes in std::list. Every std::map has a comparator, which defines the order. For a type to be "ordered" simply means that for any elements of the type, a b, and c, less(a, b) implies !less(b, a), less(a, a) is false, and less(a, b) && less(b, c) implies less(a, c). The order is "independent of the key type", but dependent upon the comparator (which may be customized per key type).
Lawnmower Man
CC BY-SA 4.0
2024-07-21T11:16:43.010Z
The fact that the name `unordered_map` was selected for hash-maps _specifically_ to highlight the difference with `map` makes it pretty clear that from the C++ standard point of view `map` is considered to be ordered. Also, CS uses "Partial Order" and "Total Order" to describe comparison properties...
Matthieu M.
<p>The short answer: Historical reasons.</p>
<p>Alexander Stepanov's philosophy was always that <a href="http://stepanovpapers.com/musser94algorithmoriented.pdf" rel="noreferrer">the <em>algorithms</em> come first</a>. One analogy he always liked was with mathematics. When mathematicians <em>present</em> their work, they generally start with the axioms and work forwards. But when they are actually <em>developing</em> their work, they generally start with the interesting theorems and work backwards.</p>
<p>It's the similar story with the Standard Template Library. He believed that the interesting <em>algorithms</em> come first, and the <em>data structures</em> and their APIs get designed around them. This was especially important if the algorithms were to be generic.</p>
<p>The very earliest versions of the libraries that eventually became Standard Template Library (e.g. the Ada Generic Library Linear Data Structure Packages) didn't include associative containers such as maps and multimaps. Notably, they were also not pitched to the C++ standards committee in <a href="http://stepanovpapers.com/Stepanov-The_Standard_Template_Library-1994.pdf" rel="noreferrer">the earliest presentations</a>.</p>
<p>Since the Ada Generic Library and original Standard Template Library were designed around algorithms, the interesting algorithms were generally on containers of a single type. When you have containers of single types, it's more or less clear what an &quot;iterator&quot; should look like, for example.</p>
<p>But associative containers have <em>two</em> interesting types: a &quot;key&quot; type and a &quot;value&quot; type. So what does a generic algorithm &quot;iterate&quot; on? Keys? Key-value pairs? We know what Stepanov and Lee eventually settled on, but it had to be worked out.</p>
<p>And that's just the API between containers and generic algorithms. The other difficult part of the API is how a programmer should present their own user-defined types to the STL.</p>
<p>C++ has native syntax for overloading the less-than and equal-test operators. And these need to be implemented already to write generic sort algorithms. Programmers find it quite easy to provide a less-than comparison for their user-defined types compared to, say, a radix query, which is why &quot;library&quot; sort functions tend to be comparison-based rather than radix-based.</p>
<p>In that context, it was clear that implementing associative containers that are based on comparisons was going to be easier and less controversial than ones based on hashing. Hash tables would require designing an API for providing user-declared hash functions. Unlike comparison, C++ didn't have &quot;native&quot; hash function support, so it needed to be designed, and it wasn't clear what the &quot;right&quot; design should be.</p>
<p>(This is a little off track, but it's also worth noting that the research community also wasn't clear as to whether or not &quot;generic&quot; algorithms on hash tables should be <a href="https://lafstern.org/matt/segmented.pdf" rel="noreferrer">&quot;aware&quot; of hash table structure</a> in some way.)</p>
<p>There was an <a href="https://www.open-std.org/jtc1/sc22/wg21/docs/papers/1995/N0605.pdf" rel="noreferrer">early proposal</a> for adding hash tables to the C++ standard library, more or less tracking HP's implementation, but it was too late to make it into the C++98 standard. What happened in the mean time is that third-party vendors wrote their own <code>hash_map</code>/<code>hash_set</code> (and the multi-variants) implementations that were all broadly similar, but subtly mutually incompatible.</p>
<p>The Boost project was started in 1998 by members of the C++ committee, in part to be a test lab for new proposals to be added to the C++ standards library. When it came time to experiment with hash tables, in around 2003, Jeremy Maitin-Shepard chose <code>unordered</code> rather than <code>hash</code> for Boost's implementation, essentially because none of the vendors had chosen that name, so there's no chance that they would clash.</p>
<p>Boost's proposal eventually was adopted into TR1, and subsequently C++11.</p>
<p>TL;DR version:</p>
<p>Languages like Perl, Python, and ECMAScript started with the data structures and did the algorithms later, which is why the hash tables get the simpler names. C++ started with the algorithms and did the data structures later, which is why the ordered search trees got the simpler names.</p>

CC BY-SA 4.0
2024-07-19T03:25:06.090Z
2024-07-19T03:41:41.520Z
2024-07-19T03:41:41.520Z
Pseudonym
CC BY-SA 4.0
2024-07-19T03:51:27.650Z
Fascinating history. It doesn't make sense to me to start with algorithms before even having data structures to support them. Very often the algorithm to be efficiently implemented depends critically on the data structure.
qwr
CC BY-SA 4.0
2024-07-19T06:22:52.480Z
@qwr Stepanov's crucial observation is that algorithms don't depend on the data structure specifically, but only on what he called an "iterator category". Quick sort, quick select, etc all work on random-access containers, and hence random access iterators. Similarly, sorting a singly-linked list and a doubly-linked list can use the same algorithm. Sort-decreasing and sort-increasing can also use the same algorithm, only with iterators reversed. And algorithms like "sum all the elements" only ever need generic forward iteration.
Pseudonym
CC BY-SA 4.0
2024-07-19T14:44:34.570Z
@Pseudonym, and that is why the C++ algorithms are more advanced and flexible than most other languages while simultaneously being a huge pain to use (iterator pair based rather than container based) and hard for a newer developer to reason about.  

The Ranges library tries to make them somewhat easier to use but ranges themselves are hard to use vs Java streams or C# LINQ.
Jeremy Richards
CC BY-SA 4.0
2024-07-19T17:48:43.863Z
That must be why I have to write out `std::sort(s.begin(), s.end());` instead of `std::sort(s);` like a normal language
qwr
CC BY-SA 4.0
2024-07-19T17:51:10.100Z
I understand that many algorithms can use any kind of random access iterator or it may be possible to swap a hashmap for a search tree. I don't like the design of everything being based on iterators without simple container equivalents that other languages seem to support just fine.
qwr
CC BY-SA 4.0
2024-07-19T22:23:55.643Z
@qwr iterators are better because they don't need to be backed by a container at all. You can call algorithms on file iterators, socket stream iterators, or any other data source for which the iterator category can be suitably defined. You can even implement comprehensions for infinite "containers".
Lawnmower Man
CC BY-SA 4.0
2024-07-20T09:10:40.617Z
We can argue about what's "better" all day. There is a certain amount of pain in making any code generic, especially in an imperative language. Moving the burden from the algorithm writer to the data structure implementor was an interesting and practical design choice. Perhaps even remarkable, when you consider that the world was OO crazy in the late 80s and early 90s, and the STL didn't contain a single virtually inherited anything.
Pseudonym
CC BY-SA 4.0
2024-07-20T15:01:05.627Z
@LawnmowerMan I don't know much C++, but is "iterator" just an alias for "interface" whereas "container" specifically means "concrete data structure"? But regardless, it still doesn't make much sense that algorithms take two arguments (for begin and end of an object) instead of a single one (just the object itself). The objects can still be implemented arbitrarily instead of being backed by a concrete in-memory data structure.
Bergi
CC BY-SA 4.0
2024-07-20T15:22:05.510Z
@Bergi Iterator *is-a* interface. Technically, a container is an "iterator generator". Since containers return their iterators separately (begin, end, typically), it made more sense to pass them that way. Forcing them to always be passed as std::pair would be considered ugly by most C++ programmers. A search returns a *single* iterator, rather than a *range*. You combine that with another iterator you have to make your actual range. Iterators could have been implemented as ranges, but that would have made them more complicated. You can build ranges on top of iterators, but vice versa is costly
Lawnmower Man
CC BY-SA 4.0
2024-07-20T15:29:26.207Z
@LawnmowerMan I think what qwr suggested with `std::sort(s)` is that `sort` should take such a range instead of two iterators. The range interface could be implemented by pairs of iterators, by containers themselves, and by any other custom data source. Why that is not the case in C++, but is in most other "*normal languages*", is probably also just historical accident.
Bergi
CC BY-SA 4.0
2024-07-21T01:08:03.753Z
@Bergi I tried to explain that many algorithms in the STL return a *single iterator*. That could be implemented via a trivial range, but that is also more wasteful, and the STL was explicitly designed to be as efficient as possible.
Lawnmower Man
CC BY-SA 4.0
2024-07-21T10:54:45.110Z
@LawnmowerMan Nobody was saying that the *return* value should change, a single iterator makes total sense for algorithms like `find`. What is awkward is having to pass two iterators as the *argument* values where a single range object would be better suited. Or are you saying that for some reason we can have only iterators or ranges but not both?
Bergi
CC BY-SA 4.0
2024-07-21T14:18:09.797Z
Surely the choice of "unordered" vs "hash" was to make no mention of the implementation - all of the STL container names describe the interface, not how it must be implemented.
OrangeDog
CC BY-SA 4.0
2024-07-21T14:36:26.563Z
@Bergi C++20 introduced std::ranges::sort. Still I don't like there isn't vector.sort() or std::sort(v) directly.
qwr
CC BY-SA 4.0
2024-07-22T04:47:20.463Z
Ranges only coming fairly late (and thus still not in widespread use) is one reason that algorithms are more awkward in C++ than in other languages.  Another is that C++'s lambdas are significantly more verbose; most languages allow you to elide a lot more of the syntax (`x => x.y` vs. `[](auto const& x) { return x.y; }` for example).  There are some benefits to this, of course (such as avoiding excessive capturing, and allowing explicit moving), but it still makes things more awkward.
Miral
CC BY-SA 4.0
2024-07-27T00:21:25.140Z
@OrangeDog You'd think so, but no. Obviously, to be compatible with `unordered`, you need to specify a hash function for your type. But even in TR1, the unordered containers had member functions for querying the load factor and iterating over buckets, which essentially dictates the underlying data structure. Compare this with `map` or `set`, which could use almost any ordered search structure that doesn't move elements.
Pseudonym
# Why did C++ standard library name the containers map and unordered_map instead of map and ordered_map?
Posted by: username_0 on 2024-07-19
This is something that has slightly annoyed me for a while. A map as a mathematical object (function) is by default "unordered", and the same is for maps as a data structure AKA associative arrays or dictionaries (python). So why did they choose to name the ordered map (usually a binary search tree) `std::map` and the map data structure (usually a hashmap) `std::unordered_map`, when `std::ordered_map` for the ordered map and `std::map` for the map data structure makes more sense?

For comparison, I'm not sure how browsers implement ES6 `Map` objects (the standard only seems to require sub-linear time operations), but they only preserve insertion order, so aren't "ordered" in the usual sense.
**Tags:** standard-library c++ history javascript
> **Comments:**
> **username_1**: *" A map as a mathematical object (function)"* ─ This assumes that mathematical functions are the correct model for maps/dictionaries; but functions must define a result for all inputs, whereas dictionaries need not have a value associated with every key. Even then, other mental models such as "a table with two columns" are also viable, and tables naturally have their rows in some order.  
> **username_0**: @kaya3 every map/dictionary implementation I've seen has to have key-value pairs, even if the value is a null value. The table example is interesting too because the relational model for data doesn't have any concept of row order.  
> **username_1**: I didn't mean the relational model, I meant actual tables, as in two-dimensional grids with actual rows and columns. The relational model is an abstraction of that; it's more natural to ask why the relational model is unordered, than to ask why table rows are ordered.  
> **username_0**: Yes, that's true. Map in every other language I've used has not imposed any kind of key order.  
---
## 3 answers
### Answer by username_6 on 2024-07-19. Score: 21 | Accepted answer
The short answer: Historical reasons.

Alexander Stepanov's philosophy was always that [the *algorithms* come first](http://stepanovpapers.com/musser94algorithmoriented.pdf). One analogy he always liked was with mathematics. When mathematicians *present* their work, they generally start with the axioms and work forwards. But when they are actually *developing* their work, they generally start with the interesting theorems and work backwards.

It's the similar story with the Standard Template Library. He believed that the interesting *algorithms* come first, and the *data structures* and their APIs get designed around them. This was especially important if the algorithms were to be generic.

The very earliest versions of the libraries that eventually became Standard Template Library (e.g. the Ada Generic Library Linear Data Structure Packages) didn't include associative containers such as maps and multimaps. Notably, they were also not pitched to the C++ standards committee in [the earliest presentations](http://stepanovpapers.com/Stepanov-The_Standard_Template_Library-1994.pdf).

Since the Ada Generic Library and original Standard Template Library were designed around algorithms, the interesting algorithms were generally on containers of a single type. When you have containers of single types, it's more or less clear what an "iterator" should look like, for example.

But associative containers have *two* interesting types: a "key" type and a "value" type. So what does a generic algorithm "iterate" on? Keys? Key-value pairs? We know what Stepanov and Lee eventually settled on, but it had to be worked out.

And that's just the API between containers and generic algorithms. The other difficult part of the API is how a programmer should present their own user-defined types to the STL.

C++ has native syntax for overloading the less-than and equal-test operators. And these need to be implemented already to write generic sort algorithms. Programmers find it quite easy to provide a less-than comparison for their user-defined types compared to, say, a radix query, which is why "library" sort functions tend to be comparison-based rather than radix-based.

In that context, it was clear that implementing associative containers that are based on comparisons was going to be easier and less controversial than ones based on hashing. Hash tables would require designing an API for providing user-declared hash functions. Unlike comparison, C++ didn't have "native" hash function support, so it needed to be designed, and it wasn't clear what the "right" design should be.

(This is a little off track, but it's also worth noting that the research community also wasn't clear as to whether or not "generic" algorithms on hash tables should be ["aware" of hash table structure](https://lafstern.org/matt/segmented.pdf) in some way.)

There was an [early proposal](https://www.open-std.org/jtc1/sc22/wg21/docs/papers/1995/N0605.pdf) for adding hash tables to the C++ standard library, more or less tracking HP's implementation, but it was too late to make it into the C++98 standard. What happened in the mean time is that third-party vendors wrote their own `hash_map`/`hash_set` (and the multi-variants) implementations that were all broadly similar, but subtly mutually incompatible.

The Boost project was started in 1998 by members of the C++ committee, in part to be a test lab for new proposals to be added to the C++ standards library. When it came time to experiment with hash tables, in around 2003, Jeremy Maitin-Shepard chose `unordered` rather than `hash` for Boost's implementation, essentially because none of the vendors had chosen that name, so there's no chance that they would clash.

Boost's proposal eventually was adopted into TR1, and subsequently C++11.

TL;DR version:

Languages like Perl, Python, and ECMAScript started with the data structures and did the algorithms later, which is why the hash tables get the simpler names. C++ started with the algorithms and did the data structures later, which is why the ordered search trees got the simpler names.
> **Comments:**
> **username_0** (2024-07-19): Fascinating history. It doesn't make sense to me to start with algorithms before even having data structures to support them. Very often the algorithm to be efficiently implemented depends critically on the data structure.  
> **username_6** (2024-07-19): @qwr Stepanov's crucial observation is that algorithms don't depend on the data structure specifically, but only on what he called an "iterator category". Quick sort, quick select, etc all work on random-access containers, and hence random access iterators. Similarly, sorting a singly-linked list and a doubly-linked list can use the same algorithm. Sort-decreasing and sort-increasing can also use the same algorithm, only with iterators reversed. And algorithms like "sum all the elements" only ever need generic forward iteration.  
> **username_7** (2024-07-19): @Pseudonym, and that is why the C++ algorithms are more advanced and flexible than most other languages while simultaneously being a huge pain to use (iterator pair based rather than container based) and hard for a newer developer to reason about.  

The Ranges library tries to make them somewhat easier to use but ranges themselves are hard to use vs Java streams or C# LINQ.  
> **username_0** (2024-07-19): That must be why I have to write out `std::sort(s.begin(), s.end());` instead of `std::sort(s);` like a normal language  
> **username_0** (2024-07-19): I understand that many algorithms can use any kind of random access iterator or it may be possible to swap a hashmap for a search tree. I don't like the design of everything being based on iterators without simple container equivalents that other languages seem to support just fine.  
> **username_4** (2024-07-19): @qwr iterators are better because they don't need to be backed by a container at all. You can call algorithms on file iterators, socket stream iterators, or any other data source for which the iterator category can be suitably defined. You can even implement comprehensions for infinite "containers".  
> **username_6** (2024-07-20): We can argue about what's "better" all day. There is a certain amount of pain in making any code generic, especially in an imperative language. Moving the burden from the algorithm writer to the data structure implementor was an interesting and practical design choice. Perhaps even remarkable, when you consider that the world was OO crazy in the late 80s and early 90s, and the STL didn't contain a single virtually inherited anything.  
> **username_8** (2024-07-20): @LawnmowerMan I don't know much C++, but is "iterator" just an alias for "interface" whereas "container" specifically means "concrete data structure"? But regardless, it still doesn't make much sense that algorithms take two arguments (for begin and end of an object) instead of a single one (just the object itself). The objects can still be implemented arbitrarily instead of being backed by a concrete in-memory data structure.  
> **username_4** (2024-07-20): @Bergi Iterator *is-a* interface. Technically, a container is an "iterator generator". Since containers return their iterators separately (begin, end, typically), it made more sense to pass them that way. Forcing them to always be passed as std::pair would be considered ugly by most C++ programmers. A search returns a *single* iterator, rather than a *range*. You combine that with another iterator you have to make your actual range. Iterators could have been implemented as ranges, but that would have made them more complicated. You can build ranges on top of iterators, but vice versa is costly  
> **username_8** (2024-07-20): @LawnmowerMan I think what qwr suggested with `std::sort(s)` is that `sort` should take such a range instead of two iterators. The range interface could be implemented by pairs of iterators, by containers themselves, and by any other custom data source. Why that is not the case in C++, but is in most other "*normal languages*", is probably also just historical accident.  
> **username_4** (2024-07-21): @Bergi I tried to explain that many algorithms in the STL return a *single iterator*. That could be implemented via a trivial range, but that is also more wasteful, and the STL was explicitly designed to be as efficient as possible.  
> **username_8** (2024-07-21): @LawnmowerMan Nobody was saying that the *return* value should change, a single iterator makes total sense for algorithms like `find`. What is awkward is having to pass two iterators as the *argument* values where a single range object would be better suited. Or are you saying that for some reason we can have only iterators or ranges but not both?  
> **username_9** (2024-07-21): Surely the choice of "unordered" vs "hash" was to make no mention of the implementation - all of the STL container names describe the interface, not how it must be implemented.  
> **username_0** (2024-07-21): @Bergi C++20 introduced std::ranges::sort. Still I don't like there isn't vector.sort() or std::sort(v) directly.  
> **username_10** (2024-07-22): Ranges only coming fairly late (and thus still not in widespread use) is one reason that algorithms are more awkward in C++ than in other languages.  Another is that C++'s lambdas are significantly more verbose; most languages allow you to elide a lot more of the syntax (`x => x.y` vs. `[](auto const& x) { return x.y; }` for example).  There are some benefits to this, of course (such as avoiding excessive capturing, and allowing explicit moving), but it still makes things more awkward.  
> **username_6** (2024-07-27): @OrangeDog You'd think so, but no. Obviously, to be compatible with `unordered`, you need to specify a hash function for your type. But even in TR1, the unordered containers had member functions for querying the load factor and iterating over buckets, which essentially dictates the underlying data structure. Compare this with `map` or `set`, which could use almost any ordered search structure that doesn't move elements.  
---
### Answer by username_2 on 2024-07-19. Score: 4
Historical accident. `map` was part of the original Standard Template Library approved by [ANSI/ISO in 1994](https://en.wikipedia.org/wiki/Standard_Template_Library). `std::unordered_map` was added to the C++ standard library with [C++ 11](https://en.wikipedia.org/wiki/C%2B%2B11).
---
### Answer by username_3 on 2024-07-19. Score: 0
I think a major reason is that a `std::map` is not *ordered*, so calling it a ordered\_map would be confusing. The term *ordered map* usually refers to a data structure that preserves items in an *order* (like a `list` or `vector`) and ALSO supports fast lookup by key. The order is independent of the key type (and different ordered maps may contain the same keys and values in a different order).

Maybe you could call `std::map` a `sorted_map` (as it stores items sorted by key)
> **Comments:**
> **username_0** (2024-07-19): I'd say it is ordered, given that the total order maintained is on the keys. Python calls one of its collections objects OrderedDict that preserves insertion order like your terminology. (Apparently to support insertion order and key lookup, it has a doubly linked list and *second dict* for that linked list...) I'm totally fine with the name sorted_map and it's probably clearer, but the main point is that a unqualified "map" is  unordered/unsorted.  
> **username_4** (2024-07-19): std::map entries are absolutely ordered. They may not be linear in memory, but neither are the nodes in std::list. Every std::map has a comparator, which defines the order. For a type to be "ordered" simply means that for any elements of the type, a b, and c, less(a, b) implies !less(b, a), less(a, a) is false, and less(a, b) && less(b, c) implies less(a, c). The order is "independent of the key type", but dependent upon the comparator (which may be customized per key type).  
> **username_5** (2024-07-21): The fact that the name `unordered_map` was selected for hash-maps _specifically_ to highlight the difference with `map` makes it pretty clear that from the C++ standard point of view `map` is considered to be ordered. Also, CS uses "Partial Order" and "Total Order" to describe comparison properties...  
---
