🔒 Locked

std::set does not insert unique elements (pointers)?

Started by VooDooTom Mar 26, 2009 at 2:15 PM 13 replies 3.1k views

Original Post

Mar 26, 2009 at 2:15 PM

Hi there, in an application of mine a set of pointers is used to have some objectes sorted and uniquely in a container. I have to use pointers since the type is an abstract class. So I defined my set as the following:



struct f_launchsite_sort
{
	bool operator()(const PLaunchSite ls1, const PLaunchSite ls2) const
	{
		// GetHeight() returns the height of the object and is comparable (like a float)
		return ls1->GetHeight() > ls2->GetHeight();
	}
};

typedef SnowSim::Model::ILaunchSite<PrecisionType>* PLaunchSite;
typedef std::set<PLaunchSite, f_launchsite_sort> LS_Set;

Now I use the set and want to insert values to it:


LS_Set* u1 = new LS_Set();
EdgeGroup::CDT_VIterator vit = eg->LaunchSites_Begin();
EdgeGroup::CDT_VIterator end = eg->LaunchSites_End();

/* go through all launch sites of this edge group */
/* and add them to the sorted list u1 */
while (vit != end) {
	PLaunchSite ls = &(*vit);
	pair<LS_Set::iterator, bool> result;
	result = u1->insert(ls);
	std::cout << ls << " -> returned iterator: " << *(result.first) << " inserted?: " << result.second << std::endl;
	++vit;
}

The iterator walks over a bunch of different objects - for testing purposes eight different sites - and all should be inserted. Strange is, that only two pointers get inserted and the others are not. Like you may have seen I added an ouput which prints the current pointer to insert, the returned iterator (to the new element if inserted, and to the old if alreay in set) and a value indicating if the insertion worked. Here is the output: 02BAF408 -> returned iterator: 02BAF408 inserted?: 1 02BAF440 -> returned iterator: 02BAF408 inserted?: 0 02BAF478 -> returned iterator: 02BAF408 inserted?: 0 02BAF4B0 -> returned iterator: 02BAF408 inserted?: 0 02BAF4E8 -> returned iterator: 02BAF4E8 inserted?: 1 02BAF520 -> returned iterator: 02BAF4E8 inserted?: 0 02BAF558 -> returned iterator: 02BAF558 inserted?: 1 02BAF590 -> returned iterator: 02BAF558 inserted?: 0 Can you tell me what is going on? Thanks in advane, Tom

NotAYakk

Mar 26, 2009 at 2:29 PM

For a std::set, if two things are equivalent, extras are discarded.

Equivalence is determined by your operator<.

Thus you have told std::set to keep exactly one element for each height. Extras are discarded.

And when searching, you have also told it that 'same height is a match'.

I'm guessing from your confusion you didn't mean to tell the container that. :)

Also note that if your objects change ordering (get taller) while in a set, the result is undefined and likely to be a crash or infinite loop the next time you try to poke around with your set.

alagtriste

Mar 26, 2009 at 2:43 PM

I guess that your edge group container have repeated pointers. You have 8 pointers but only 3 are unique.

Zahlman

257

Zahlman

Mar 26, 2009 at 7:34 PM

I'm confused about how you use the iterators in your code. 'PLaunchSite ls = &(*vit);' suggests that 'vit' iterates over a vector of launch sites, rather than pointers to them. Is it the case that you have a vector of one concrete derived class used for these elements, but you will eventually add instances of other derived classes to the same set? Or are you trying to store pointers as weak references to previously-existing objects, instead of copying them into the set?

In any case, there doesn't seem to be any reason to allocate the set itself dynamically. Also, sets provide an iterator-range constructor that may simplify things for you immensely (depending on your answers to the previous).

VooDooTom

Author

VooDooTom

Mar 26, 2009 at 9:04 PM

Quote:
Original post by NotAYakk
For a std::set, if two things are equivalent, extras are discarded.

Equivalence is determined by your operator<.

Thus you have told std::set to keep exactly one element for each height. Extras are discarded.

And when searching, you have also told it that 'same height is a match'.

I'm guessing from your confusion you didn't mean to tell the container that. :)

Also note that if your objects change ordering (get taller) while in a set, the result is undefined and likely to be a crash or infinite loop the next time you try to poke around with your set.

Thank you for the hints - I changed the compare method and use an reverse_iterator to get from "highest" to "lowest" site.

/// A compare method for sorting the launch sitesstruct f_launchsite_sort{	bool operator()(const PLaunchSite ls1, const PLaunchSite ls2) const	{		return ls1->GetHeight() < ls2->GetHeight();	}};

Quote:
Original post by alagtriste
I guess that your edge group container have repeated pointers. You have 8 pointers but only 3 are unique.

I guess you misinterpreted the output, the pointers on the left are the input pointers, followed by the pointer the iterator encapsulates and the last value (boolean) denotes if the insertion of the most left pointer had succeeded.

Quote:
Original post by Zahlman
I'm confused about how you use the iterators in your code. 'PLaunchSite ls = &(*vit);' suggests that 'vit' iterates over a vector of launch sites, rather than pointers to them.

I overloaded the * operator and everything works fine, I get the type I need :) But, thanks for the sharp eyes.

