Using for_each to modify std containers (even though you shouldn't)

Question

I'm taking a self-study course for C++, learning how the Standard Library works, and I want to understand how this code that uses for_each works, particularly regarding mutating objects (as opposed to native data types). I realize that you shouldn't use for_each this way, but this is for the purpose of learning.

I had thought this code would mutate all the elements in the set, but it doesn't.

My question is: 1. Why doesn't this code mutate the set? 2. How can the code be altered so that it will modify the set? To clarify: is there a way to keep the for_each and have it manipulate the set, or is this not possible and some other method (such as transform) has to be used?

Code

#include <iostream>
#include <algorithm>
#include <set>
using namespace std;

class A {
    int a;
public:
    A(int a) : a(a) {}
    int getA() const { return a; }
    void setA(int a) { this->a = a; }
    bool operator<(const A & b) const { return a<b.a; }
};

struct myprinter { 
    void operator()(const A & a) { cout << a.getA() << ", "; }  
};

struct doubler {
    void operator()(A a) { a.setA(a.getA()*2); }
};

int main() {
    int mynumbers[] = {8, 9, 7, 6, 4, 1};
    set<A> s1(mynumbers, mynumbers+6);
    for_each(s1.begin(), s1.end(), doubler()); //<-- Line in question
    for_each(s1.begin(), s1.end(), myprinter());
    return 0;
}

//Expected output: 2, 8, 12, 14, 16, 18
//Actual output: 1, 4, 6, 7, 8, 9,

What I've tried so far

• At first I thought the problem was that doubler was taking the parameter by value and not by reference, so it wasn't saving the changes to the set. But when I change the signature to be void operator()(A & a), I get the error of:

  error: no match for call to '(doubler) (const A&)
  ' __f(*__first);
    ~~~^~~~~~~~~~
  error: binding 'const A' to reference of type 'A&' discards qualifiers
  

  I deducted that that line being pointed out is from the internal implementation of for_each. I cannot make the parameter a const ref, because I am trying to change the a value using the setA() method, so it cannot be const.

• If I change the set to be a vector instead, then when I changed the signature of doubler to take a reference, it successfully doubled the elements in the container. Why would it not work if the container is a set instead?

Edit: moooeeeep linked to another question that shows how to edit each element of a set. This is a practical solution to my problem, but my question is more theoretical - why can you not edit sets using for_each, where you can edit vectors and other stl containers?

Answer 1

Because a std::set manages the order of it's elements, it prohibits the user to change it's elements through it's iterators. Which means it's begin() and end() methods return a const_iterator. You're only allowed to read the element pointed to by that iterator, not modify it (it's const) which is what doubler() is trying to do.

A solution would be to just use std::vector and std::sort to order it yourself:

#include <iostream>
#include <algorithm>
#include <vector>

class A {
    int a;
public:
    A(int a) : a(a) {}
    int getA() const { return a; }
    void setA(int a) { this->a = a; }
    bool operator<(const A & b) const { return a<b.a; }
};

struct myprinter { 
    void operator()(const A & a) { cout << a.getA() << ", "; }  
};

struct doubler {
    void operator()(A& a) { a.setA(a.getA()*2); } // by reference!
};

int main() {
    int mynumbers[] = {8, 9, 7, 6, 4, 1};
    std::vector<A> s1(mynumbers, mynumbers+6);
    std::sort(s1.begin(), s1.end());
    std::for_each(s1.begin(), s1.end(), doubler());
    std::for_each(s1.begin(), s1.end(), myprinter());
    return 0;
}

Answer 2

The problem is that you are not allowed to modify elements in a std::set. If it were possible, then how would it handle something like this:

std::set<int> my_set { 1, 2, 3 };
int& foo = *(my_set.begin());
foo = 2;

Now there is two elements with value 2. That doesn't make sense in a set due to

std::set is an associative container that contains a sorted set of unique objects of type Key.

(emphasis mine)

http://en.cppreference.com/w/cpp/container/set

Answer 3

Because the contents of an object in an std::set determines its position. That's why std::set iterators are always const.

Of course, it is often the case that not all members of an object have an effect on its position. A possible workaround is then to declare those members mutable. Then you can modify them using const references.

To modify a member that does affect the object's position in a set, remove the object from the set, modify it, and add it back in.

Answer 4

You can't simply change the key of an element in a key-value store kind of a data structure. (In case of a set, it's only key, no value.)

If you would, the element's position in the underlying container might need to be adjusted, based on the recomputed hash value in case of an unordered hash table, or a different sorting position in a binary search tree / ordered list.

Therefore the API of the std::set requires you to erase and reinsert the item in this case.

Which the answers to existing questions in this direction already state:

• C++ STL set update is tedious: I can't change an element in place
• How to update an existing element of std::set?

Answer 5

Based on the comments, I've learned the following so far:

1. Why doesn't this code mutate the set?

Because the parameter passed into the doubler method is passed by value (the C++ default), instead of by reference. Therefore, the value of each a parameter is modified, but this is not saved to the element in the container.

2. How can the code be altered so that it will modify the set?

Not easy to do. Sets (as opposed to other containers such as vectors, deques, lists, and arrays) maintains order to its elements. (Suppose instead that the function used in the for_each method negated every element. Then the set would be ordered backwards, and the order the set tried to maintained would be lost). Thus, if you want to modify the elements of a set you have to do so one at a time (Thank you @NathanOliver and @moooeeeep for your comments)

Note: If the container was not a set (instead, a vector or deque), then the doubler method could be modified to the following to mutate the elements:

void operator()(A & a) { a.setA(a.getA()*2); }

Answer 6

This is a piece of cake with a lambda expression.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    int mynumbers[] = {8, 9, 7, 6, 4, 1};
    vector<int> s1(mynumbers, mynumbers+6);
    sort(s1.begin(), s1.end());
    for_each(s1.begin(), s1.end(), [](int &x) { x*=2; });
    for_each(s1.begin(), s1.end(), [](int x) { cout << x << ", "; });
    return 0;
}

OUTPUT:
2, 8, 12, 14, 16, 18,

Answer 7

The doc for std::set (http://www.cplusplus.com/reference/set/set/) defines the std::set::iterator returned by non-const version of begin and end as :

a bidirectional iterator to const value_type

So, even non-const std::set::iterator returns a const object.

Answer 8

There is in fact nothing wrong with modifying elements in the functor of a for_each:

If InputIt is a mutable iterator, f may modify the elements of the range through the dereferenced iterator

So next we should look at the definition of set, note that since c++11 clarified this, both it's iterator and const_iterator types are: "Constant Bidirectional Iterators".

So it is undefined behavior to modify a set with a for_each.