Sign in to follow this  
DevFred

putting pointers to objects in a set

Recommended Posts

Can some C++ guru confirm I'm invoking undefined behavior?
#include <set>

class Player
{
    // exact contents irrelevant
};

int main()
{
    Player* a = new Player();
    Player* b = new Player();
    std::set<Player*> players;

    players.insert(a);
    players.insert(b);

    players.clear();
    delete b;
    delete a;
}
I don't want to spoil the fun, but it's obviously got to do with pointers ;)

Share this post


Link to post
Share on other sites
Quote:

5.9 Relational operators

If two pointers point to elements of the same array or one beyond the end of the array, the pointer to the object with the higher subscript compares higher. [...] Other pointer comparisons are unspecified.

Yup, there you have it. But what exactly does "unspecified" mean in this context? Is that less strong than "undefined"?

As I understand it, putting pointers to objects in an unordered_set should be ok, right?
Quote:

5.10 Equality operators

Pointers to objects or functions of the same type (after pointer conversions) can be compared for equality. Two pointers of the same type compare equal if and only if they are both null, both point to the same function, or both represent the same address.

Share this post


Link to post
Share on other sites
Quote:
Original post by DevFred
Quote:

5.9 Relational operators

If two pointers point to elements of the same array or one beyond the end of the array, the pointer to the object with the higher subscript compares higher. [...] Other pointer comparisons are unspecified.
Yup, there you have it. But what exactly does "unspecified" mean in this context? Is that less strong than "undefined"?
Much less strong than 'undefined':

Unspecified behavior also means that the code is also completely legal C++, but compilers may interpret it differently. The difference between implementation-defined behavior and unspecified behavior is that the compiler vendor is not required to describe what their particular compiler does. For example, when you cast an integer to an enum , the resulting enum value may in some cases be unspecified. (source)

However, an interesting side effect of that definition of 'unspecified', is that your original code is indeed legal C++. Or, in other words, C++ doesn't guarantee the order of elements in your set-of-pointers, but it does guarantee that an ordering will exist (and may differ between implementations).

Share this post


Link to post
Share on other sites
Hm, but as I understand it, "unspecified" could also mean that p < q always returns false if p and q do not point to elements of the same array, because the implementation can do whatever it wants...

Share this post


Link to post
Share on other sites
Because defining and specifying the behavior of a lot of that behavior would have performance impacts. Ex: indexing out array bounds with a pointer is undefined behavior. In order to define that behavior, you would then need to track the array bounds and the pointer aliases and do comparisons against those bounds.

Share this post


Link to post
Share on other sites
Quote:
Original post by DevFred
Can some C++ guru confirm I'm invoking undefined behavior?

*** Source Snippet Removed ***

I don't want to spoil the fun, but it's obviously got to do with pointers ;)


Yup. Failing to return a specific value from a function of type int is bad, and in the case of main() it should be explicitly return EXIT_SUCCESS; *nod nod nod*.

Yes, ok, the hidden < operator is wrong in this context. But memory has been flat since Windows 3.1 died, anywhere I've even been, so ordering by address is something I no longer worry about. It's all a big array now really.

On the other hand, there is rarely reason to order things by address. You just wouldn't use set for that, you're paying for useless ordering. Which in itself bugs me; I don't know why a set, which is not a term that implies ordering to me, has to be ordered in the first place. They should have been called set and ordered_set. Yeah. Someone fix the standard.

Share this post


Link to post
Share on other sites
Quote:

Yup. Failing to return a specific value from a function of type int is bad, and in the case of main() it should be explicitly return EXIT_SUCCESS;

It is permissible for main() to omit the return statement; the behavior is as if return 0 had been specified.

The standard considers EXIT_SUCCESS relevant directly to exit() (and the value of EXIT_SUCCESS is not specified), where its semantics are the same as 0. Since the return statement in main has the effect of leaving the function and calling std::exit with the return value, 0 is just as acceptable a value.

Share this post


Link to post
Share on other sites
Quote:
Original post by ScottMayo
Failing to return a specific value from a function of type int is bad

Wrong.
Quote:

3.6.1 Main function (5)

A return statement in main has the effect of leaving the main function (destroying any objects with automatic storage duration) and calling std::exit with the return value as the argument. If control reaches the end of main without encountering a return statement, the effect is that of executing
return 0;

