4 ms·

Set is just sort of weird in other languages, I've never looked at set in the STL. I'm sort of surprised at the implementation in STL. Almost every other langu

Set is just sort of weird in other languages, I've never looked at set in the STL. I'm sort of surprised at the implementation in STL. Almost every other language's library tends to implement sets as a special case of a hash map without values, just keys. This leads a lot of people down a weird alley where they think they're getting a list that prevents duplicates and then have all sorts of weird behavior when they iterate over it. However, 90% of the time they don't care about order and the set is nowhere near large enough to really show the overhead you're incurring over a normal linked list or array list. Still, it's funny when they finally run into either of those issues and someone has to explain that the entire point of a set is really a data structure optimized around answering the question, "Do you contain x?" and not "Prevent duplicate entries." I've actually used sets before, but for the purpose of having a sort of "memory" about nodes the code has seen before while looking for cycles in a graph. Even then, that was hardly production code and more a slow running data clean up operation.

ksherlock 10y ago
As of c++11, there's also unordered_set (and unordered_map) which is a hash map.
Roboprog 10y ago
Uh, OK: "Is x a duplicate?" -> "Do you contain x?"
- deleted 10y ago
  [deleted]
- deleted 10y ago
  [deleted]
- krinchan 10y ago
  Not exactly. Typically, iterating over a set is generally not what's intended when someone designs a set structure. This in turn becomes a problem in some languages. 95% of the time it simply doesn't matter. I mean, people iterate over maps all the time in day-to-day stuff, which is also a lookup-oriented structure. But the other 5% of the time people expect list like behavior or performance from a set and don't get it, they act like this is a totally new thing for them even though they've been programming for years. :-/ EDIT: To clarify, it's really hard to explain to some folks that sets are optimized to answer quickly if they contain an X and Lists are optimized to quickly let you do a thing across all elements. Sets just happen to give you values back most of the time, but the real question they're trying to answer is if you have previously placed a known value into the set. Returning the actual contents of the Set is not actually a requirement at the more abstract, theoretical level though most standard libraries provide that. In some libraries, actually getting at the contents and iterating over a set is quite hard. I've seen highly optimized sets for massive data that doesn't actually store the item, but a highly optimized, almost range encoded version (hashes 0xabcd through 0xafaa are in the set) of the data. Like I said, the distinction between a list that disallows duplicate entries and a set really doesn't show up until you get into some pretty large scale things that most programmers don't ever use. However, I feel understanding the distinction and how trying to answer one question (Do you contain X?) can lead to design decisions that make answering another question (What are all the unique values out of the values I just added to you?) more difficult leads to better programmers. That is, if they have the skills to abstract the thought exercise and apply it to other situations.
  - Roboprog 10y ago
    Thanks for the follow up. I don't expect a particular order if I spin through the contents of a set, but it hadn't occurred to me how expensive it might be simply to get the sequence. This makes a good example of when "polymorphism" or "strategy patterns" are useful to swap in and out how you do some related things to fit what actually ended up happening in an app.
matthewaveryusa 10y ago
>Almost every other language's library tends to implement sets as a special case of a hash map without values, just keys. C++ is even weirder. It implements std::map as a std::set that has std::pair, keyed on the first element in the tuple. both std::set and std::map use a tree structure (RBtree) C++11 has unordered set/map which uses hashing.

ksherlock 10y ago

As of c++11, there's also unordered_set (and unordered_map) which is a hash map.

Roboprog 10y ago

Uh, OK: "Is x a duplicate?" -> "Do you contain x?"

deleted 10y ago
[deleted]
deleted 10y ago
[deleted]
krinchan 10y ago
Not exactly. Typically, iterating over a set is generally not what's intended when someone designs a set structure. This in turn becomes a problem in some languages. 95% of the time it simply doesn't matter. I mean, people iterate over maps all the time in day-to-day stuff, which is also a lookup-oriented structure. But the other 5% of the time people expect list like behavior or performance from a set and don't get it, they act like this is a totally new thing for them even though they've been programming for years. :-/ EDIT: To clarify, it's really hard to explain to some folks that sets are optimized to answer quickly if they contain an X and Lists are optimized to quickly let you do a thing across all elements. Sets just happen to give you values back most of the time, but the real question they're trying to answer is if you have previously placed a known value into the set. Returning the actual contents of the Set is not actually a requirement at the more abstract, theoretical level though most standard libraries provide that. In some libraries, actually getting at the contents and iterating over a set is quite hard. I've seen highly optimized sets for massive data that doesn't actually store the item, but a highly optimized, almost range encoded version (hashes 0xabcd through 0xafaa are in the set) of the data. Like I said, the distinction between a list that disallows duplicate entries and a set really doesn't show up until you get into some pretty large scale things that most programmers don't ever use. However, I feel understanding the distinction and how trying to answer one question (Do you contain X?) can lead to design decisions that make answering another question (What are all the unique values out of the values I just added to you?) more difficult leads to better programmers. That is, if they have the skills to abstract the thought exercise and apply it to other situations.
- Roboprog 10y ago
  Thanks for the follow up. I don't expect a particular order if I spin through the contents of a set, but it hadn't occurred to me how expensive it might be simply to get the sequence. This makes a good example of when "polymorphism" or "strategy patterns" are useful to swap in and out how you do some related things to fit what actually ended up happening in an app.

matthewaveryusa 10y ago

>Almost every other language's library tends to implement sets as a special case of a hash map without values, just keys. C++ is even weirder. It implements std::map as a std::set that has std::pair, keyed on the first element in the tuple. both std::set and std::map use a tree structure (RBtree) C++11 has unordered set/map which uses hashing.