• Advertisement
Sign in to follow this  

std::set equivalent in C# ?

This topic is 4255 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Or just a simple sorted container, I don’t want an associative container. I see SortedList and SortedDictionary are both associative. And I don’t see any other sorted containers.

Share this post


Link to post
Share on other sites
Advertisement
If you want a container that's sorted but not associative, use a List<T> and .Sort() as needed. If you want a container that's sorted, not associative, and won't allow duplicates, you need a Set. One example is here, and the corresponding generic extensions (by a different author) are here.

hope that helps,

Share this post


Link to post
Share on other sites
Quote:
Original post by NotAYakk
Can't you just map your key to a null or empty type?


Given that SortedList sorts the keys, and not the values, I guess not.

Share this post


Link to post
Share on other sites
A map "maps" the key to a value.

If the key maps to a null or empty type, then the values are empty types, and the keys are non-null.

Share this post


Link to post
Share on other sites
This may be a silly suggestions but...

Couldn't you just use the object itself as both the key AND the value? That would also effectively give you a set.

Share this post


Link to post
Share on other sites
I'm still not sure that he really wants a set (in the mathematical sense), since sets aren't ordered. Taken in context, there is no such thing as "the fourth element of a set", for instance.

Share this post


Link to post
Share on other sites
True, but when speaking of containers, doesn't "set" generally just mean that no element may be present more than one time?

Share this post


Link to post
Share on other sites
Quote:
Original post by kSquared
If you want a container that's sorted but not associative, use a List<T> and .Sort() as needed. If you want a container that's sorted, not associative, and won't allow duplicates, you need a Set. One example is here, and the corresponding generic extensions (by a different author) are here.



hope that helps,

I’ll check out both of those, however how stable/reliable are they?
Quote:
Original post by smitty1276
This may be a silly suggestions but...

Couldn't you just use the object itself as both the key AND the value? That would also effectively give you a set.

Ok is this a good solution? Sounds like a waste of memory.


Quote:
Original post by kSquared
I'm still not sure that he really wants a set (in the mathematical sense), since sets aren't ordered. Taken in context, there is no such thing as "the fourth element of a set", for instance.
What I want specifically is a container that guarantees O(log n) and doesn’t allow duplicates, and that isn’t associative.

Why isn’t this in the .Net library?
I swear for all the raving I hear about how wonderful and easy to use C# and .Net are... They have given me nothing but headaches.

Share this post


Link to post
Share on other sites
O(log n) what? Sorting, searching, insertion, deletion? An array is O(1) lookup but O(n) inserting, for instance. You need to be more specific. You're right that a "set" in the mathematical sense does not exist in the .NET framework, though.

Share this post


Link to post
Share on other sites
Grain:
Let T be the type you want a set of.

Let Empty be a type with no data in it.

Make a map from T->Empty.

Such a map has at most one instance of any one T, has lg(n) insertion and lg(n) deletion and lg(n) searching and O(1) iteration.

Or is there some quirk of the C# language that makes this not work?

Share this post


Link to post
Share on other sites
Quote:
Original post by Grain
Quote:
Original post by smitty1276
Couldn't you just use the object itself as both the key AND the value? That would also effectively give you a set.

Ok is this a good solution? Sounds like a waste of memory.

Well, it wastes at most 20% memory, in most apps you can get by with that.

Share this post


Link to post
Share on other sites
I asked this question in the .NET forum here recently. I ended up using one of the associative containers, with a pointless bool as the value type. No one mentioned the generic set that already existed, so I may have to check that out. I do find it to be a somewhat glaring (and obvious) omission from the standard library.

Share this post


Link to post
Share on other sites
How do you get a reference to the object then? Don’t associative containers just return a reference to the value type?

Share this post


Link to post
Share on other sites
Ah, right. I wasn't as concerned about (log n) operations, so I actually used SortedList. And then I used .Keys whenever I needed to do anything...

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement