C++ std::transform side effect

Question

I've implementation of UnaryOperation like this

struct Converter
{
    Converter( std::size_t value ):
        value_( value ), i_( 0 )
    {}
    std::string operator() ( const std::string& word )
    {
        return ( value_ & ( 1 << i_++ ) ) ?
            word:
            std::string( word.size(), ' ' );
    }
    std::size_t value_;
    std::size_t i_;
};

And I use it like

std::vector v;
// initialization of v  
std::transform( v.begin(), v.end(),
                std::back_inserter( result ),
                Converter( data ) );

My question is can I rely on my assumption that algorithm will call my 'Converter operator ()' in the order that 'Converter::i_' will correspond to number of element in 'v'.

Please quote the standard in case I can't rely on the order or put the stl-like solution that avoid possible problem if any.

Thanks.

Edit:

I am aware of "no Side effect" requirements in the standard for the transform algorithm. I can't find what is exactly "side effect" for functors in the same standard.

Maybe there is some good-looking-boost-like solution for this task?

Answer 1

Yes and no. This is because you feed iterators to your Converter object. For a sequence container like vector you get i to correspond to the order of the elements. However, for associative containers like map/multimap/set/multiset this may not be (will most probably not be) valid.

Answer 2

I've just checked the standard and if I understand it correctly the answer is no. The description of 'transform' has the following additional requirement (25.2.3):

Requires: op and binary_op shall not have any side effects.

Reaching back into the depths of my memory, I remember a talk given Nicolai Josuttis at an ACCU conference, where he showed that for a particular type of container and STL implementation, the function object was copied. Éric provided this link to a Dr. Dobb's article that discusses the differences in more detail.

EDIT: Alternative solution:

The *for_each* algorithm does not have this restriction, so you could change your Converter object to take a reference to the result vector and do the push_back inside the Converter function.

struct Converter
{
  Converter( std::size_t value, std::vector<std::string> & result ):
      value_( value ), i_( 0 ), result_(result)
  {}
  void operator() ( const std::string& word )
  {
    result_.push_back ( value_ & ( 1 << i_++ ) ) ?
             word:
             std::string( word.size(), ' ' );
  }
  std::size_t value_;
  std::size_t i_;
  std::vector<std::string> & result_;
};

And use *for_each* rather than transform:

std::vector v;
// initialization of v  
std::for_each ( v.begin()
              , v.end(),
              Converter( data, result ) );

Answer 3

Qute from standard:

25.2.3 Transform [lib.alg.transform]
Requires:
op and binary_op shall not have any side effects.

Side Effect ( wikipedia definition )

In your case we have next side effect:

Converter c( data );  
c( some_const_value ) != c( some_const_value );

You don't have any guarantees for your algorithms, but I belive that it will works on almost all stl implementations.

Suggested solution
It seems I know one way to do what you need:
use boost::counting_iterator - for iterate over two containers;

it will looks like:

bool bit_enabled( size_t data, unsigned char number )
{
    return ( data & 1 << number ) != 0;
}

std::string select_word( 
             const std::string& word,
             size_t data, 
             size_t number )
{
    return bit_enabled( data, number ) ? word : std::string( ' ', word.length() );
}

const size_t data = 7;
const boost::array< std::string, 3 > vocabulary = { "a", "b", "c" };
std::vector< std::string > result;
std::transform(
    vocabulary.begin(),
    vocabulary.end(),
    boost::counting_iterator< size_t >(0),
    back_inserter( result ),
    boost::bind( &select_word, _1, data, _2 )
);

Also maybe if you will define bit iterator or will use some bit container you will can use boost::zip_iterator for iterate both containers.

EDIT:
Yestarday I found interest article which contain definition of Side Effect by standard.

The Standard defines a side effect as follows: Accessing an object designated by a volatile lvalue, modifying an object, calling a library I/O function, or calling a function that does any of those operations are all side effects, which are changes in the state of the execution environment.

EDIT:
I hope it will be latest edit.
I am always tought that "no have side effect" mean:
f(a) should be equal f(a) always. ( f independed from execution environment: memory/cpu/global variables/member variables as in your case etc).
"Not produce side effect" mean - don't changing execution environment.

But in c++ standard we have more low-level defintion for Side effect.

Thing what you do in your example named as Stateful functor.
Standard doesn't say about "Statefull" functors, but also doesn't say about count of copies of your functor - you couldn't use this trick because it is unspecified behavior.

See Standard Library Issues list ( similar issue for predicat ):
http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-active.html#92

Answer 4

As an example of a case where side-effects would be a definite bad thing, consider a hypothetical parallel STL implementation which split the work between several CPUs.

I believe this was in the minds of the authors of STL. The original STL was from SGI, one of the larger names in building massively parallel single-image and cluster systems.