What is the most efficient way to add arbitrary number of elements to an std::vector in C++?

Question

I have a defined class A and an std::vector vec that stores a series of A instances. I attempt to write a function that appends an arbitrary number of A instances to vec.

Should I use vec.reserve() along with vec.push_back() since constantly resizing vector is expensive? Or, should I use vec.insert()?

Currently, I'm not sure if I should design the function to accept a variable number of arguments using variadic functions or a vector of A instances that I'd like to combine and then concatenate with vec?

What is an efficient way to design this function (speed is critical and A is a complex class)?

Answer 1

The following should cover common cases, I think. The rref_capture trick is from this answer. The point of it all is that the values are moved whenever possible.

You can also use a variadic template version, as given in the other answer.

// https://github.com/KubaO/stackoverflown/tree/master/questions/vector-append-40274282
#include <array>
#include <cassert>
#include <initializer_list>
#include <iterator>
#include <type_traits>
#include <vector>

template<typename T>
class rref_capture {
   T* ptr;
public:
   rref_capture(T&& x) : ptr(&x) {}
   operator T&& () const { return std::move(*ptr); } // restitute rvalue ref
};

template <typename T>
void append(std::vector<T> & v,
            typename std::decay<std::initializer_list<rref_capture<T>>>::type u) {
   v.reserve(v.size() + u.size());
   for (auto && item : u)
      v.push_back(std::move(item));
}

template <typename T, typename U>
void append(std::vector<T> & v, U && u) {
   v.reserve(v.size() + std::distance(std::begin(u), std::end(u)));
   for (auto & item : u)
      v.push_back(std::move(item));
}

template <typename T, typename U>
void append(std::vector<T> & v, U & u) {
   v.reserve(v.size() + std::distance(std::begin(u), std::end(u)));
   for (auto & item : u)
      v.push_back(item);
}

struct A {
   static int copies, moves;
   A() {}
   A(A&&) { moves++; }
   A(const A&) { copies++; }
   A& operator=(const A&) { copies++; return *this; }
   static void reset() { A::copies = 0; A::moves = 0; }
};
int A::copies, A::moves;

int main() {
   std::vector<A> vec;
   vec.reserve(100);

   A::reset();
   append(vec, {A(), A()});
   assert(A::copies == 0 && A::moves == 2 && vec.size() == 2);

   auto vec2 = vec;
   A::reset();
   append(vec, vec2);
   assert(A::copies == 2 && A::moves == 0 && vec.size() == 4);

   A::reset();
   append(vec, std::move(vec2));
   assert(A::copies == 0 && A::moves == 2 && vec.size() == 6);

   A::reset();
   append(vec, std::array<A,2>{A(), A()});
   assert(A::copies == 0 && A::moves == 2 && vec.size() == 8);

   const std::vector<A> cvec{2};
   A::reset();
   append(vec, cvec);
   assert(A::copies == 2 && A::moves == 0 && vec.size() == 10);

   A arr[2];
   A::reset();
   append(vec, arr);
   assert(A::copies == 2 && A::moves == 0 && vec.size() == 12);
}

Answer 2

Well... I suppose you could use reserve() one time and then add the single element using push_back().

The following example use int instead of class A but should give the idea

#include <vector>
#include <iostream>

template <typename T>
void appendT (std::vector<T> & v)
 { }

template <typename T, typename ... Ts>
void appendT (std::vector<T> & v, T t, Ts ... ts)
 { 
   v.push_back(t);

   appendT(v, ts...);
 }

template <typename T, typename ... Ts>
void appendTs (std::vector<T> & v, Ts ... ts)
 {
   v.reserve(v.size() + sizeof...(Ts));

   appendT(v, ts...);
 }

int main()
 {
   std::vector<int> v { 2, 3, 5 };

   appendTs(v, 7, 11, 13, 17);

   for ( auto const & i : v )
      std::cout << ' ' << i; // print " 2 3 5 7 11 13 17"

   std::cout << std::endl;
 }

If you don't like the recursive solution, you can write an appendTs() that do all the works (but I don't know how to avoid the annoing "warning: unused variable 'unused'" I know how to avoid the warning but I don't know if it's a good idea Kuba Ober suggested me an elegant way to avoid the warning)

#include <vector>
#include <iostream>

template <typename T, typename ... Ts>
void appendTs (std::vector<T> & v, Ts ... ts)
 {
   v.reserve(v.size() + sizeof...(Ts));

   // the first '0' is to avoid an error when sizeof...(Ts) is zero
   char unused[] { '0', (v.push_back(ts), '0')... };

   // the following statement is to avoid an annoing "unused variable
   // 'unused'" warning (thanks Kuba Ober)
   (void)unused;
 }

int main()
 {
   std::vector<int> v { 2, 3, 5 };

   appendTs(v, 7, 11, 13, 17);

   for ( auto const & i : v )
      std::cout << ' ' << i; // print " 2 3 5 7 11 13 17"

   std::cout << std::endl;
 }