Is it safe to modify mutable members of objects inside sets?

Question

I was curious as to whether the following scenario is safe.

I have the following class definitions:

class ActiveStatusEffect
{
public:
    StatusEffect* effect;
    mutable int ReminaingTurns;
    ActiveStatusEffect() : ReminaingTurns(0)
    {
    }
    //Other unimportant stuff down here
}

I then store a group of these inside an std::set as follows:

struct ASECmp
{
    bool operator ()(const StatusEffects::ActiveStatusEffect &eff1, const StatusEffects::ActiveStatusEffect &eff2)
    {
        return eff1.effect->GetPriority() < eff2.effect->GetPriority();
    }
};
std::set<StatusEffects::ActiveStatusEffect, ASECmp> ActiveStatusEffects;

I mark RemainingTurns as mutable because I want to be able to change it without haing to constantly erase/insert into the set. I.e.

void BaseCharacter::Tick(Battles::BattleField &field, int ticks)
{
    for (auto effect = ActiveStatusEffects.begin(); effect != ActiveStatusEffects.end();)// ++index)
    {
           auto next = effect;
            ++next;
        if (effect->effect->HasFlag(StatusEffects::STATUS_FLAGS::TickEffect) && effect->ReminaingTurns > 0)
        {                       
            effect->effect->TickCharacter(*this, field, ticks);
            --effect->ReminaingTurns;

        }
        if (effect->ReminaingTurns == 0)
        {
            ActiveStatusEffects.erase(effect);
        }
        effect = next;
    }
}

I'm concerned because it seems possible for this to mess up the ordering within the set, meaning I can't guarantee the set will always be sorted by effect->GetPrority()

If that's true, is there a safe way (such as not have RemainingTurns form part of the key) to do this besides copying, modifying, erasing then inserting what I need to change?

EDIT:

@ildjarn - sorry, I didn't think that mattered. It just returns an int stored within StatusEffect. That int is guaranteed not to change over the runtime of the program.

int StatusEffect::GetPriority() const
{
    return StatusPriority;
}

Sounds like a case for [`std::priority_queue<>`](http://www.sgi.com/tech/stl/priority_queue.html) container instead; for more complex scenarios, see [Boost MultiIndex](http://www.boost.org/doc/libs/1_37_0/libs/multi_index/doc/index.html) — sehe, May 20 '11 at 06:28
@sehe: Can a priority handle changing keys without reinsertion? — Björn Pollex, May 20 '11 at 06:30
How can we possibly know whether `RemainingTurns`' mutability matters when we can't see the implementation of `StatusEffect::GetPriority()`? — ildjarn, May 20 '11 at 06:30
@Space_C0wb0y: std::priority_queue can't handle changing keys without reinsertion and *can't handle reinsertion either* because it does not allow you to access non-top element at all. Been there, had to reimplement it (implemented Dijkstra's algorithm, which needs one). Boost.Graph has a priority queue that can handle updates, but dug up deep in `details` and it requires that each object has ID suitable as array index, which was blocker for me anyway. — Jan Hudec, May 20 '11 at 06:46
If you have one key part and one data part, why not use a map? — Bo Persson, May 20 '11 at 06:52
Related: http://stackoverflow.com/questions/908949/what-happens-when-you-modify-an-element-of-an-stdset — Ciro Santilli OurBigBook.com, Jan 10 '17 at 21:44

score 7 · Accepted Answer · answered May 20 '11 at 06:42

7

Changing data that affects the ordering of an object will indeed break the invariants of associative containers, but because ActiveStatusEffect::ReminaingTurns is not involved in the ordering of ActiveStatusEffect objects whatsoever, keeping it mutable and modifying its value is perfectly harmless.

I'm concerned because it seems possible for this to mess up the ordering within the set, meaning I can't guarantee the set will always be sorted by effect->GetPrority()

It's a std::set<StatusEffects::ActiveStatusEffect, ASECmp>; how could it sort by any criteria other than that defined by ASECmp?

answered May 20 '11 at 06:42

ildjarn

62,044
9
127
211

I was concerned about it breaking the keys, and future insertions not being inserted correctly once that occurs – Megatron May 20 '11 at 07:04
@user127817 : But `ActiveStatusEffect::ReminaingTurns` isn't part of the key's identity as far as the standard ordered associative containers are concerned, because it's not taken into account inside of `ActiveStatusEffect`'s ordering. I.e., the only risk you run of breaking something in the future is by changing `ActiveStatusEffect`'s ordering logic to use `ReminaingTurns` somehow. – ildjarn May 20 '11 at 17:23

score 2 · Answer 2 · answered May 20 '11 at 06:24

If you change the key of something in a std::set you are off in Undefined Behaviour land - simple as that. Not only will it "mess up the ordering", but the set will probably stop working correctly altogether.

score 0 · Answer 3 · answered May 20 '11 at 07:55

If the key is unrelated to the actual object, or only a part of it, then you should consider using a map rather than a set:

std::map< int, ActiveStatusEffect > m;
ActiveStatusEffect x = create();
m[ x.effect->GetPriority ] = x;      // !!!

Other issues with your code is that you should use some encapsulation (user code should not get access to the internals of the class (i.e. members should not be public).

Is it safe to modify mutable members of objects inside sets?

3 Answers3

Linked