35

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!

  • "In the mean time, the current standard has no "legal" solution to this, but size_t cast works." The `less` solution **is** the one of the current standard. It's not C++0x specific – Johannes Schaub - litb Sep 14 '09 at 15:40

6 Answers6

34

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.

Community
  • 1
  • 1
Johannes Schaub - litb
  • 496,577
  • 130
  • 894
  • 1,212
  • I don't think that is intended to imply that one can use less, greater etc. on arbitrary pointers. –  Jul 08 '09 at 16:18
  • @Neil: If not then why explicitly specify that they are different to the builtin operators? – Richard Corden Jul 08 '09 at 16:21
  • @:Richard Because the C++ and C standards say that you cannot compare arbitrary pointers. There is no way that templates can get round basic language semantics. –  Jul 08 '09 at 16:24
  • I interpret it as being there for cases exactly like this one, i.e. ordering is only needed to make set work using pointers as keys such that the ordering is not actually important (happy to just let the implementation pick one). – Daniel Earwicker Jul 08 '09 at 16:25
  • 2
    Why do you think so? It says "the specializations for any pointer type yield a total order". Without restrictions in any way on the values, even explicitly mentioning that it doesn't depend on `operator<` etc. boost's shared_ptr implementation also uses `std::less` for comparison. – Johannes Schaub - litb Jul 08 '09 at 16:28
  • @Earwicker I don't think that the standards specify that the (apparent) bit patterns inside a pointer have to be unique for arbitrary pointers. Could be wrong on this, however. –  Jul 08 '09 at 16:28
  • @litb How are you going to implement less for arbitrary pointers without comparing them in some way? –  Jul 08 '09 at 16:29
  • 2
    @Neil: You and I cannot compare arbitrary pointers, but the all mighty compiler/library implementation *can*. They provide a specialization of 'std::less' which uses some internal magic to do that comparison and it will return a valid result. – Richard Corden Jul 08 '09 at 16:30
  • @Richard The reason that the standard is so vague in this area is because it may not be possible to compare pointers on a given architecture. The compiler is, after all, just another program. If the platform does not support comparable pointers, then the compiler cannot support them either. –  Jul 08 '09 at 16:34
  • 2
    @Neil nothing says that the standard library is in any way bound to the rules of the Standard in any way. The description of the standard, e.g that `std::less` returns `a < b` is just an *as-if* rule. So if you put a user defined type to `std::less`, then it behaves as-if `operator<` is called on it (and of course, `operator<` will be called to satisfy the rule). But if you provide a pointer, then the additional guarantee matters, and the comparison is well-formed. – Johannes Schaub - litb Jul 08 '09 at 16:34
  • @Neil - indeed, and also 0 (interpreted as a pointer) doesn't have to be "all bits set to zero", and I think there are some other examples where the standard tries to be abstract about these things. But then it has little things else where (like std::less) which cock it up and make it almost totally impossible to avoid using the "obvious" low-level representation. Similar to how std::vector was originally imagined to be abstract enough to allow the bool specialisation, but then &v[0] has to be available and that completely breaks it in practical terms. – Daniel Earwicker Jul 08 '09 at 16:34
  • @Neil: "The reason that the standard is so vague in this area ...". You've read the quoted text in litb's answer, right? ;) There are areas in the standard which are "vague", I've been to committee meetings and they sometimes refer to parts of the standard that do "hand waving". However, this is almost certainly not "hand waving" and there is no mention of "implementation defined" or "conditionally supported". The only remaining cases are those of broken or non standard compiler/library implementations. – Richard Corden Jul 08 '09 at 16:41
  • @litb I still do not see that the standard para you quoted allows you to compare arbitrary pointers. I believe if that was intended it would have been spelled out specifically, as this would be a major break with C practice. But I certainly seem to be in a minority :-) –  Jul 08 '09 at 16:47
  • 4
    Neil, it seems to me that the standard *does* spell it out specifically when it says "the specializations for any pointer type yield a total order." You can't have a total order if you still have undefined behavior, so that statement must remove the undefinedness from the templates. – Rob Kennedy Jul 08 '09 at 17:00
  • @Rob You can have a total order if the pointers are into the same block. I believe this is what the standard is saying, and that it assumed that everyone knew that comparing arbitrary pointers was UB. The standard is full of instances of this kind of phrasing. –  Jul 08 '09 at 17:05
  • 4
    In case anyone's counting, I'm another vote for "Neil has misread the spec". Total order means total order over the whole type. A "total order" which only includes certain values is technically referred to as a "partial order". I speculate that the reason for the difference from C is precisely that std::set cannot be implemented if int* aren't comparable. Hence the standard provides for int* to be comparable. What I don't understand is why the standard doesn't just say that operator< for pointers does the same as std::les.. – Steve Jessop Jul 08 '09 at 17:10
  • 2
    It doesn't say anything about being in the same block. If that restriction were still there, then the entire statement wouldn't be worth including in the standard since it wouldn't be saying anything different from what had already been defined for the built-in operators. Instead, the standard explicitly says that the templates are *different* from the built-in operators. – Rob Kennedy Jul 08 '09 at 17:12
  • @onebyone You can implement set under my interpretation if all the pointers the set contains are into the same block. And I believev that is what the standard intended. I really don't see any way of resolving this, however. –  Jul 08 '09 at 17:14
  • @rob when interpreting the standard, taking the most restrictive view is usually the best policy. –  Jul 08 '09 at 17:17
  • 4
    BTW, can I suggest that a few more people vote the original question up? This has turned out to be quite a good question! –  Jul 08 '09 at 17:19
  • "I really don't see any way of resolving this, however." - I wonder if it's too late to request a clarification in C++0x. If nothing else, I think you and litb have demonstrated that the language in the spec is inadequate. – Steve Jessop Jul 08 '09 at 17:24
  • @onebyone Well, let's wait for a few more responses from litb before we bother the standards org. He usually convinces me in the end :-) –  Jul 08 '09 at 17:29
  • 4
    @Neil Have a look into the latest draft at `19.5.1.3/3`, which defines `operator<` for `error_category` in terms of `std::less()(this, &rhs)` with a note *"less provides a total ordering for pointers"*. – Johannes Schaub - litb Jul 08 '09 at 17:39
  • @litb The standard's language may be unadorned, but it is ambiguous in many areas. Let me return to my main point: An architecture may not support comparable arbitrary pointers - the C model does not. Therefore, it may not be possible to support less for pointers on such architectures. Therefore, sensible people writing a standard (let's call it the C++ standard) would not write clauses describing such behaviour into the standard that could not be implemented. QED. –  Jul 08 '09 at 17:43
  • @Neil, i dunno why they did add it :( I imagine this would be a good question to comp.std.c++ or comp.lang.c++.moderated, though. – Johannes Schaub - litb Jul 08 '09 at 17:57
  • @all I've posted this to comp.lang.c++.moderated, and will summarise any replies. comp.std.c++ is to scary for me. –  Jul 08 '09 at 18:27
  • "sensible people would not write clauses" - and sensible people wouldn't have dropped copy_if on the cutting room floor and lost it under a bench. But that's what happened, and surely you wouldn't argue that copy_if actually is in the standard, because that's what the committee *meant* to say ;-) – Steve Jessop Jul 08 '09 at 22:24
  • 2
    @onebyone: "why the standard doesn't just say that operator< for pointers does the same as std::less". Performance and the principle that you don't pay for what you don't neeed. Consider where your pointers do point to the same array object, then you want to be able to take advantage of the "fast" comparison. And you use std::less when you don't have that guarantee. – Richard Corden Jul 09 '09 at 09:18
  • 5
    @Neil: "An architecture may not support comparable pointers". I don't see how this is important. The standard doesn't dictate that std::less has to be fast! It merely requires that it provide an ordering. If the architecture doesn't support it then the compiler/library is required to provide some sort of alternative mechanism to get the ordering. For example a lookup table that maps the address to an order value. Just because the architecture doesn't support it doesn't mean that it cannot be done. – Richard Corden Jul 09 '09 at 09:25
  • 2
    @all Question is on clc++m as http://groups.google.com/group/comp.lang.c++.moderated/browse_thread/thread/28c38b920600bf6f/af5c98f53ed635e7#af5c98f53ed635e7 - answers so far all of the litb persuasion :-( –  Jul 09 '09 at 16:15
