In the following code which implements the Viterbi algorithm: (Wikipedia link)

std::pair<std::vector<index_t>, float> viterbi_get_optimal_path(const SoundGraph &g,
                                                      SequenceIter s_first,
                                                      SequenceIter s_last,
                                                      index_t curr_index) {
  if (s_first == s_last) {
    return {std::vector<index_t>({curr_index}), 1.0f};
  }
  std::vector<index_t> seq;
  float prob = 0.0f;
  for (const auto &[next_index, curr_sound] : g.edges(curr_index)) {
    if (curr_sound.sound_ == *s_first) {
      auto [res_seq, res_prob] =
          viterbi_get_optimal_path(g, std::next(s_first), s_last, next_index);
      if (res_prob > 0.0f && curr_sound.prob_ * res_prob > prob) {
        prob = curr_sound.prob_ * res_prob;
        std::swap(seq, res_seq);
        seq.push_back(curr_index);
      }
    }
  }
  return {seq, prob};
}

Is the std::vector<index_t> copied or moved in this line?

      auto [res_seq, res_prob] =
          viterbi_get_optimal_path(g, std::next(s_first), s_last, next_index);

I'd like to believe it was moved but I'm not sure.

index_t is just std::ptrdiff_t

CodePudding user response：

Assuming C 17 or later, it will be copied once if the function returns via return {seq, prob}; and moved once if it returns via return {std::vector<index_t>({curr_index}), 1.0f};.

You can avoid the copy, by explicitly moving in the return statement:

return {std::move(seq), prob};

In the most common case such a move of a local variable is implicitly done, but only if the return statement directly (and only) names the variable. That is not the case here, so you need to move manually.

You can potentially avoid the move operations as well by defining seq as a std::pair<std::vector<index_t>, float> instead and then returning return seq;. This so-called named return value optimization is not guaranteed, but the compiler is allowed to apply it. To help the compiler apply it, you might then want to make sure that both branches use return seq; then. Before applying this blindly, benchmark though. This is a significant enough change that other effects might dominate and end with worse overall result.