Anyway, even with the changes above (comparison method + reverse iterators) the results are the same :(

Regards and thanks,
Tom

Sneftel

296

Sneftel

Mar 26, 2009 at 9:08 PM

Quote:
Original post by VooDooTom
Thank you for the hints - I changed the compare method and use an reverse_iterator to get from "highest" to "lowest" site.

I don't think you're quite understanding.

The rules of equivalence are as follows: For two objects a and b, a and b are equivalent if and only if (a<b) == false and (b<a) == false. And, of course, a set doesn't allow you to add a second element that's equivalent to one already in the set; that's what makes it a unique container. So tell me: For two LaunchSites, both with height 3, are they equivalent or not?

What you'll need is a method of breaking ties. Take a look at how std::pair::operator< works.

VooDooTom

Author

VooDooTom

Mar 26, 2009 at 9:38 PM

NotAYakk,

thanks for the clarification. At least it gets clearer. To answer your question: Two different LaunchSites, both with same height (e. g. 3), are different. Both should be in the set and thus are not equivalent.

So, lets say I use a std::pair - how should I parameterize it? std::pair<PLaunchSite, float> (float for height)? I still can not a compare method for this idea and it would be great if you could sketch this up.

Thanks,
Tom

Edit: Ah I did not read that you mentioned "std::pair::operator<" and not only "std::pair" - I will look after this. Thanks.

NotAYakk

Mar 26, 2009 at 10:25 PM

Ie:

bool operator()(const PLaunchSite ls1, const PLaunchSite ls2) const	{		if(ls1->GetHeight() < ls2->GetHeight()) return true;		if(ls1->GetHeight() > ls2->GetHeight()) return false;		return ls1 < ls2;	}

Now left is equivalent to right if and only if their pointers are equal.

We first sort by the height, then (if there is a collision) we sort by binary address.

When you walk through the set, you'll get things in height value.

Another option would be using a std::multiset.

VooDooTom

Author

VooDooTom

Mar 27, 2009 at 4:13 AM

Great, now everything is clear, thank you. I tryed to come up with a similar solution but did not know that I can compare pointers by the operator<. I thought this is only possible if they are pointing into the same array or part of the same object?

Regards,
Tom

Ezbez

154

Ezbez

Mar 27, 2009 at 4:27 AM

NotAYakk:

I'm really not sure, but that code doesn't seem quite right to me. Wouldn't it have to take ls1 and ls2 as pointers in order to compare them that way? Surely the code you have would, after the first two comparisons, simply call the operator< of the PLaunchSite class? And since they're both passed in by value, won't they be copies of the class and so have different pointers regardless of whether or not they were the same original PLaunchSite?

VooDooTom

Author

VooDooTom

Mar 27, 2009 at 4:38 AM

Quote:
Original post by Ezbez
NotAYakk:

I'm really not sure, but that code doesn't seem quite right to me. Wouldn't it have to take ls1 and ls2 as pointers in order to compare them that way? Surely the code you have would, after the first two comparisons, simply call the operator< of the PLaunchSite class? And since they're both passed in by value, won't they be copies of the class and so have different pointers regardless of whether or not they were the same original PLaunchSite?

In my first posting I defined PLaunchSite:

typedef SnowSim::Model::ILaunchSite<PrecisionType>* PLaunchSite;

So everything is ok :) (besides that I wonder if one can compare pointers by "<" just as one wants).

Zahlman

257

Zahlman

Mar 27, 2009 at 7:43 AM

Quote:
Original post by VooDooTom
So everything is ok :) (besides that I wonder if one can compare pointers by "<" just as one wants).

Not if they point into different buffers.

Sneftel

296

Sneftel

Mar 27, 2009 at 8:21 AM

Quote:
Original post by VooDooTom
Great, now everything is clear, thank you. I tryed to come up with a similar solution but did not know that I can compare pointers by the operator<. I thought this is only possible if they are pointing into the same array or part of the same object?

Yeah, it's technically an undefined operation, and bad mojo. I don't know of an actually existent processor/architecture/OS that actually chokes on it, though, so I wouldn't worry about it if I were you. Certainly plenty of other code relies on it.

ToohrVyk

238

ToohrVyk

Mar 27, 2009 at 8:34 AM

The standard guarantees that you can reinterpret_cast a pointer into an integer without loss of data (if the integer is of appropriate size). So, you can implement your comparison in terms of reinterpet_cast and let the compiler optimize it away.

NotAYakk

Mar 27, 2009 at 10:05 AM

Quote:
Original post by Zahlman
Quote:
Original post by VooDooTom
So everything is ok :) (besides that I wonder if one can compare pointers by "<" just as one wants).

Not if they point into different buffers.

True.

Use std::less, however, and the results are guaranteed to be meaningful (or so goes my google-fu).

Ie:

bool operator()(const PLaunchSite ls1, const PLaunchSite ls2) const	{		if(ls1->GetHeight() < ls2->GetHeight()) return true;		if(ls1->GetHeight() > ls2->GetHeight()) return false;		return std::less<void*>()(ls1, ls2);	}

However, this is mainly a concern on reasonably pathological (read: segmented memory or similar cases) hardware platforms -- this may exist in some embedded spaces and the like.

The hatred of segmented memory models means that even with stuff like NUMA, they are likely to implement it with a flat address space. So operator< directly on pointers isn't that dangerous.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.