This question already has answers here: Concatenating two std::vectors (27 answers) Closed 7 years ago.
Assuming I have 2 standard vectors:
vector<int> a;
vector<int> b;
Let's also say the both have around 30 elements.
How do I add the vector b to the end of vector a?
The dirty way would be iterating through b and adding each element via vector<int>::push_back()
, though I wouldn't like to do that!
insert
is sufficient?
a.append(b)
(or even a+=b
) would capture the intent much better than a.insert(a.end(), b.begin(), b.end())
.
a.insert(a.end(), b.begin(), b.end());
or
a.insert(std::end(a), std::begin(b), std::end(b));
The second variant is a more generically applicable solution, as b
could also be an array. However, it requires C++11. If you want to work with user-defined types, use ADL:
using std::begin, std::end;
a.insert(end(a), begin(b), end(b));
std::copy (b.begin(), b.end(), std::back_inserter(a));
This can be used in case the items in vector a have no assignment operator (e.g. const member).
In all other cases this solution is ineffiecent compared to the above insert solution.
std::vector<>::insert()
, because std::copy()
can't reserve enough space before-hand (it doesn't have access to the vector itself, only to an iterator which has), while std::vector<>::insert()
, being a member function, can. (It needs to figure out that the iterators to read from are random-access iterators in order to pre-calculate the sequence's length, but it would be a weak implementation which wouldn't do this.)
std::
implementor can make it work. They can use non-standard extensions internally.
std::back_inserter_iterator<std::vector<T>>
to allow an implementation of std::copy()
to recognize it and use this private interface to get hold of the std::vector
and call reserve()
on it. In practice, however, it's unlikely any implementer jumps through all these hoops to optimize such a corner case.
std::copy
is indeed slower than using std::vector::insert
. I just tested it with libstdc++ that came with g++ 4.4.5.
While saying "the compiler can reserve", why rely on it? And what about automatic detection of move semantics? And what about all that repeating of the container name with the begin
s and end
s?
Wouldn't you want something, you know, simpler?
(Scroll down to main
for the punchline)
#include <type_traits>
#include <vector>
#include <iterator>
#include <iostream>
template<typename C,typename=void> struct can_reserve: std::false_type {};
template<typename T, typename A>
struct can_reserve<std::vector<T,A>,void>:
std::true_type
{};
template<int n> struct secret_enum { enum class type {}; };
template<int n>
using SecretEnum = typename secret_enum<n>::type;
template<bool b, int override_num=1>
using EnableFuncIf = typename std::enable_if< b, SecretEnum<override_num> >::type;
template<bool b, int override_num=1>
using DisableFuncIf = EnableFuncIf< !b, -override_num >;
template<typename C, EnableFuncIf< can_reserve<C>::value >... >
void try_reserve( C& c, std::size_t n ) {
c.reserve(n);
}
template<typename C, DisableFuncIf< can_reserve<C>::value >... >
void try_reserve( C& c, std::size_t ) { } // do nothing
template<typename C,typename=void>
struct has_size_method:std::false_type {};
template<typename C>
struct has_size_method<C, typename std::enable_if<std::is_same<
decltype( std::declval<C>().size() ),
decltype( std::declval<C>().size() )
>::value>::type>:std::true_type {};
namespace adl_aux {
using std::begin; using std::end;
template<typename C>
auto adl_begin(C&&c)->decltype( begin(std::forward<C>(c)) );
template<typename C>
auto adl_end(C&&c)->decltype( end(std::forward<C>(c)) );
}
template<typename C>
struct iterable_traits {
typedef decltype( adl_aux::adl_begin(std::declval<C&>()) ) iterator;
typedef decltype( adl_aux::adl_begin(std::declval<C const&>()) ) const_iterator;
};
template<typename C> using Iterator = typename iterable_traits<C>::iterator;
template<typename C> using ConstIterator = typename iterable_traits<C>::const_iterator;
template<typename I> using IteratorCategory = typename std::iterator_traits<I>::iterator_category;
template<typename C, EnableFuncIf< has_size_method<C>::value, 1>... >
std::size_t size_at_least( C&& c ) {
return c.size();
}
template<typename C, EnableFuncIf< !has_size_method<C>::value &&
std::is_base_of< std::random_access_iterator_tag, IteratorCategory<Iterator<C>> >::value, 2>... >
std::size_t size_at_least( C&& c ) {
using std::begin; using std::end;
return end(c)-begin(c);
};
template<typename C, EnableFuncIf< !has_size_method<C>::value &&
!std::is_base_of< std::random_access_iterator_tag, IteratorCategory<Iterator<C>> >::value, 3>... >
std::size_t size_at_least( C&& c ) {
return 0;
};
template < typename It >
auto try_make_move_iterator(It i, std::true_type)
-> decltype(make_move_iterator(i))
{
return make_move_iterator(i);
}
template < typename It >
It try_make_move_iterator(It i, ...)
{
return i;
}
#include <iostream>
template<typename C1, typename C2>
C1&& append_containers( C1&& c1, C2&& c2 )
{
using std::begin; using std::end;
try_reserve( c1, size_at_least(c1) + size_at_least(c2) );
using is_rvref = std::is_rvalue_reference<C2&&>;
c1.insert( end(c1),
try_make_move_iterator(begin(c2), is_rvref{}),
try_make_move_iterator(end(c2), is_rvref{}) );
return std::forward<C1>(c1);
}
struct append_infix_op {} append;
template<typename LHS>
struct append_on_right_op {
LHS lhs;
template<typename RHS>
LHS&& operator=( RHS&& rhs ) {
return append_containers( std::forward<LHS>(lhs), std::forward<RHS>(rhs) );
}
};
template<typename LHS>
append_on_right_op<LHS> operator+( LHS&& lhs, append_infix_op ) {
return { std::forward<LHS>(lhs) };
}
template<typename LHS,typename RHS>
typename std::remove_reference<LHS>::type operator+( append_on_right_op<LHS>&& lhs, RHS&& rhs ) {
typename std::decay<LHS>::type retval = std::forward<LHS>(lhs.lhs);
return append_containers( std::move(retval), std::forward<RHS>(rhs) );
}
template<typename C>
void print_container( C&& c ) {
for( auto&& x:c )
std::cout << x << ",";
std::cout << "\n";
};
int main() {
std::vector<int> a = {0,1,2};
std::vector<int> b = {3,4,5};
print_container(a);
print_container(b);
a +append= b;
const int arr[] = {6,7,8};
a +append= arr;
print_container(a);
print_container(b);
std::vector<double> d = ( std::vector<double>{-3.14, -2, -1} +append= a );
print_container(d);
std::vector<double> c = std::move(d) +append+ a;
print_container(c);
print_container(d);
std::vector<double> e = c +append+ std::move(a);
print_container(e);
print_container(a);
}
hehe.
Now with move-data-from-rhs, append-array-to-container, append forward_list-to-container, move-container-from-lhs, thanks to @DyP's help.
Note that the above does not compile in clang thanks to the EnableFunctionIf<>...
technique. In clang this workaround works.
try_reserve
part
size_at_least
? (I can only see declaration/definition, but no call..)
main
, where if you skip the code-salad above, is shockingly readable: the humor is that this is "simpler", which is far, far, far from the case. What that unreadable code-salad does is adds a named operator to the language: there is no support in C++ for named operators, so it does it via strange tricks. It is also poorly written: I have gotten better since.
If you would like to add vector to itself both popular solutions will fail:
std::vector<std::string> v, orig;
orig.push_back("first");
orig.push_back("second");
// BAD:
v = orig;
v.insert(v.end(), v.begin(), v.end());
// Now v contains: { "first", "second", "", "" }
// BAD:
v = orig;
std::copy(v.begin(), v.end(), std::back_inserter(v));
// std::bad_alloc exception is generated
// GOOD, but I can't guarantee it will work with any STL:
v = orig;
v.reserve(v.size()*2);
v.insert(v.end(), v.begin(), v.end());
// Now v contains: { "first", "second", "first", "second" }
// GOOD, but I can't guarantee it will work with any STL:
v = orig;
v.reserve(v.size()*2);
std::copy(v.begin(), v.end(), std::back_inserter(v));
// Now v contains: { "first", "second", "first", "second" }
// GOOD (best):
v = orig;
v.insert(v.end(), orig.begin(), orig.end()); // note: we use different vectors here
// Now v contains: { "first", "second", "first", "second" }
insert
must not get iterators into the container it operates on and copy
's iterators are invalidated by the insertion via back_inserter
). The two you labeled as "good" seem to work because there is no reallocation (because of your reserve
call). The last one is the way to go. Another option that would actually allow to avoid a second container would be to use resize instead of reserve and then copy the first half of the vector to the newly allocated elements.
Success story sharing
reserve
beforeinsert
?insert
must not be from the same range as the receiver object's elements, so I suppose that technically speaking it's UB.a.insert(p, i, j)
that "i and j are not iterators into a."