Does a program with std::map<T*, U> have well-defined behaviour? [duplicate]

Question

Comparing pointers to unrelated objects has unspecified results.

That would seem to suggest that this program may have undefined behaviour, at the very least because we cannot guarantee a strict weak ordering on the key type:

#include <map>

int main()
{
    int x = 0, y = 1;
    bool arbitrary = false;

    std::map<int*, bool> m{
       {&x, arbitrary},
       {&y, arbitrary}
    };
}

More generally, then, can we say that a map with pointer keys is a dangerous* proposition? Or is there some special rule we can lean on here?

^{* Academically speaking, that is; in reality I'm not aware of mainstream implementations that will actually raise hell over comparing arbitrary pointers.}

Luigi

The question is answered in Is is valid to construct std::set of pointer type? – Nodical

@LanguageLawyer You are right – Luigi

Answer 1

Yes, because std::map default comparison operator is std::less, which, unlike the standard comparison operator, is completely defined for pointer types.

[comparisons#2]

For templates less, greater, less_­equal, and greater_­equal, the specializations for any pointer type yield a result consistent with the implementation-defined strict total order over pointers ([defns.order.ptr]).

The implementation-defined strict total order over pointers is defined in [defns.order.ptr] as:

implementation-defined strict total ordering over all pointer values such that the ordering is consistent with the partial order imposed by the builtin operators <, >, <=, >=, and <=>

Scapolite

Oh yeah haha. Nice one – Luigi

Interesting, that directly violates [expr.rel]/4, no? – Kimbro

@Kimbro As I understand this, the standard imposes implementation to have a strict total order over all pointers, but this order is not presented through built-in operators but only through std::less-like functors. So there are two different "orders" (one implementation-specific usable through std::less, and one for built-in operators), and they have to be consistent when both are defined (same-array / members of same object). – Scapolite

But it says "order imposed by the builtin operators < ..." ;) – Kimbro

@Kimbro The "implementation-defined strict total order over pointers" must be consistent with the standard-defined partial order imposed by the builtin operators. – Scapolite

@Kimbro A valid implementation is allowed to produce false for both p1 < p2 and p2 < p1 when p1 and p2 do not fall into the scope defined by [expr.rel]/4, but at least one of std::less{}(p1, p2) or std::less{}(p2, p1) must be true. – Scapolite

@L.F. According to eel.is/c++draft/comparisons#2, even the void-specialization should provide a strict total order. – Scapolite

@Scapolite It's actually LWG2450, which was resolved as of C++17. I gotta learn more ... – Microwave

Answer 2

std::less (default comparer of std::map) has special treatment about pointer allowing that:

A specialization of std::less for any pointer type yields a strict total order, even if the built-in operator< does not.

And about

can we say that a map with pointer keys is a dangerous proposition?

So it is fine in general.

Additional precaution should be taken with const char* key:

We compare pointers and not string content (mostly beginner confusions).

C-string literals with same content have no guaranty to be equals:

"literal" == "literal"; // Not guaranteed
"literal" < "literal"; // false .. or true

Alter

OTOH in a scope where a static variable is guaranteed to exist in one instance in the program, every source code instance of a literal string is guaranteed to have one well defined address, so inline void *literal() { return "literal";} guarantees that literal()==literal(). OTOH the same literal string in diff file static functions in diff TU have no such guarantee. – Emelinaemeline

Answer 3

std::map use std::less that have a specialization for pointer type :

A specialization of std::less for any pointer type yields a strict total order, even if the built-in operator< does not. The strict total order is consistent among specializations of std::less, std::greater, std::less_equal, and std::greater_equal for that pointer type, and is also consistent with the partial order imposed by the corresponding built-in operators (<, >, <= and >=).

For a more specific description i leave you 2 links:

std::less first link

std::less second link

Lepidopterous

Answer 4

that is; in reality I'm not aware of mainstream implementations that will actually raise hell over comparing arbitrary pointers.

Depends on what hell means. Hell isn't just crashing right away or scrambling memory with random data. It could be giving indeterminate results to what should be a deterministic function.

GCC was known to optimize pointer comparisons on objects known to point to related (virtual) (sub) objects of different complete objects A and B: anything based on &A would compare differently to anything based on &B, even &A+1, even when the address were actually the same. I don't know if that was observed in C or in C++, but your question is pretty much C/C++ (and applies to qsort too).

That is, the result of a pointer comparison would depend on the known origin of a pointer. That mean that depending on optimization level, inlining context, translation unit, etc. a comparison could give different results.

So yes it could break down on at least some versions of a popular compiler if you did these pointer comparisons.

Which you don't as std::map is not defined in term operator< but in term of std::less.

Emelinaemeline

Granted; "raise hell" I suppose is left-over wording from an earlier revision of the question when I thought the pointer comparison itself might have UB; a broken ordering still could but that's not what the quoted bit says. I should have updated that too. But if I had, I wouldn't have received this helpful addition :) – Luigi