0

I have a 

class Widget;
std::list<Widget*> listOfPointers;

where the listOfPointers may contain two or more pointers pointing to the same object. All pointers are pointing to objects which are created one by one on the heap and are not members of the same array.

How can I get rid of the duplicates?

I tried:

listOfPointers.sort();
listOfPointers.unique();

but this is undefined behavior since operator < is not defined for pointers in my problem.

I can compare each pointer to each other using the defined operator==, but this would lead to quadratic complexity.

Community
  • 1
  • 1
Martin Drozdik
  • 12,742
  • 22
  • 81
  • 146

2 Answers2

6

You can use the other overload of sort that uses a comparator/binary predicate, and supply std::less<Widget*> as predicate: std::less is blessed with the ability to be able to compare arbitrary pointers (so you can use them in set or as keys in map).

listOfPointers.sort(std::less<Widget*>());
listOfPointers.unique();

However, I would like to point out that std::list::sort is not particularly efficient due to the fact that a list does not offer random access.

Martin Drozdik
  • 12,742
  • 22
  • 81
  • 146
Matthieu M.
  • 287,565
  • 48
  • 449
  • 722
1

It's technically true that pointers to objects not within the same array cannot be compared with relational operators. In practice, the results will be well-defined and consistent on every compiler you're likely to encounter, and will be a strict weak ordering as required by std::sort.

Sneftel
  • 40,271
  • 12
  • 71
  • 104
  • 2
    Actually, Matthieu makes a good point -- even though < is not guaranteed ordered for arbitrary pointers, std::less is. – Sneftel Sep 29 '13 at 11:07
  • Actually, you bring an interesting point; I've heard that before I was born (!) there used to be computed with *near* and *far* pointers and I wonder what kind of onus it would put on an implementation to provide a version of `std::less` that could accommodate those. – Matthieu M. Sep 29 '13 at 14:23
  • I was thinking the same, until very mysterious bugs started to appear in my program. After eliminating all possibilities it turns out that the undefined comparison of pointers indeed is the problem. And I am not working with some cryptic platform but Linux and gcc on a fairly new desktop computer. My advice is to never under any circumstances underestimate undefined behavior. – Martin Drozdik Sep 30 '13 at 07:50
  • Matthieu: near/far pointers have different types, so you don't need to worry about comparing them with each other. Near pointers compare as usual. Far pointers are the trickiest: they need to be linearized (shift the segment four bits left, add the offset) before comparison. By the time C++ was standardized, though, people had moved away from segmented architectures. – Sneftel Sep 30 '13 at 11:09
  • Martin: With respect, I think you may have misdiagnosed that bug. Desktop computers have a linear memory model, and GCC's variant of C++ does not support compacting garbage collection; these are the only reasons I know of why pointer comparisons could ever be poorly behaved. Indeed, a quirk of the `sbrk()` system call actually requires arbitrary pointer comparison to work under UNIX variants. – Sneftel Sep 30 '13 at 11:18
  • (I should add, of course, that if the pointer value is uninitialized, all bets are truly off.) – Sneftel Sep 30 '13 at 11:37
  • @Ben I admit I could have made a mistake, I am a beginner programmer. But the bug went away somehow once I used std::less – Martin Drozdik Sep 30 '13 at 14:41