Re: [Boost-users] [unordered] order in container

Subject: Re: [Boost-users] [unordered] order in container
From: Anthony Foiani (tkil_at_[hidden])
Date: 2013-06-14 11:49:29

gast128 <gast128_at_[hidden]> writes:

> 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