CODEWITHSUNDEEP
c++pointerscomparison
simeonz
simeonz

Reputation: 412

Is there a portable alternative to relational comparison of pointers in C++?

I lack industry experience with the language. But in my spare time I have encountered a couple of places where I need to compare pointers, preferably with behavior defined by the standard.

First case, if I decide to use ordered binary tree as a container in my application (and not hash table) and I want equality to be the object's identity (i.e. equal means the same instance) then I find no portable way to do this.

Second, if I want to test the containment relationship between the "complete objects" and their sub-objects, I again seem to have no portable approach. That is if I have two void* pointers "p" and "q", and I have the size of the object pointed to by "q", I see no way to test whether "p" is a non-static member variable of "q" or not. I fail to find encouragement in paragraph 5.9 ("Relational operators") from the standard. The latter scenario appears, for example, in the garbage collector from this boost forum post. I liked the general idea and started to explore it, but certain parts seem to use pointers and allocation semantics in ways which are not portable.

That is I want to know how to make the contains function from the following code portable:

#include <stddef.h>
#include <assert.h>

struct A {
    int x;
} a;

struct B {
    int y;
} b;

bool contains(const void *outer, size_t size, const void *inner)
{
    return (outer <= inner) &&
        (inner < static_cast<const char *>(outer) + size);
}

int main()
{
    assert(contains(&a, sizeof(a), &a.x));
    assert(contains(&b, sizeof(b), &b.y));
    assert(!contains(&a, sizeof(a), &b.y));
    assert(!contains(&b, sizeof(b), &a.x));
}

Thanks and best regards.

PS:
Ok, after consulting the standard again, I see that it states explicitly, as GMan informs in his answer, that the functors such as less and less_equal provide total ordering for pointers. I think it is also implied that the ordering will be consistent with the built-in comparison operators < and <=, but that point could be addressed more pedantically. The built-in operators are not predictable when the pointers do not point in the same array, or to sub-objects of the same object. I mean, what is the test for distinctiveness in this total order - the binary representation of the pointer? For example, when not comparable in well-defined manner with the built-in operators, what does it mean to be non-identical in the total order on void* pointers?

For member variables with the same access control, the standard defines their order in memory, i.e. when observed through pointer comparison. It is the order of appearance in the object's type definition. From the perspective of the built-in comparison operators, the first member variable has the smallest address and the last member variable has the biggest address. Also, in the section on types, it is stated that objects of a "trivially copyable type" will be laid out in memory in the range between the value of the & operator and the following sizeof characters. Now lets assume that the functors provide total order in the sense of pointers to distinct objects being distinct. Doesn't this mean that, even if inadvertently, the standard implies the behavior of the snippet above, if functors are used instead of the built-in operators in the contains function?

Just want to get the point clear - if the standard has omission, or simply needs clarification, or it leaves flexibility for the implementation of pointer comparison.

Upvotes: 1

Views: 249

Answers (1)

GManNickG
GManNickG

Reputation: 503973

I'm not quite sure what you're asking for (i.e., what exactly are you trying to accomplish?), but I think this is what you want to know:

The relational functors greater, greater_equal, less, and less_equal defined in <functional> yield total ordering for any pointer type, even if the built-in relational operators do not.

That is:

#include <functional>
#include <iostream>

int main()
{
    int i, *j = &i;    
    int k, *l = &k;

    std::cout << std::boolalpha << std::less<int*>()(j, l) << std::endl;
}

is well-defined. (Note the output is implementation-defined, but you are guaranteed total ordering.)

The associative containers predicate defaults to std::less, so it's okay to use pointers as keys.

Upvotes: 6

Related Questions