Can't sort unordered_set

1
votes

I have an unordered_set of a class ActiveStatusEffect The set is declared as follows:

boost::unordered_set<StatusEffects::ActiveStatusEffect> ActiveStatusEffects;

ActiveStatusEffect is defined as follows:

class ActiveStatusEffect
    {
    public:
        StatusEffect* effect;
        int ReminaingTurns;
        bool operator<(const ActiveStatusEffect& ase) const
        {
            return *effect < *ase.effect;
        }
        bool operator>(const ActiveStatusEffect& ase) const
        {
            return *effect > *ase.effect;
        }
        bool operator==(const ActiveStatusEffect& ase) const
        {
            return *effect == *ase.effect;
        }
        bool operator!=(const ActiveStatusEffect& ase) const
        {
            return !((*this) == ase);
        }
    };

The comparison between StatusEffect's is a comparison between a unique integer assinged to each instance of a status effect.

However, if I try to sort the effects like follows:

std::sort(statusSet.begin(), statusSet.end(), [](StatusEffects::ActiveStatusEffect const &se1, StatusEffects::ActiveStatusEffect const &se2){return se1.effect->GetPriority() < se2.effect->GetPriority();});

I get many errors in the algorithm header file such as

Error 198 error C2784: '_Base1::difference_type std::operator -(const std::_Revranit<_RanIt,_Base> &,const std::_Revranit<_RanIt2,_Base2> &)' : could not deduce template argument for 'const std::_Revranit<_RanIt,_Base> &' from 'boost::unordered_detail::hash_const_iterator' c:\program files (x86)\microsoft visual studio 10.0\vc\include\algorithm 3806

Error 199 error C2784: '_Base1::difference_type std::operator -(const std::_Revranit<_RanIt,_Base> &,const std::_Revranit<_RanIt2,_Base2> &)' : could not deduce template argument for 'const std::_Revranit<_RanIt,_Base> &' from 'boost::unordered_detail::hash_const_iterator' c:\program files (x86)\microsoft visual studio 10.0\vc\include\algorithm 3806

Why am I not able to sort the set? I'm quite certain this is something about unordered_set as removing attempts to sort or changing it to a vector does not generate errors.

2
c++sorting
If the set is unordered how would you sort (e.g. order) it? – Jordan
Somehow this really made me laugh... must be the time it's 2 am and im on SO... – RedX

2 Answers

7
votes

unordered_set doesn't have non-const iterators, because if you could mutate the item pointed to by an iterator you could violate the invariants of the set (uniqueness among others). Additionally if you sorted an unordered_set you would no longer be able to look up the item in the container anymore (assuming it works by hash).

If you really want to sort the set of items, you'll need to copy it into a vector first and then sort that. But in that case have you considered if unordered_set is the right container for you in the first place? What about using a normal set which is ordered at the expense of lookups being slower.

5
votes
boost::unordered_set<Foo> a;
a.insert(...);
...

std::set<Foo> b(a.begin(), a.end());

std::set<Foo> c;
std::copy(a.begin(), a.end(), std::inserter(c, c.end());

Voilà, a sorted set.