Three things: - value_type should just be pair< Key, T > (no reference or const qualifications on Key or T) - reference should be pair< Key const &, T& >, with T possibly const-qualified (as you've done) - you can (if you want) use iterator_adaptor instead of iterator_facade to automatically get a correct equal, increment, and decrement. I have modified the code as you have suggested and now it compiles OK. The modified code is available at http://codepad.org/AJFIVbdY.
However, there is one thing I'm concerned about. Consider the example at http://codepad.org/plyTCBpx. The following lines do not call the copy constructor of class A: BOOST_FOREACH(auto pair, m) { const A &key = pair.first; } However, when I use range adaptors, the copy constructor is called. That was exactly what I was trying to avoid by using references in value_type. I guess I'll try to fix this by myself and then file a patch. -- Best regards, Alexander Fokin, http://elric.ru.