std::transform needs special care with sets

Question

I don't understand why this snippet of code compiles:

#include <set>
#include <list>
#include <algorithm>

int modify(int i)
{
 return 2*i;
}

int main (int args, char** argv)
{
  std::set<int> a;
  a.insert(1);
  a.insert(2);
  a.insert(3);

  std::list<int> b;  // change to set here

  std::transform(a.begin(), a.end(), b.begin(), modify);   // line 19
}

while, if I just change the type of b from std::list<int> to std::set<int> it fails at compilation time (at line 19) with the error: read-only variable is not assignable. To use b as a set I need to change the transform line to

std::transform(a.begin(), a.end(), std::inserter(b, b.begin()), modify);

Why is that? I somehow guess the reason has to do with the fact that set is an associative container, while list is a sequence container, but I might be completely off the point here.

Edit

I forgot to mention: I tried this on gcc 3.4.2 and llvm 3.3 using the default standard (c++98). I tried again on llvm 3.3 using c++03 and I get the same behavior.

Answer 1

In your code without std::inserter, transform assigns to *b.begin(). In the case of set that's a const reference to an element (since C++11). Hence, a compile-time error.

In the case of the list it still assigns to *b.begin(), which compiles but has undefined behavior because the list has size 0. So b.begin() may not be dereferenced.

You are correct that this is to do with the fact that set is an associative container whereas list is a sequence. Associative containers don't let you modify the part of the element used as a key. In the case of set that part is the element, for map you can modify the value but not the key.

The whole point of std::inserter is to arrange that instead of assigning through an iterator, it calls insert.

Answer 2

First, the code as you have it exhibits undefined behavior, since the target list doesn't actually have space. Use a back_inserter to create space as you go.

As for the set, a set's elements are immutable. This is why you can't assign to a dereferenced iterator, even if you had space. But using the inserter is perfectly fine.

Answer 3

In C++03 this code compiles but results in undefined behavior - you cannot simply change values of set because they must be in ascending order. In c++11 that was fixed and set::iterator is a bidirectional iterator on const T, so you cannot change its values at all. std::inserter does not change existing values, instead it inserts new values in operator++ and so everything works

Answer 4

This record

std::transform(a.begin(), a.end(), b.begin(), modify);

is invalid even for std::list<int> (though it can be compiled for std::list or std::set in C++ 2003 where set has non-const iterator) because you defined an empty list.

std::list<int> b;

When such a record is used it is supposed that the output container already has elements in the range

[b.begin(), b.begin() + distance( a.begin(), a.end() ) )

because they are reassigned. So if to consider a set then it is supposed that the set has already all required elements but you may not change them. When you use iterator adapter std::insert_iterator then it adds new elements in the container. So in this case you may use a set.