How to self-copy a vector?

Question

Let's say I have a vector<string> containing "a" and "b", I wanna copy itself 2 times so that the vector now contains "a", "b", "a", "b", "a", "b"

What is a better approach than using for and push_back?

Answer 1

My initial thought:

myvec.reserve(myvec.size()*3);  //reserve not only speeds things upt it also protects us ftom iterator invalidation
vector<string>::iterator it = myvec.end();    //we ant to add two times the origional onto the end so we save the end of the origional end
myvec.insert(myvec.end(), myvec.begin(), it);
myvec.insert(myvec.end(), myvec.begin(), it);

thanks to Emilio Garavaglia for first pointing out problems with this, see here many reasons why this has problems: Does std::vector::insert() invalidate iterators if the vector has enough room (created through reserve)?

Second try:

std::size_t size = myvec.size();
myvec.resize(size*3);  //resize must protects us from iterator invalidation
vector<string>::iterator it = myvec.begin()+size;
std::copy(myvec.begin(),it,it);
std::copy(myvec.begin(),it,it+size);

since no implementation is going to implement a std::string whos default constructor allocates something on the heap this should cause less heap access and therefore be faster than others examples.

Another heap access minimization is to copy the vector into another insert it and then move in the originals, I stole Emilio Garavaglia code and pimped it:

{
vector<string> m = { "a", "b" };
auto n = m; // keep initial value safe
m.reserve(3 * m.size()); // preallocate, to avoid consecutive allocations
m.insert(m.end, n.begin(), n.end());
std::for_each(n.begin(),n.end(),[&n](std::string &in){n.emplace_back(std::move(in));});
}

Answer 2

vector<string> m = { "a", "b" };

auto n = m; // keep initial value safe

m.reserve(3 * m.size()); // preallocate, to avoid consecutive allocations
m.insert(m.end, n.begin(), n.end());
m.insert(m.end, n.begin(), n.end());

Answer 3

My first thought is the following to avoid problems with invalidating iterators.

{   // note: nested scope
    vector<string> temp(vec); // 1st copy
    temp.insert(temp.end(), vec.begin(), vec.end()); // 2nd copy
    temp.insert(temp.end(), vec.begin(), vec.end()); // 3rd copy
    temp.swap(vec); // swap contents before temp is destroyed
}

On review, I think PorkyBrain and Emilio Garavaglia's answers might make more sense.

Answer 4

Here is a simple method:

template<typename T, typename A1, typename A2>
std::vector<T, A1> operator+( std::vector<T, A1> left, std::vector<T, A2> const& right ) {
  left.insert( left.end(), right.begin(), right.end() );
  return left;
}


int main() {
  std::vector<string> m = { "a", "b" );

  m = m + m + m;
}

but as @ChristianAmmer noted, overriding operator+ on a std::vector is ambiguous. And that would be wrong.

So you could go and write an entire infix named operator syntax, and use the magic of C++ to embed it in the C++ language, to get rid of that ambiguity. Sort of like this:

#include <utility>

template<typename Operation, short op>
struct InfixOp {
  Operation* self() { return static_cast<Operation*>(this); }
  Operation const* self() const { return static_cast<Operation const*>(this); }
};

template<typename first_type, typename Infix, short op>
struct PartialForm {
  Infix const* infix;

  first_type a;

  template<typename T>
  PartialForm(T&& first, Infix const* i):infix(i), a(std::forward<T>(first)) {}
};

#define OVERRIDE_OPERATORS(OP, CODE) \
template<\
  typename Left,\
  typename Operation\
>\
PartialForm<typename std::remove_reference<Left>::type, Operation, CODE> operator OP( Left&& left, InfixOp<Operation, CODE> const& op ) {\
  return PartialForm<typename std::remove_reference<Left>::type, Operation, CODE>( std::forward<Left>(left), op.self() );\
}\
\
template<\
  typename Right,\
  typename First,\
  typename Operation\
>\
auto operator OP( PartialForm<First, Operation, CODE>&& left, Right&& right )\
  ->decltype( (*left.infix)( std::move( left.a ), std::forward<Right>(right)) )\
{\
  return (*left.infix)( std::move( left.a ), std::forward<Right>(right) );\
}

OVERRIDE_OPERATORS(+, '+')
OVERRIDE_OPERATORS(*, '*')
OVERRIDE_OPERATORS(%, '%')
OVERRIDE_OPERATORS(^, '^')
OVERRIDE_OPERATORS(/, '/')
OVERRIDE_OPERATORS(==, '=')
OVERRIDE_OPERATORS(<, '<')
OVERRIDE_OPERATORS(>, '>')
OVERRIDE_OPERATORS(&, '&')
OVERRIDE_OPERATORS(|, '|')
//OVERRIDE_OPERATORS(!=, '!=')
//OVERRIDE_OPERATORS(<=, '<=')
//OVERRIDE_OPERATORS(>=, '>=')


template<typename Functor, char... ops>
struct Infix:InfixOp<Infix<Functor, ops...>, ops>...
{
  Functor f;
  template<typename F>
  explicit Infix(F&& f_in):f(std::forward<F>(f_in)) {}
  Infix(Infix<Functor, ops...> const& o):f(o.f) {}
  Infix(Infix<Functor, ops...>&& o):f(std::move(o.f)) {}
  Infix(Infix<Functor, ops...>& o):f(o.f) {}
  template<typename L, typename R>
  auto operator()( L&& left, R&& right ) const
    -> decltype( f(std::forward<L>(left), std::forward<R>(right)))
  {
    return f(std::forward<L>(left), std::forward<R>(right));
  }
};

template<char... ops, typename Functor>
Infix<Functor, ops...> make_infix( Functor&& f )
{
  return Infix<Functor, ops...>(std::forward<Functor>(f));
}

#include <vector>

struct append_vectors {
  template<typename T>
  std::vector<T> operator()(std::vector<T> left, std::vector<T>const& right) const {
    left.insert(left.end(), right.begin(), right.end());
    return std::move(left);
  }
};

struct sum_elements {
  template<typename T>
  std::vector<T> operator()(std::vector<T> left, std::vector<T>const& right) const {
    for(auto it = left.begin(), it2 = right.begin(); it != left.end() && it2 != right.end(); ++it, ++it2) {
      *it = *it + *it2;
    }
    return left;
  }
};
struct prod_elements {
  template<typename T>
  std::vector<T> operator()(std::vector<T> left, std::vector<T>const& right) const {
    for(auto it = left.begin(), it2 = right.begin(); it != left.end() && it2 != right.end(); ++it, ++it2) {
      *it = *it * *it2;
    }
    return left;
  }
};

#include <iostream>

int main() {
  auto append = make_infix<'+'>(append_vectors());
  auto sum = make_infix<'+'>(sum_elements());
  auto prod = make_infix<'*'>(prod_elements());

  std::vector<int> a = {1,2,3};
  a = a +append+ a +append+ a;
  a = a +sum+ a;
  a = a *prod* a;

  std::cout << a.size() << "\n";
  for (auto&& x:a) {
    std::cout << x << ",";
  }
  std::cout << "\n";
}

which has the advantage of clarity at the point where you use it (I mean, a = a +append+ a is pretty clear what it intends to do), at the cost of being a bit tricky to understand how it works, and a bit verbose for such a simple problem.

But at least the ambiguity is gone, which is a good thing, right?