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

Предположим, что у меня есть вектор строк, и я хочу объединить их через 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(ППК *я) для каждого итератора 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, я был бы рад иметь решение, которое, вероятно, будет работать для любого объекта, в котором реализованы конструкторы копирования и перемещения/назначения.

4 7
c++ algorithm c++11 rvalue-reference

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

Я разбил бы это на две операции, сначала 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; });
Общей альтернативой этому является использование шаблонов выражений, но это не вписывается в ответ. В основном вы создаете структуру данных, которая отображает операции, но не выполняет их. Когда выражение окончательно вычисляется, оно может собрать необходимую информацию заранее и использовать ее для зарезервируйте место и сделайте копии. Код, использующий шаблон выражения, лучше, но сложнее.
11

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

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

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.
Эта реализация не имеетникаких избыточных копий, перемещений или перераспределений.

4

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

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

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 в строке члена. Если бы я это сделал, я бы ... вероятно, вручную написать конструктор копирования, а также, чтобы гарантировать, что строка в скопированном объекте имела требуемую емкость.)

1