3

Does ETS set guarantee that internal order of tuples is the same as the order by which they were inserted? For instance: I keep a log by inserting a tuple every second, timestamp is the key. In this example, does set guarantee that tuples are sorted by the key?

I understand that ordered_set would do what I wish, but it has a insert overhead. So if set keeps the insert order, then using set would be much more efficient in my example. So, does it? :-)

Thanks in advance, Nikola

2 Answers 2

5

No, for table type set there are no guarantees at all of what order the keys are sorted. They are hashed and then the hash value is used to put the elements in a table. The table is occasionally resized and resorted as well so the order will change. So no, you were just lucky.

2
  • @dijxtra: Yes, set and bag are hashed while ordered_set is a sorted binary tree.
    – rvirding
    Nov 14, 2011 at 10:14
  • I wonder... If you need an ordered index compared by key, can you then do faster than O(lg n) worst case time? Of course you can amortize the inserts and pay with extractions (like a pairing heap does for instance) - but still... Nov 14, 2011 at 10:58
2

Even if the ETS set does fulfill your assumption today, there is no guarantee that it would continue to do so in the future -- especially when there is an ordered_set that has the exact property you need.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.