7

There's this other question asking about how comparing pointers is supposed to be interpreted wrt the C++ Std.

So I was wondering what the C++ Std has to say about using pointers as keys in ordered standard library (STL) containers -- i.e. is one allowed to have

std::map<T1*, T2>

and is this due to the specification of std::less or builtin operator <?

Community
  • 1
  • 1
Martin Ba
  • 37,187
  • 33
  • 183
  • 337
  • btw, do you want to use the addresses as key or the value of the things they point to as key? In the latter case you would have to provide a custom comparator – sellibitze Feb 06 '11 at 12:17
  • related: [checking if pointer points within an array](http://stackoverflow.com/questions/4657976/) – fredoverflow Feb 06 '11 at 12:19

4 Answers4

12

Yes, because it uses std::less, which is required to result in a total order even if < doesn't. (< would be allowed to treat different pointers from distinct sequences as equal, which would result in an odd behaviour of map etc if you insert pointers from different sequences).

etarion
  • 16,935
  • 4
  • 43
  • 66
  • 1
    To phrase this slightly different: To quote sellibitze from a comment to an answer below: "... it's safe to use pointers as keys in associative containers. But this has nothing to do with the less-than operator because std::less is the default comparator for these containers and C++ makes special guarantees for std::less in case T is a pointer type. ..." – Martin Ba Feb 08 '11 at 11:35
3

I'd like to add another reason to not do this. If you are using pointers in this way, and if you happen to have a bug that depends on the ordering of the elements of a container, then it will be very difficult to find. Even if your program seems to be completely deterministic, it will not be. The order of the elements in a container depends on the algorithm the memory allocator uses, which is completely out of your control. If you run the same example muliple times without restarting your program, some may fail and others succeed.

This is the voice of bitter experience. I did this with a debugger project once, where I had containers filled with C++ symbols. When I needed to sort the symbols, I ended up with symbols which are different, but which have the same name (think overloaded functions) and which were identical in all other respect. So, in this case I compared them as a last resort by the address of the symbol object. I ran into several bugs which were apparently non-deterministic, where the non-determinism was caused by just this phenomenon. Sometimes it took more than 10 or 15 attempts to reproduce the problems. I eventually took the time to eliminate sorting by addresses, and that saved me a lot of trouble over the longer term.

With that said, I won't say I haven't done this recently. But every time I do it I feel like it's a mistake.

Bill White
  • 41
  • 6
0

"They may valid but don't" is the answer I would give.

Obviously there is the issue of comparability that you raise, but the reason you don't want to is because of the lack of reference management on "vanilla" pointers. It's very easy for the object to be deleted without it being removed from the container, resulting in an invalid pointer and an access violation next time you go to access it.

dlanod
  • 8,664
  • 8
  • 54
  • 96
  • That's not necessarily valid- things like unique_ptr or shared_ptr may well provide comparitive operators based on the underlying pointer. – Puppy Feb 06 '11 at 12:23
-3

Yes. Pointers are comparable via operator<().

If the pointers do not point to the elements of the same array or elements within the same object the c++ standard says the behavior is unspecified [expr.rel].

The standard says unspecified behavior means it's implementation defined [defns.unspecified].

If your compiler guaranties a strict weak order of pointers you can use any pointer with associative containers.

Most compilers do pointer comparison by comparing the memory addresses. On most architectures this comparison forms a strict weak order.

Therefore it's safe to use pointers as keys.

joke
  • 654
  • 9
  • 11
  • only if they point to elements of the same array. The c++ standard makes stronger guarantees for std::less which is the default for ordered associative containers – sellibitze Feb 06 '11 at 12:15
  • @sellibitze: Pointers are not related to arrays. Pointers to elements of different arrays are less-comparable. – joke Feb 06 '11 at 12:20
  • 1
    @joke: No, the standard does not allow comparing arbitrary pointers with `<`. – fredoverflow Feb 06 '11 at 12:38
  • 1
    The C++ standard places no guarantees on that. But chances are, that it does what you want on most implementations. fyi: I didn't downvote. But maybe I should -- given that this answer is wrong *and* you ignore criticism. – sellibitze Feb 06 '11 at 12:44
  • 1
    §5.9/2, second bullet point: "If two pointers p and q of the same type point to different objects that are not members of the same object or elements of the same array or to different functions, or if only one of them is null, the results of pq, p<=q, and p>=q are unspecified." – sellibitze Feb 07 '11 at 08:36
  • The fact that it is unspecified is not the same as undefined. If it is unspecified it means that the expected result is not determined by the standard, so before hand, given the code: `int *a = new int, *b = new int;`, and as most people will expect, whether `a < b` or `b < a` is an unknown. On the other hand that does not mean that the requirements of std::less are broken, `<` applied to pointers can determine a partial order. – David Rodríguez - dribeas Feb 07 '11 at 09:14
  • @sellibitze: Same here. Just because the value is unspecified doesn't mean is not usable for comparison. It is guaranteed not to throw an exception so it's usable for comparison even if the compared result doesn't make sense. It's the programmers responsibility not to add items to the map which which may cause in unspecified behavior if compared. Nevertheless I think there isn't a single c++ compiler which will not compare the memory addresses and return a truly unspecified result. – joke Feb 07 '11 at 09:50
  • Don't weasel yourself out of this. If the result of p – sellibitze Feb 07 '11 at 12:56
  • @David Rodriguez: Where das the standard say that < defines a partial order on all possible pointers? It doesn't say that. Also, see my above comment about equivalence relations. I'm sure you don't want the map to treat unequal pointers as equal´just because !(p – sellibitze Feb 07 '11 at 13:00
  • @sellibitze: The standard says it's undefined behavior, meaning it's up to the implementation how it works [defns.unspecified]. Commonly arbitrary comparison of pointers returns the result of comparing the memory addresses. If they form a strict weak order among all possible pointers is implementation defined. If your implementation guaranties a strict weak order among pointers it absolutely possible to use any pointer within an associative container. If it doesn't guaranty a strict weak order the programmers should only use pointers to elements of the same array. – joke Feb 07 '11 at 13:59
  • @joke: The standard says unspecified behavior. And to be clear: on common architectures memory addresses form a strict weak order. So it's perfectly safe to use pointers as a keys of associative containers. – joke Feb 07 '11 at 14:37
  • @joke: depends on your definition of "perfectly safe". Mine doesn't include the use of unspecified behaviour. The standard places no guarantee on < being a partial ordering on arbitrary pointers and even if it was a partial ordering there is no guarantee that this partial ordering behaves like you want it to w.r.t. equivalence of keys. – sellibitze Feb 07 '11 at 17:54
  • @sellibitze: The behavior is "unspecified" not "undefined". "unspecified" means implementation defined [defns.unspecified]. If you don't like implementation defined behavior you can't even calculate a sum like 1+1 because the standard doesn't guarantee the sizeof(int) being greater than 0. – joke Feb 07 '11 at 18:57
  • @sellibitze: I am not claiming that the guarantees a partial order, only that *unspecified* is completely different to *undefined*. A program with undefined behavior can yield different results in different runs (or compilations): `i++ + ++i` can yield different results in different runs. But that is different from *unspecified*. The standard does require a particular ordering among objects in the *same object or array*, which means that it places a requirement on the compiler for the layout of members, or elements in the array. – David Rodríguez - dribeas Feb 07 '11 at 21:22
  • ... as in `struct test { int a,b; }` the compiler is required to lay out `a` and `b` such that in `test t;`, the relation `&t.a < &t.b` is true. It does not, on the other hand place any requirement on the placement of unrelated objects, for example in `void foo() { int a, b; }`, the standard does not specify where `a` has to be laid with respect to `b`, that is what *unspecified* means. – David Rodríguez - dribeas Feb 07 '11 at 21:26
  • @joke: That's total nonsense. sizeof always evaluates to an integer that is at least 1 and int is guaranteed to be able to represent numbers from the range -32767...32767. I know that unspecified is not the same as undefined. But for the purpose of using < as comparator in an associative container for comparing arbitrary pointers "unspecified" is not good enough. Of course, you can pull out the "but on my machine it works" card and I have nothing against that. What I'm objecting to is that your answer promotes the idea that < is guaranteed to work for the intended use and this is not the case. – sellibitze Feb 07 '11 at 21:51
  • @sellibitze: the result of sizeof can be 0 in certain cases. And sizeof(int) is not required to be 2. It's required to be a least sizeof(char) which is 1 not 2. – joke Feb 07 '11 at 22:23
  • @joke: This is getting ridiculus. Of course, it's safe to use pointers as keys in associative containers. But this has nothing to do with the less-than operator because std::less is the default comparator for these containers and C++ makes special guarantees for std::less in case T is a pointer type. As for sizeof(int)==2, I did not claim such a thing. I'm starting to doubt your reading and comprehension skills. Also, you forgot to mention which cases you had in mind where you think sizeof may return 0. – sellibitze Feb 08 '11 at 10:13
  • @joke -1, this is very old but you really need to be downvoted on this until you correct it, it's the behavior of `std::less` that matters here, which the standard requires forms a total order. Even if `operator<` formed a strict weak order, it would not be safe to put pointer into containers using this relation because a weak order (unlike a total order) does not guarantee that every unique pointer belongs to the same equivalence class, only that the equivalence classes themselves can be ordered...thus you could `insert` two unique pointers into a set and have only one in the result. – Stephen Lin Mar 06 '13 at 06:10