CODEWITHSUNDEEP
c++stlset
Roman
Roman

Reputation: 1019

Is it possible to erase modified element from std::set?

I need a sorted collection where elements can be modified. Is it safe to erase element after modification? Sorting key can be modified.

auto it=s.find(e)
modify(e)
s.erase(it)

I have made some tests in VS2010, and it worked. I think erase(it) does not need to search for element, so there is no need to call compare on element being erased.

It is hard to modify whole program to remove elements before modification, that is why I am looking for an alternative solution.

EDIT: adding working sample to make it more clear

#include <iostream>
#include <algorithm>
#include <set>

template <typename T>
struct PtrCmp
{
    bool operator()(const T* x, const T* y) const
    {
        return *x<*y;
    }
};

int main()
{
    std::set<int*, PtrCmp<int>> aset;
    int t[]={1,2,3,4};
    for(int i=0;i<4;++i)
    aset.insert(&t[i]);

    auto it=aset.find(&t[2]);
    t[2]=5;
    aset.erase(it);

    for(auto it=aset.begin(); it!=aset.end(); ++it)
        std::cout<<**it<<std::endl;
}

Upvotes: 0

Views: 686

Answers (8)

Serge Rogatch
Serge Rogatch

Reputation: 15020

In your example t[2]=5; modifies the value which is used in comparator which is used e.g. for rebalancing the tree data structure behind the set container. Therefore such modification is not safe because the balanced-tree algorithm may fail in case the factual key at a node is changed, therefore does not match the expectation for that tree node. erase operation is likely to trigger tree rebalancing, and that is how you get undefined behavior. So by modification of a value used in comparator you factually break the balancedness of the tree behind a set container.

Upvotes: 1

Jarod42
Jarod42

Reputation: 217135

In your sample, you modify the ordering of the set and so have undefined behaviour (and 'working as wanted' is one possible behaviour :-/).

You may use the following to have correct code:

auto it = aset.find(&t[2]);
assert(it != aset.end()); // or any other error check methods
aset.erase(it);
t[2] = 5; // No longer used by set

or

auto it = aset.find(&t[2]);
assert(it != aset.end()); // or any other error check methods
auto* ref = *it;
aset.erase(it);
assert(ref != nullptr); // or any other error check methods
*ref = 5; // No longer used by set.

Upvotes: 0

Fox
Fox

Reputation: 2138

Verbalise it:

                  // I have this key 'e'...
auto it=s.find(e) // I look through my set for another like 'e'
                  // and 'it' now points to it
modify(e)         // now I 'invert' e.
s.erase(it)       // and I remove object pointed to by 'it'

*it and e are two different objects.

In general, the object pointed to by an STL set/map iterator and an object used as a search key are different objects. So, you would still be working on a copy of the container's object.

Now your other questions boil down to two:

  • Can I modify the object pointed to by itr? Would it affect sorting order?

    • Theoretically possible. The contents of a set are const and the iterator doesnt allow direct assignment - 

      test.cpp10:9: error: read-only variable is not assignable.
*it = 4;
~~~ ^

      - but using mutable or a combination of const_cast and pointer-magic, it is possible to modify const-data. Is it dangerous? You betcha. Each container has its own set of assumptions that its API leaves invariant. So, a general rule - NEVER - do stuff to an STL container that its API doesn't allow.

  • Can I get a sorted container whose elements can be modified?

    • Of course! You just do it outside the container and put it back.

      auto it=s.find(e);
// possible optimisation (see below)
s.erase(it);
modify(e);
auto position = s.insert(e);
if (position.first) // no existing values matching e's comparison!
     assert(*position.second.key == e.key);

      With C++11, depending on what 'e' is, you can use move-semantics to move non-comparison elements from *it to e, in tandem with set emplace to optimise the number of copies done.

Upvotes: 0

M.M
M.M

Reputation: 141554

Your code is correct. The set contains four pointers. It does not contain the things being pointed to by those pointers.

t[2] = 5; does not modify the set in any way.

Upvotes: 0

Melebius
Melebius

Reputation: 6695

It is safe unless your modify() does any operation that invalidates the iterator. If it cannot access the svariable, there is no problem.

Upvotes: 0

Sebastian Redl
Sebastian Redl

Reputation: 71899

The element in the set doesn't (or shouldn't) have anything to do with e. If you modify e and it doesn't affect the set element, you're fine.

If the modification does affect the set element in a way that modifies its sort order, you've technically got undefined behavior at this very moment, and the erase afterwards is no longer required to work.

See C++11 23.2.4 paragraphs 4 and 5.

Upvotes: 0

Dietmar K&#252;hl
Dietmar K&#252;hl

Reputation: 153810

Element in a std::set<T> are considered const. If you change an element, e.g., by having a mutable member or a pointer to some internal data and chnage the key, the invariants for std::set<T> are violated and you'll get undefined behavior when accessing the std::set<T> in any way.

Upvotes: 0

Aaron McDaid
Aaron McDaid

Reputation: 27133

modify(e) (maybe) doesn't modify the set. My guess is that e is something outside the set, and that s.find(e) searches within the set for (a copy of) e. Basically, your code is equivalent to:

auto it=s.find(e)
s.erase(it)
modify(e)

And so there won't be any problem.

Unless e is actually a raw pointer to data.

Upvotes: 0

Related Questions