Эффективное накопление

Предположим, у меня есть вектор строк, и я хочу объединить их через std::accumulate.

Если я использую следующий код:

std::vector<std::string> foo{"foo","bar"};
string res=""; 
res=std::accumulate(foo.begin(),foo.end(),res,
  [](string &rs,string &arg){ return rs+arg; });

Я могу быть уверен, что будет временное строительство объекта.

В этом ответе говорится, что эффект std::accumulate указан следующим образом:

Вычисляет результат, инициализируя аккумулятор acc начальным значением init, а затем изменяя его с помощью acc = acc + *i или acc = binary_op(acc, *i) для каждого итератора i в диапазоне [first, last) по порядку.

Поэтому мне интересно, как правильно это сделать, чтобы избежать ненужной конструкции временного объекта.

Одна из идей заключалась в том, чтобы изменить лямбду следующим образом:

[](string &rs,string &arg){ rs+=arg; return rs; }

В этом случае я решил принудительно объединить строки и помочь компилятору (я знаю, что должен 't) опустите ненужную копию, так как это должно быть эквивалентно (псевдокоду):

accum = [](& accum,& arg){ ...; return accum; }

и поэтому

accum = & accum;

Другая идея состояла в том, чтобы использовать

accum = [](& accum,& arg){ ...; return std::move(accum); }

Но это, вероятно, приведет к чему-то вроде:

accum = std::move(& accum);

Что мне кажется очень подозрительным.

Как правильно написать это, чтобы свести к минимуму риск ненужного создания временных объектов? Меня не просто интересует std::string, я был бы рад получить решение, которое, вероятно, будет работать для любого объекта, в котором реализованы конструкторы/назначения копирования и перемещения.


person tach    schedule 29.10.2013    source источник
comment
Вы должны просто сделать функцию для конкатенации...   -  person user541686    schedule 29.10.2013
comment
Уродливой альтернативой является использование указателя на локальную переменную std::string в качестве аккумулятора и, возможно, reserve заранее. Хотя теперь accumulate уменьшено до for_each, и это ненамного лучше, чем решение Дэвида ниже.   -  person R. Martinho Fernandes    schedule 29.10.2013
comment
Похоже, что std::accumulate всегда будет делать временные копии. Если это неприемлемо, то нужно использовать что-то другое.   -  person Mark Ransom    schedule 29.10.2013
comment
@MarkRansom std::accumulate не делает временных копий; это operator+, который он вызывает, который делает дополнительную копию. (Кроме того, operator= может закончиться копированием; с C++ и семантикой перемещения, скорее всего, этого не произойдет, но с более ранними версиями это произойдет.)   -  person James Kanze    schedule 30.10.2013
comment
C++20 определяет его как acc = move(acc) + rhs, что может значительно удешевить накопление типов, копирование которых обходится недешево. Например, хорошая реализация std::string будет иметь operator+(string&& lhs, T), который перехватывает lhs, добавляет к нему и возвращает его (что является RVO-способным). @R.MartinhoFernandes Менее уродливым эквивалентом этого является накопление в reference_wrapper, как в этом ответе, но да, я интересно, действительно ли это намного/лучше, чем просто for[_each] с захваченной ссылкой. Я думаю, может быть, немного, семантически?   -  person underscore_d    schedule 24.09.2018


Ответы (4)


Попробуйте следующее

res=std::accumulate(foo.begin(),foo.end(),res,
  [](string &rs, const string &arg) -> string & { return rs+=arg; });

Перед этим звонком, может быть, есть смысл позвонить

std::string::size_type n = std::accumulate( foo.begin(), foo.end(), 
   std::string::size_type( 0 ),
   [] ( std::string_size_type n, const std::string &s ) { return ( n += s.size() ); } );

res.reserve( n );
person Vlad from Moscow    schedule 29.10.2013
comment
Это сделает копии в аккумуляторе, используемом внутри accumulate (это эквивалентно accum = op(accum, *it);. - person R. Martinho Fernandes; 29.10.2013
comment
Никакого совладания нет. Существует оператор присваивания копирования, который увидит, что строка пытается присвоить сама себе. - person Vlad from Moscow; 29.10.2013
comment
@VladfromMoscow: Вы уверены? Это происходит только в этом случае или это работает для return rs; что я тоже сказал в своем вопросе? Если бы я мог положиться на него или, по крайней мере, быть уверенным, этого было бы достаточно для меня. - person tach; 29.10.2013
comment
@tach, если вы сделаете это [](string &rs,string &arg) -> string& { ..., то да, это относится и к вашему примеру. - person R. Martinho Fernandes; 29.10.2013
comment
Это правда, только что проверил. Большое спасибо! - person tach; 29.10.2013
comment
версия без лямбда: std::string result; std::accumulate<std::string::iterator, std::string&>(foo.begin(), foo.end(), result);. В C+11 присваивание внутри std::accumulate (v = v + s) превращается в обмен из-за семантики перемещения. Это не бесплатно, но не требует копирования символов. - person rici; 29.10.2013
comment
@VladfromMoscow Это была бы очень плохая реализация оператора присваивания std::string. Замедлите обычный случай (хотя бы немного), чтобы улучшить производительность редкого случая. - person James Kanze; 29.10.2013
comment
@rici Он все еще создает новый строковый объект (с копией) для возврата из оператора +. - person James Kanze; 29.10.2013
comment
@JamesKanze, оператор присваивания должен обрабатывать случай, когда вы присваиваете себе значение, каким бы редким оно ни было. Однако есть и другие методы, такие как получение параметра копией вместо ссылки (позволяя конструктору копирования выполнять работу) и замена содержимого - это работает, но не позволяет избежать накладных расходов, как следует из этого ответа. - person Mark Ransom; 29.10.2013
comment
@MarkRansom: в данном случае это назначение перемещения, а не копирование. Он по-прежнему должен обрабатывать самоназначение, но ему нужно только выполнить обмен, а не копирование и обмен. - person rici; 29.10.2013
comment
@JamesKanze: Хорошая мысль, хотя реальность немного отличается. Он создает новую строку с копией в качестве аргумента +, но результат не копируется; он заменен. Это потому, что operator+(std::string,std::string) определяется через std::string::operator+= (что-то вроде: std::string r = a; r += b; return r; ) - person rici; 29.10.2013
comment
@MarkRansom Конечно, оператор присваивания должен работать, если вы присваиваете себе. Но для этого вам не нужно проверять самоназначение; на самом деле, если вам нужно проверить самоназначение, оператор, вероятно, не работает. - person James Kanze; 30.10.2013

Я бы разбил это на две операции: сначала std::accumulate для получения общей длины строки, которую необходимо создать, затем std::for_each с лямбдой, которая обновляет локальную строку:

std::string::size_type total = std::accumulate(foo.begin(), foo.end(), 0u, 
                [](std::string::size_type c, std::string const& s) {
                    return c+s.size() 
                });
std::string result;
result.reserve(total);
std::for_each(foo.begin(), foo.end(), 
              [&](std::string const& s) { result += s; });

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

person David Rodríguez - dribeas    schedule 29.10.2013
comment
Я пытаюсь заставить std::accumulate работать эффективно, то есть избегать ненужного создания временных объектов. Я не против реаллоков. Я могу избежать std::accumulate и заставить эффективное поведение другим способом, но это не то, что я ищу. - person tach; 29.10.2013
comment
Хорошая идея! Это, вероятно, не станет более эффективным, чем это, и это также достаточно короткий код. +1 - person stefan; 29.10.2013
comment
@tach: вы можете выбрать желаемое поведение или инструмент, который вы используете, но вы не можете открутить его молотком. -- Хотя это не совсем так, если вы готовы приложить достаточно усилий, вы можете создать для этого инфраструктуру (опять же, подход типа шаблонов выражений). - person David Rodríguez - dribeas; 29.10.2013
comment
Я предполагаю, что в некоторых случаях компилятор может оптимизировать создание временных объектов или, по крайней мере, как-то смягчить его. Я бы хотел использовать std::accumulate из-за его синтаксиса, но если он всегда неэффективен, я бы сказал, что его полезность значительно снижается. - person tach; 29.10.2013
comment
@tach: проблема не в оптимизации с точки зрения компилятора того, что такое оптимизация. Вы хотите, чтобы он изменил вызовы operator+ и сопоставил их с operator+=, но компилятор не знает об этой эквивалентности. Обратите внимание, что хотя std::string является частью стандарта, он реализован как определяемый пользователем тип, и компилятор, скорее всего, знает не так много, как вы. - person David Rodríguez - dribeas; 29.10.2013
comment
Я думаю, что вы имеете правильную идею, но ошибаетесь в паре деталей. Мне пришлось сделать несколько модов, чтобы это скомпилировалось. Вы знаете, почему accumulate не суммирует размеры? ideone.com/Kc1vf8 - person Mark Ransom; 29.10.2013
comment
@MarkRansom: я не обращал внимания на детали. В вашей ссылке ideone проблема в том, что accumulate возвращает новое значение, оно не изменяет аргумент. Результат накопления игнорируется (как в моем исходном коде, так и в вашем коде) - person David Rodríguez - dribeas; 29.10.2013
comment
Кстати, если бы я действительно спрашивал, как сделать конкатенацию эффективной, а не об оптимизации std::accumulate, я бы предпочел этот код: ideone.com/2kpX2q . Семантически он почти такой же, как ваш код, но менее типичен. (Даже с std::string::size_type он будет короче). - person tach; 30.10.2013
comment
@tach: обратите внимание, что принятый ответ не гарантирует оптимизации стоимости временных материалов. Реализация std::string может использовать идиому копирования и замены, и в этом случае назначение, скрытое внутри std::accumulate, потребует создания дополнительной строки. VS явно проверяет самоназначение, а gcc использует (неправильный) подсчет ссылок, поэтому ни на одной из платформ стоимость отсутствует, но в разных реализациях все может быть по-разному. - person David Rodríguez - dribeas; 30.10.2013
comment
@DavidRodríguez-dribeas Независимо от реализации: возвращаемое значение operator+ представляет собой строку, отличную от его аргументов. В a = a + b оператор a + b должен создать новый объект, скопировав a и b в этот новый объект. - person James Kanze; 30.10.2013
comment
@DavidRodríguez-dribeas Когда вы говорите, что g++ использует неправильный подсчет ссылок, вы имеете в виду проблему безопасности потоков, которую я обнаружил много лет назад, или что-то еще. (На практике, хотя легко показать проблему безопасности потоков, она требует такой экзотической комбинации действий, что я сомневаюсь, что кто-то действительно видел ее в реальном коде.) - person James Kanze; 30.10.2013
comment
@JamesKanze: под давлением Дитмара Кхюля я теперь использую C++ для ссылки на C++11 и C++03 для более старого стандарта. В C++11 реализация не может использовать подсчет ссылок. Честно говоря, они исправили это, но вы должны согласиться на новое поведение, так как это бинарное несовместимое изменение. Насколько я знаю, в g++ 4.8 поддерживается нестандартное поведение подсчета ссылок. - person David Rodríguez - dribeas; 30.10.2013
comment
@DavidRodríguez-dribeas Я думал об этом. До C++11 выраженное намерение заключалось в разрешении подсчета ссылок, поскольку это действительно предпочтительная реализация для многих применений. Является ли тот факт, что это больше не является законным, преднамеренным (что означало бы большой шаг назад) или просто случайным побочным эффектом попытки исправить некоторые неверные формулировки? - person James Kanze; 31.10.2013
comment
@JamesKanze: Похоже, это сделано намеренно. Проверьте N2668. - person David Rodríguez - dribeas; 31.10.2013
comment
@DavidRodríguez-dribeas Или, по крайней мере, они это поняли и рассмотрели последствия. (Мне скорее понравился CoW, но его трудно эффективно и реализовать в многопоточной среде.) - person James Kanze; 31.10.2013
comment
что касается вывода шаблона std::acculumate, я бы заменил 0u на std::string::size_type(0) или статическое приведение к этому типу. - person JHBonarius; 09.09.2020

Эффективное использование std::accumulate без каких-либо избыточных копий неочевидно.
Помимо переназначения и передачи в лямбда-выражение и из него, накапливающееся значение может быть скопировано внутри реализации.
Также обратите внимание, что std::accumulate() сам принимает начальное значение по значению, вызывая копию -ctor и, таким образом, игнорируя любые reserve(), выполненные в источнике копии (как предлагается в некоторых других ответах).

Наиболее эффективный способ объединения строк, который я нашел, выглядит следующим образом:

std::vector<std::string> str_vec{"foo","bar"};

// get reserve size:
auto sz = std::accumulate(str_vec.cbegin(), str_vec.cend(), std::string::size_type(0), [](int sz, auto const& str) { return sz + str.size() + 1; });

std::string res;
res.reserve(sz);
std::accumulate(str_vec.cbegin(), str_vec.cend(),
   std::ref(res), // use a ref wrapper to keep same object with capacity
   [](std::string& a, std::string const& b) -> std::string& // must specify return type because cannot return `std::reference_wrapper<std::string>`.
{                                                           // can't use `auto&` args for the same reason
   a += b;
   return a;
});

Результатом будет res.
В этой реализации нет избыточных копий, перемещений или перераспределений.

person Adi Shavit    schedule 14.09.2016
comment
@VaughnCato: Спасибо :-). На самом деле я исследовал эту же проблему и понял это за пару дней до того, как нашел вопрос. - person Adi Shavit; 18.09.2016

Это немного сложно, так как задействованы две операции: сложение и присваивание. Чтобы избежать копирования, вы должны изменить строку в дополнении, и убедиться, что присваивание не выполняется. Это вторая часть, которая является сложной.

То, что я делал в некоторых случаях, - это создание собственного «аккумулятора» в соответствии с строками:

class Accu
{
    std::string myCollector;
    enum DummyToSuppressAsgn { dummy };
public:
    Accu( std::string const& startingValue = std::string() )
        : myCollector( startingValue )
    {
    }
    //  Default copy ctor and copy asgn are OK.
    //  On the other hand, we need the following special operators
    Accu& operator=( DummyToSuppressAsgn )
    {
        //  Don't do anything...
        return *this;
    }
    DummyToSuppressAsgn operator+( std::string const& other )
    {
        myCollector += other;
        return dummy;
    }
    //  And to get the final results...
    operator std::string() const
    {
        return myCollector;
    }
};

Будет несколько копий при вызове accumulate и возвращаемого значения, а при фактическом накоплении ничего. Просто вызовите:

std::string results = std::accumulate( foo.begin(), foo.end(), Accu() );

(Если вас действительно беспокоит производительность, вы можете добавить аргумент емкости в конструктор Accu, чтобы он мог выполнять reserve в строке-члене. Если бы я сделал это, я, вероятно, также написал бы конструктор копирования вручную. , чтобы убедиться, что строка в скопированном объекте имеет требуемую емкость.)

person James Kanze    schedule 29.10.2013