Эффективно накапливать
Предположим, у меня есть вектор строк, и я хочу объединить их через std :: аккумулировать.
Если я использую следующий код:
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 :: аккумулируется следующим образом:
Вычисляет его результат, инициализируя аккумулятор в соответствии с
начальное значение init, а затем изменяет его с помощью acc = acc + * i или acc =
binary_op (acc, * i) для каждого итератора i в диапазоне [first, last) в
порядок.
Поэтому мне интересно, как правильно это сделать, чтобы избежать ненужной временной постройки объекта.
Одна идея состояла в том, чтобы изменить лямбду таким образом:
[](string &rs,string &arg){ rs+=arg; return rs; }
В этом случае я подумал, что заставлю эффективную конкатенацию строк и помочь компилятору (я знаю, я не должен) пропустите ненужную копию, поскольку она должна быть эквивалентна (псевдокод):
accum = [](& accum,& arg){ ...; return accum; }
и поэтому
accum = & accum;
Другая идея заключалась в использовании
accum = [](& accum,& arg){ ...; return std::move(accum); }
Но это, вероятно, приведет к чему-то вроде:
accum = std::move(& accum);
Что выглядит очень подозрительно для меня.
Как правильно написать это, чтобы минимизировать риск ненужного создания временных объектов? Я не просто заинтересован в std :: string, я был бы рад иметь решение, которое, вероятно, будет работать для любого объекта, в котором реализованы функции копирования и перемещения конструкторов / присваиваний.
Решение
Попробуйте следующее
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 );
Другие решения
Я бы разбил это на две операции, во-первых 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; });
Обычной альтернативой этому является использование шаблонов выражений, но это не вписывается в ответ. В основном вы создаете структуру данных, которая отображает операции, но не выполняет их. Когда выражение, наконец, будет оценено, оно может собрать необходимую информацию заранее и использовать ее, чтобы зарезервировать пространство и сделать копии. Код, который использует шаблон выражения, приятнее, но сложнее.
С помощью std::accumulate Эффективно без каких-либо избыточных копий не очевидно.
В дополнение к переназначению и передаче в и из лямбды-накопления значение может быть скопировано внутри реализации.
Также обратите внимание, что std::accumulate() сам принимает начальное значение по значению, вызывая copy-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,
Эта реализация имеет нет избыточные копии, перемещения или перераспределения.
Это немного сложно, так как есть два вовлеченные операции,
дополнение и назначение. Чтобы избежать копий,
вы должны оба изменить строку в дополнении, а также
убедитесь, что задание не разрешено. Это вторая часть
что сложно.
То, что я сделал в некоторых случаях, это создать собственный «аккумулятор»,
вдоль линий:
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 на строке члена. Если бы я сделал это, я бы
вероятно, вручную напишите конструктор копирования, чтобы
строка в скопированном объекте имела необходимую емкость.)