Share this post


Link to post
Share on other sites
On the other hand, why a set? Why not a list? Isn't the only thing you get out of this that when you insert the same pointer more than once it has no effect? But why insert the same pointer more than once in the first place?

Share this post


Link to post
Share on other sites
Quote:
Original post by ScottMayo
On the other hand, there is rarely reason to order things by address. You just wouldn't use set for that, you're paying for useless ordering. Which in itself bugs me; I don't know why a set, which is not a term that implies ordering to me, has to be ordered in the first place. They should have been called set and ordered_set. Yeah. Someone fix the standard.
The primary issue I see is that unordered_set makes a very lousy set implementation. Sure, it fulfils the basic requirements (unique elements, quick insertion and inclusion testing), but how often do you use a set for just that? And implementing the set operations (union, intersection, difference, etc.) on an unordered_set is not a happy place to be...

Share this post


Link to post
Share on other sites
Quote:

3.6.1 Main function (5)

...If control reaches the end of main without encountering a return statement, the effect is that of executing
return 0;


Ick. I stand corrected, but what an ugly addition. Just what the language needed, a special case for main() that makes it look like int functions in general will return 0 if you fall out. I think I'll stick to return 0 (or the more correct EXIT_SUCCESS).

Share this post


Link to post
Share on other sites
Quote:
Original post by DevFred
I thought about reinterpret_cast, but the result of that would be just as unspecified, wouldn't it ;)
Doesn't casting a pointer to an integer immediately take you all the way into the realm of 'undefined'?
Quote:
Original post by ScottMayo
I think I'll stick to return 0 (or the more correct EXIT_SUCCESS).
It is the 'correct' part that keeps tripping you up - return 0 is equally correct, the standard guarantees it [smile]

Share this post


Link to post
Share on other sites
Quote:
Original post by swiftcoder
Quote:
Original post by DevFred
I thought about reinterpret_cast, but the result of that would be just as unspecified, wouldn't it ;)
Doesn't casting a pointer to an integer immediately take you all the way into the realm of 'undefined'?

No, just implementation defined, as long as the integer is large enough. From the standard, section 5.2.10 paragraphs 4 and 5:
Quote:

A pointer can be explicitly converted to any integral type large enough to hold it. The mapping function is implementation-defined....

A value of integral type or enumeration type can be explicitly converted to a pointer. A pointer converted to an integer of sufficient size (if any such exists on the implementation) and back to the same pointer type will have its original value; mappings between pointers and integers are otherwise implementation-defined.

Share this post


Link to post
Share on other sites
Quote:
Original post by swiftcoder
It is the 'correct' part that keeps tripping you up - return 0 is equally correct, the standard guarantees it [smile]


It guarantees... something.

http://bytes.com/groups/c/215177-exit_success-guaranteed-always-zero

See post #15. It's language lawyering at the hyper-fine-grained nitpick level, but he's right - there's a reason the standards committee didn't just outright define EXIT_SUCCESS as 0 explicitly, and the reason has to do with the influence of DEC on the C standards committee, back in the bad old days of VMS. EXIT_SUCCESS and 0 can mean different things, though both have to indicate "some kind of" success. The distinction probably died with VMS. But I learned EXIT_SUCCESS back in the day. :-)

Great. Next time I write a main(), I'm going to sit there for five minutes, fretting over return 0, return EXIT_SUCCESS, or }. And I'll do it even though I Know Perfectly Well it doesn't matter. *sigh*

Share this post


Link to post
Share on other sites
Quote:
Original post by SiCrane
A pointer converted to an integer of sufficient size (if any such exists on the implementation) and back to the same pointer type will have its original value


Which is all the OP needs; for that to work, distinct pointers must map to distinct integers, and integers have the necessary ordering properties for the set.

Share this post


Link to post
Share on other sites
I think the behaviour of the original snippet is defined. std::set uses std::less by default instead of op <. And std::less guarantees total ordering even for pointer types:
Quote:
ISO/IEC 14882:2003 20.3.3.8
For templates greater, less, greater_equal, and less_equal, the specializations for any pointer type yield a total order, even if the built-in operators <, >, <=, >= do not.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this