vendredi 30 octobre 2020

Why does std::copy() require std::back_inserter to insert into a vector with sufficient capacity?

REFERENCE CODE:

#include <vector>
#include <algorithm>
#include <string>

void print(std::string label, std::vector<int> & arr) {
  std::cout << label << ":" << " size: " << arr.size() << " cap: " << arr.capacity() << " [ ";
  for (auto elem : arr) {
    std::cout << elem << " ";
  }
  std::cout << " ] " << std::endl;
}

void reserve_dest_use_begin() {
  std::vector<int> s_arr = {0, 1, 2, 3, 4, 5}; 
  print("source", s_arr);

  std::vector<int> d_arr;
  d_arr.reserve(3);
  print("dest", d_arr);

  auto min_elems = std::min(s_arr.size(), d_arr.capacity());

  std::cout << "COPYING FIRST" << min_elems << "3 FROM SOURCE TO DEST" << std::endl;

  std::copy(s_arr.begin(), s_arr.begin() + min_elems, d_arr.begin());

  print("source", s_arr);
  print("dest", d_arr);
}

void reserve_dest_use_back_inserter() {
  std::vector<int> s_arr = {0, 1, 2, 3, 4, 5}; 
  print("source", s_arr);

  std::vector<int> d_arr;
  d_arr.reserve(3);
  print("dest", d_arr);

  auto min_elems = std::min(s_arr.size(), d_arr.capacity());

  std::cout << "COPYING FIRST" << min_elems << " ELEMENTS FROM SOURCE TO DEST" << std::endl;

  std::copy(s_arr.begin(), s_arr.begin() + min_elems, std::back_inserter(d_arr));

  print("source", s_arr);
  print("dest", d_arr);
}

int main() {
  std::cout << "RESERVE DEST ARR. USE BEGIN() TO COPY" << std::endl;
  reserve_dest_use_begin();
  std::cout << "RESERVE DEST ARR. USE BACK_INSERTER() TO COPY" << std::endl;
  reserve_dest_use_back_inserter();

OUTPUT:

RESERVE DEST ARR USE BEGIN() TO COPY
source: size: 6 cap: 6 [ 0 1 2 3 4 5  ] 
dest: size: 0 cap: 3 [  ] 
COPYING FIRST 3 ELEMENTS FROM SOURCE TO DEST
source: size: 6 cap: 6 [ 0 1 2 3 4 5  ] 
dest: size: 0 cap: 3 [  ] 
=============================================
RESERVE DEST ARR USE BACK_INSERTER() TO COPY
source: size: 6 cap: 6 [ 0 1 2 3 4 5  ] 
dest: size: 0 cap: 3 [  ] 
COPYING FIRST 3 ELEMENTS FROM SOURCE TO DEST
source: size: 6 cap: 6 [ 0 1 2 3 4 5  ] 
dest: size: 3 cap: 3 [ 0 1 2  ]

In both scenarios, the destination array has sufficient capacity. The documentation from cppreference indicates:

Copies the elements in the range, defined by [first, last), to another range beginning at d_first.
1) Copies all elements in the range [first, last) starting from first and proceeding to last - 1. The behavior is undefined if d_first is within the range [first, last). In this case, std::copy_backward may be used instead.

The d_arr.begin() points to a range that is outside of the source range of [first, last), but in the provided example, I need to use std::back_inserter() to copy instead of just providing d_arr.begin() despite the underlying vector having enough capacity.

Is the std::back_inserter() operation optimized to just memmove the block of memory, or is it pushing back every element? The note from cppreference indicates:

In practice, implementations of std::copy avoid multiple assignments and use bulk copy functions such as std::memmove if the value type is TriviallyCopyable and the iterator types satisfy LegacyContiguousIterator.

However, with std::back_inserter() I suspect it doesn't optimize with memmove.

In summary, I have the following questions:

  1. Why can't I use d_arr.begin() as the OutputIt in std::copy when the underlying vector has sufficient capacity?
  2. Is use std::back_inserter() optimized to bulk copy ranges?

Aucun commentaire:

Enregistrer un commentaire