Hello all, although it's called 'unordered_set', it surprised me that an unordered container could have a different ordering although its contents are the same: void f() { boost::unordered_set<int> uset1; uset1.insert(10); uset1.insert(9); uset1.insert(8); boost::unordered_set<int> uset2; uset2.insert(8); uset2.insert(9); uset2.insert(10); //uset1: 8, 9, 10 //uset2: 10, 9, 8 bool b = uset1 == uset2; //ok, they are the same } Maybe it is somewhere in the documentation, otherwise maybe add a documentation note.
gast128
although it's called 'unordered_set', it surprised me that an unordered container could have a different ordering although its contents are the same:
void f() { boost::unordered_set<int> uset1; uset1.insert(10); uset1.insert(9); uset1.insert(8);
boost::unordered_set<int> uset2; uset2.insert(8); uset2.insert(9); uset2.insert(10);
Don't confuse "sequence of insertion" with "sequence of storage". "set" uses ordered storage, while "unordered_set" uses unordered storage.
// uset1: 8, 9, 10 // uset2: 10, 9, 8
The reality is that the storage for uset1 and uset2 probably look more like this: uset1: 10, 8, 9 uset2: 10, 8, 9 ("unordered" keys are really hashed -- so the result is still deterministic, just not ordered by "<" operator).
bool b = uset1 == uset2; //ok, they are the same
The concept of set equality involves the membership of the sets, not with how members are stored in that set. If you really want these two collections to be non-equal, then you need a container that preserves order. A std::vector would work in this case, although it would not give you the no-duplicates guarantee of the set classes. If you need to preserve sequence as well as no-dups, then you need to look at hybrid data structures (e.g., boost::multi_index), or modify your algorithm. (Note that some special cases can make "brute force" approaches workable. There is a famous example in the "Programming Pearls" book, where a memory-limited computer was still able to manage sets of 10M integers by using a bitset instead of a traditional node or slot approach.) Best regards, Anthony Foiani
On 14 June 2013 16:49, Anthony Foiani
// uset1: 8, 9, 10 // uset2: 10, 9, 8
The reality is that the storage for uset1 and uset2 probably look more like this:
uset1: 10, 8, 9 uset2: 10, 8, 9
It used to, but now Boost.Unordered stores elements in a single singly-linked list in order to get o(1) iteration. When inserting into an empty bucket the element is inserted at the beginning of the list. But please don't rely on that.
participants (3)
-
Anthony Foiani -
Daniel James -
gast128