Universal less<> for pointers in C++ standard

Question

Many times I needed a set of pointers. Every time that happens, I end up writing a less<> implementation for a pointer type - cast two pointers to size_t and compare the results.

My question is - is that available in the standard? I could not find anything like that. Seems like common enough case...

Update: it seems that the upcoming standard fixes all of the problems with less<> provided for pointer types and unordered_set included, too. In a few years this question will be moot.

In the mean time, the current standard has no "legal" solution to this, but size_t cast works.

Update for update: well, I'll be gobsmacked! Not only

std::map<void *, int, std::less<void*> > myMap;

works, but even

std::map<void *, int > myMap;

as well.

And that's in gcc 3.4.1 . I've been doing all the these casts for nothing, and litb is perfectly right. Even the section number he cites is exactly the same in the current standard. Hurray!

Answer 1

Two pointers can be compared with using the comparison function objects less, greater etc. Otherwise, using blanket operator< etc, this is only possible if the pointers point to elements of the same array object or one past the end. Otherwise, results are unspecified.

20.3.3/8 in C++03

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.

No need to explicitly specialize and manually casting to size_t: That would lower the portability even, since the mapping of reinterpret_cast from pointers to integers is implementation defined and is not required to yield any order.

---

Edit: For a more detailed answer, see this one.

Answer 2

No, it's not available. The standard says that pointers are only comparable with the built-in operators when they point to the same array or other memory block. That is, the block needs to have been allocated all at once, as opposed to two separate allocations that might happen to be adjacent to each other.

This is OK:

int x[2];
bool b = &x[0] < &x[1];

This is undefined:

int x0;
int x1;
bool b = &x0 < &x1;

This is OK:

struct foo {
  int x0;
  int x1;
};
foo f;
bool b = &f.x0 < &f.x1;

Both values are members of the same struct, so they belong to the same block of memory (namely, f's).

Practically speaking, though, there's nothing wrong with your custom-defined comparison.

However, your custom specialization is unnecessary, since the std::less template is defined for pointers, evidently. So this is OK:

int x0;
int x1;
std::less<int*> compare;
bool b = compare(&x0, &x1);

There's still no indication of what the result must be, but you're at least promised to have some result, as opposed to undefined behavior. You get a total order, but you don't know what order until you run it.

Answer 3

Comparing pointers is a pretty fraught business. It only makes sense to compare pointers if they both point into the same block of memory, otherwise the operation is undefined. A (valid) set of pointers is therefore a pretty specialised thing, and no, the Standard Library doesn't have one.

Answer 4

Even though you may think that comparing the bits of pointers is harmless (after all, they're just addresses in memory, right?), there are good reasons why the language standard doesn't encourage it. For one, if you have code whose results depend on the relative ordering of pointers (e.g, the order of results depends on iteration order through a set or map of pointers), the results will be unstable: Changing the version of compiler or operating system release can change the results. Reproducibility is valuable enough to make this instability worth avoiding.

Answer 5

Comparing pointers that are not allocated in the same block is undefined, probably because there are memory models that have problems with them (and used to be more common).

What you need to use is unordered_set<>, which doesn't appear to require a comparison operator. It's in the next C++ standard, and available as a Boost header in the meantime.

Answer 6

Isn't hash_set what you need? It will be a part of the next standard