Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to update an existing element of std::set?

Tags:

c++

set

stl

I have a std::set<Foo>, and I'd like to update some value of an existing element therein. Note that the value I'm updating does not change the order in the set:

#include <iostream> #include <set> #include <utility>  struct Foo {   Foo(int i, int j) : id(i), val(j) {}   int id;   int val;   bool operator<(const Foo& other) const {     return id < other.id;   } };  typedef std::set<Foo> Set;  void update(Set& s, Foo f) {   std::pair<Set::iterator, bool> p = s.insert(f);   bool alreadyThere = p.second;   if (alreadyThere)     p.first->val += f.val; // error: assignment of data-member                            // ‘Foo::val’ in read-only structure }  int main(int argc, char** argv){   Set s;   update(s, Foo(1, 10));   update(s, Foo(1, 5));   // Now there should be one Foo object with val==15 in the set.                                                                   return 0; } 

Is there any concise way to do this? Or do I have to check if the element is already there, and if so, remove it, add the value and re-insert?

like image 662
Frank Avatar asked Sep 07 '11 20:09

Frank


People also ask

How do I change an element in a set in C++?

There are probably a few duplicates of that question but you can't replace an item in a set. You have to remove the old item and add the new item. It's not too hard. c++ provide basic functionalities which can be used to form several others like replace --> remove old + add new .

Is set in C++ mutable?

The C++ Standard does not specify whether the iterator of a set container (type set<T>:: iterator) is a mutable or immutable iterator. As a result, popular compilers and their Standard libraries provide different implementations of the set iterator.

How do you remove an element from a set in C++?

set::erase() erase() function is used to remove elements from a container from the specified position or range.


2 Answers

Since val is not involved in comparison, it could be declared mutable

struct Foo {   Foo(int i, int j) : id(i), val(j) {}   int id;   mutable int val;   bool operator<(const Foo& other) const {     return id < other.id;   } }; 

This implies that the value of val may change in a logically-const Foo, which means that it shouldn't affect other comparison operators etc.

Or you could just remove and insert, that takes O(1) additional time (compared to accessing and modifying) if insertion uses the position just before just after the old one as the hint.

Something like:

bool alreadyThere = !p.second; // you forgot the ! if (alreadyThere) {     Set::iterator hint = p.first;     hint++;     s.erase(p.first);     s.insert(hint, f); } 
like image 102
Cubbi Avatar answered Oct 01 '22 04:10

Cubbi


Don't try to solve this problem by working around the const-ness of items in a set. Instead, why not use map, which already expresses the key-value relationship you are modeling and provides easy ways to update existing elements.

like image 22
Mark B Avatar answered Oct 01 '22 03:10

Mark B