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.