这个问题在这里已经有了答案: Concatenating two std::vectors (27 answers) 7年前关闭。
假设我有 2 个标准向量:
vector<int> a;
vector<int> b;
假设两者都有大约 30 个元素。
如何将向量 b 添加到向量 a 的末尾?
肮脏的方法是遍历 b 并通过 vector<int>::push_back()
添加每个元素,尽管我不想这样做!
insert
就足够了吗?
a.append(b)
(甚至 a+=b
)会比 a.insert(a.end(), b.begin(), b.end())
更好地捕捉意图。
a.insert(a.end(), b.begin(), b.end());
或者
a.insert(std::end(a), std::begin(b), std::end(b));
第二个变体是更通用的解决方案,因为 b
也可以是一个数组。但是,它需要 C++11。如果要使用用户定义的类型,请使用 ADL:
using std::begin, std::end;
a.insert(end(a), begin(b), end(b));
std::copy (b.begin(), b.end(), std::back_inserter(a));
这可以用于向量 a 中的项目没有赋值运算符(例如 const 成员)的情况。
在所有其他情况下,与上述插入解决方案相比,该解决方案效率低下。
std::vector<>::insert()
效率低,因为 std::copy()
无法预先预留足够的空间(它无法访问向量本身,只能访问具有的迭代器),而 { 1},作为成员函数,可以。 (它需要弄清楚要读取的迭代器是随机访问迭代器,以便预先计算序列的长度,但这将是一个弱实现,不会这样做。)
std::
实现者可以使其工作。他们可以在内部使用非标准扩展。
std::back_inserter_iterator<std::vector<T>>
以允许 std::copy()
的实现识别它并使用此私有接口来获取 std::vector
并在其上调用 reserve()
。然而,在实践中,任何实现者都不太可能跳过所有这些障碍来优化这种极端情况。
std::copy
确实比使用 std::vector::insert
慢。我刚刚使用 g++ 4.4.5 附带的 libstdc++ 对其进行了测试。
虽然说“编译器可以保留”,但为什么要依赖它呢?那么移动语义的自动检测呢?那么容器名称与 begin
和 end
的所有重复呢?
你不想要一些更简单的东西吗?
(向下滚动到 main
以查看妙语)
#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。
现在有了 move-data-from-rhs、append-array-to-container、append forward_list-to-container、move-container-from-lhs,感谢 @DyP 的帮助。
请注意,由于使用了 EnableFunctionIf<>...
技术,上面的代码不会在 clang 中编译。在铿锵this workaround作品。
try_reserve
part
size_at_least
? (我只能看到声明/定义,但没有调用..)
main
中,如果你跳过上面的代码沙拉,它的可读性令人震惊:幽默是这“更简单”,这与案例相去甚远。不可读的代码沙拉所做的是向语言添加命名运算符:C++ 中不支持命名运算符,因此它通过奇怪的技巧来实现。它也写得不好:从那以后我变得更好了。
如果您想将向量添加到自身,两种流行的解决方案都将失败:
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
不得将迭代器放入它所操作的容器中,并且 copy
的迭代器因通过 back_inserter
的插入而失效)。您标记为“好”的两个似乎有效,因为没有重新分配(因为您的 reserve
调用)。最后一个是要走的路。实际上允许避免第二个容器的另一个选项是使用调整大小而不是保留,然后将向量的前半部分复制到新分配的元素。
不定期副业成功案例分享
insert
之前reserve
吗?insert
的迭代器不能与接收器对象的元素在同一范围内,所以我认为从技术上讲它是UB。a.insert(p, i, j)
的先决条件列出了“i 和 j 不是 a 的迭代器”。