C ++ std :: transform побочный эффект

Question

У меня есть реализация UnaryOperation, подобная этой

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_;
};

И я использую это как

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

Мой вопрос - могу ли я полагаться на мое предположение, что алгоритм вызовет мой «Оператор преобразования ()» в том порядке, в котором «Преобразователь :: i_» будет соответствовать номеру элемента в «v».

Пожалуйста, указывайте стандарт на случай, если я не могу положиться на заказ, или поставьте решение, подобное stl, чтобы избежать возможных проблем, если таковые имеются.

Спасибо.

Edit:

Мне известны требования «без побочных эффектов» в стандарте для алгоритма преобразования. Я не могу найти то, что является "побочным эффектом" для функторов в том же стандарте.

Может быть, есть какое-то симпатичное решение для этой задачи?

Answer 1

Qute от стандарта:

25.2.3 Transform [lib.alg.transform]
Требуется:
op и binary_op не должны иметь побочных эффектов.

Побочный эффект (определение из Википедии)

В вашем случае у нас есть следующий побочный эффект:

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

У вас нет никаких гарантий для ваших алгоритмов, но я верю, что он будет работать практически на всех реализациях stl.

Предлагаемое решение
Кажется, я знаю один способ сделать то, что вам нужно:
использовать boost :: counting_iterator - для итерации по двум контейнерам;

это будет выглядеть так:

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 )
);

Также, возможно, если вы определите битовый итератор или будете использовать некоторый битовый контейнер, вы можете использовать boost :: zip_iterator для итерации обоих контейнеров.

EDIT:
Вчера я обнаружил интересную статью , в которой содержится стандарт определения побочного эффекта.

Стандарт определяет побочный эффект как следует: доступ к объекту обозначается изменчивым значением, изменение объекта, вызов библиотеки Функция ввода / вывода или вызов функции что делает любая из этих операций все побочные эффекты, которые являются изменениями в состояние исполнения окружающая среда.

EDIT:
Я надеюсь, что это будет последняя редакция.
Меня всегда убеждали, что «нет побочного эффекта» означает:
f (a) всегда должно быть равно f (a). (f не зависит от среды выполнения: память / процессор / глобальные переменные / переменные-члены, как в вашем случае и т. д.).
«Не вызывать побочный эффект» означает - не изменять среду исполнения.

Но в стандарте c ++ у нас есть более низкое определение побочного эффекта.

То, что вы делаете в вашем примере, называется Stateful функтор.
Стандарт не говорит о функторах «Statefull», но также не говорит о количестве копий вашего функтора - вы не могли использовать этот трюк, потому что это неуказанное поведение.

См. Список стандартных проблем с библиотекой (похожая проблема для предиката):
http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-active.html#92

Answer 2

Я только что проверил стандарт, и если я правильно понимаю, ответ - нет. Описание 'transform' имеет следующее дополнительное требование (25.2.3):

Требуется : op и binary_op не должны иметь побочных эффектов.

Вспоминая глубины своей памяти, я помню выступление Николая Йосуттиса на конференции ACCU , где он показал это для конкретного типа контейнера и реализации STL объект функции был скопирован. Эрик предоставил эту ссылку на статью доктора Добба, в которой более подробно обсуждаются различия.

РЕДАКТИРОВАТЬ: Альтернативное решение:

Алгоритм for_each не имеет этого ограничения, поэтому вы можете изменить свой объект Converter, чтобы получить ссылку на вектор результата и выполнить push_back внутри функции Converter.

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_;
};

И используйте for_each вместо transform :

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

Answer 3

В качестве примера случая, когда побочные эффекты были бы определенной плохой вещью , рассмотрим гипотетическую параллельную реализацию STL, которая разделяет работу между несколькими ЦП.

Я полагаю, что это было в умах авторов STL. Первоначальный STL принадлежал SGI, одному из крупнейших имен в создании массивно параллельных систем с одним изображением и кластером.

Answer 4

Я считаю, что есть некоторые случаи, когда ответ да, но также есть определенные случаи, когда нет. Не имея возможности вспомнить, какой (извините), и сделать код менее хрупким, я бы не стал полагаться на него и оставил бы себя вне функтора для безопасности. т.е. внутри Converter делать:

Converter( std::size_t value, std::size_t& i ): value_( value ), i_ ( i ) {}
и
std::size_t &i_;

Затем вызовите с помощью

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

Грязно, но безопаснее.

Answer 5

Да и нет. Это потому, что вы передаете итераторы в ваш Converter объект. Для контейнера последовательности, такого как vector, вы получаете i, соответствующий порядку элементов. Однако для ассоциативных контейнеров, таких как map/multimap/set/multiset, это может быть (скорее всего, не будет) допустимым.