4

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.

Rob Kennedy
  • 161,384
  • 21
  • 275
  • 467
  • This is incorrect, it is possible to get relative ordering of pointers. std::less (as per litb's answer) is guaranteed to return correct ordering. – Richard Corden Jul 08 '09 at 16:19
  • @Richard Corden - it may return *an* ordering but there's nothing "correct" about it, because there is no meaningful ordering for pointers that are not to locations within a single block or array. – Daniel Earwicker Jul 08 '09 at 16:21
  • 1
    @Earwicker: I'm not sure what you're implying here. What does it mean to say two pointers are less than each other anyway! The point is that std::less is defined by the C++ committee to provide a consistent ordering for pointer types. If you require Comparision object for a map/set for which you want to store unique pointers, then std::less is your man. Regarding "correct", I was referring to the comment: "The standard says that pointers are only comparable when they point to the same array or other memory block". This is not true, std::less compares all pointers. – Richard Corden Jul 08 '09 at 16:27
  • I'm just quibbling really - I took your "correct" to imply an ordering that could be considered meaningful or useful by some general or portable criteria, when (as you say in your next comment) the ordering is chosen by the implementation. Good enough to store unique pointers, no good if you expect them to iterate in the same order on different systems. – Daniel Earwicker Jul 08 '09 at 16:31
  • What would it even mean for them to iterate in the same order on different systems? You can't copy pointer values from one system to another anyway, unless you serialise via some integer type. What std::less doesn't say, is that it's consistent with comparison by casting to uintptr_t and comparing (and not just because uintptr_t isn't in C++, it doesn't say anything about consistency with any integer order). – Steve Jessop Jul 08 '09 at 17:15
  • I think only my first sentence was incorrect. The rest was merely incomplete. My edits address that shortcoming, I hope. – Rob Kennedy Jul 08 '09 at 17:26
  • @onebyone - the most common expectation I've encountered in beginners is that the order of some pointers stored in a set (or used as keys in a map) will depend in some way on the contents of the objects pointed to. – Daniel Earwicker Jul 08 '09 at 20:11
  • Your edit has resolved my concerns with this answer - vote returned! – Richard Corden Jul 09 '09 at 09:11
  • 1
    @Earwicker: tell 'em that when they sort envelopes at the post office, they do it by the address of the house, not by the surname of the person who lives there ;-) – Steve Jessop Jul 09 '09 at 13:03
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.

  • litb is correct (yet again here). 'std::less' et al. do guarantee to give a defined ordering. Again to directly address the comment you made on litb's answer, why else would the committee explicitly differentitate these functions from the builtin operators if they did not provide something extra? – Richard Corden Jul 08 '09 at 16:22
  • @Martin Because C++ and C do not specify what the bit patternn inside a pointer mean. –  Jul 08 '09 at 16:26
  • The standard attempts to leave it open so that pointers are more abstractly defined than that. Whether it succeeds is another matter, but in theory if two pointers are compared and they are not from the same block, an implementation is allowed to format your hard drive, etc. (insert favourite "undefined behaviour" cliche here). – Daniel Earwicker Jul 08 '09 at 16:27
  • Bah, that was @Martin but he's disappeared. – Daniel Earwicker Jul 08 '09 at 16:28
3

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.

Nathan Kitchen
  • 4,799
  • 1
  • 24
  • 19
2

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.

David Thornley
  • 56,304
  • 9
  • 91
  • 158
1

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

Dmitry Risenberg
  • 2,321
  • 2
  • 18
  • 22
  • 2
    The container isn't the issue. The issue is the comparison operator *used* with the container. There is no such operator defined for arbitrary pointers. – Rob Kennedy Jul 08 '09 at 16:03
  • First, it's unordered_set in the next standard and the Boost library. Second, the container is the issue. With a standard set, you need comparison operators, which are undefined for pointers. With unordered_set, you don't (as far as I can tell). – David Thornley Jul 08 '09 at 16:18
  • +1 - the container is the issue: set is an ordered container so it isn't suitable for pointers, which are not generally speaking ordered. – Daniel Earwicker Jul 08 '09 at 16:19
  • I see. The hash_set and unordered_set classes transform the pointers with a hash function, so the pointers aren't being compared with each other anymore. They're compared via their hashes, and they're compared for equality. – Rob Kennedy Jul 08 '09 at 17:32