I want to use a set S of type node and I want to manipulate the cost section in the set and order the set by cost:
struct node
{
int label;
long cost=LONG_MAX;
bool visited=false;
bool operator < (const node &other) const { return cost < other.cost; }
}
set<node> S;
//here i just want to update the cost of a node in my set S
set<node>::iterator it=S.find(vertex);
*it.cost=200;
Does that change the order in the set automatically?
Does that change the order in the set automatically?
Not only does it not change the order of the set, but the operation itself is illegal. Associative container iterators give you a const type for the key - so *it in your example has type node const.
If you think about it, that's the only way to ensure the invariant that the container provides. After all, how could it->cost = 200 possibly update the underlying set? Maybe if C++ had reflection and the iterators dereferenced to some proxy that had overloaded operator= that... yeah that just sounds like a mess.
The current idiomatic way to "update" an element in a set involves erasing it, modifying it, and then re-inserting it. In your case:
auto it = S.find(vertex);
node cur = std::move(*it);
auto next = S.erase(it);
cur.cost = 200;
S.insert(next, cur);
That's admittedly pretty tedious.
There is a proposal (P0083R2) to improve this in the future.
Update for C++17: that proposal has been accepted. Now you want to use extract():
auto node = S.extract(vertex);
node.value().cost = 200;
S.insert(std::move(node));
This will avoid an extra copy of your type and an extra allocation/deallocation.
You cannot normally change the existing contents of the set. It's a dirty little secret, but std::set iterators are really const_iterators. Go ahead and try to compile that, you'll get compilation errors.
Of course, there are ways around that, but they will result in undefined behavior.
