向向量中添加一个向量

Question

假设我有两个标准向量：

vector<int> a;
vector<int> b;

假设它们两个都有大约30个元素。

• 如何将向量b添加到向量a的末尾？

粗暴的方法是通过vector<int>::push_back()遍历b并添加每个元素，但我不想这样做！

- sub

---

我想大家都会使用迭代器来发布答案。我从未理解为什么vector没有op+=()或append()函数。 - anon

因为“insert”已经足够了？ - Andreas Brinck

“安德烈亚斯，std::string也不是同样的情况吗？当然，insert()足够用了，但在你的回答中很难看出实际上是一个向量被附加到另一个向量。a += b可以使这一点更加明显。” - anon

在我的看法中，a.append(b)（或者甚至是a+=b）比a.insert(a.end(), b.begin(), b.end())更能准确地表达意图，虽然后者在性能方面可能足够好，但阅读起来却不够简洁明了。 - sbi

@Andreas 我猜你是在提到“肥接口”问题。有些类应该具备肥接口，而在我看来字符串正是其中之一——我发现 std::string 非常好用，无论纯洁主义者如何评价。我只是认为 vector 可以增加一点体重，以方便其用户与清晰表达代码读者的意图。 - anon

Answer 1

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));

- Andreas Brinck

---

在执行insert操作之前，是否需要先进行reserve操作？ - Violet Giraffe

保留空间不是必需的，但是可能是明智的。如果你知道最终大小很大并且需要多次向向量中插入元素，使用保留空间是明智的选择。否则，最好让STL根据需要动态增加向量的大小。 - moodboom

如果尝试将向量附加到自身，则此解决方案将失败。它会生成大小正确的向量，但添加空元素而不是原始元素。只有在使用v.reserve(v.size()*2)进行预分配之后才能开始工作（但这可能取决于STL实现）。 - Sergey

我认为标准特别指出传递给insert的迭代器不能来自于接收对象元素的相同范围，所以严格来说这是未定义行为。 - templatetypedef

在我的C++14标准草案中，第100表（序列容器要求）将调用a.insert(p, i, j)的前提条件列为“i和j不是指向a的迭代器”。请注意，这里涉及到的是C++编程语言的标准。 - templatetypedef

Answer 2

std::copy (b.begin(), b.end(), std::back_inserter(a));

如果向量a中的项没有赋值运算符（例如const成员），则可以使用此方法。

在所有其他情况下，与上述插入解决方案相比，此解决方案效率低下。

- user184968

---

注意，与使用std::vector<>::insert()相比，这种方法可能效率较低，因为std::copy()不能预先保留足够的空间（它只有访问迭代器的权限，而没有访问向量本身的权限），而std::vector<>::insert()则可以（作为成员函数）。（为了预先计算序列的长度，它需要确定要读取的迭代器是随机访问迭代器，但不这样做的实现将是薄弱的。） - sbi

实际上是正确的，但在理论上，“std::”实现者可以使之工作。他们可以在内部使用非标准扩展。 - MSalters

我知道一种实现方法可能会这样做。这就是为什么我写它“可能不太高效”的原因。理论上，一个实现者可以向std::back_inserter_iterator<std::vector<T>>添加一个私有接口，以使std::copy()的实现能够识别它并使用此私有接口来获取std::vector并调用其上的reserve()。然而，在实践中，很少有实现者费劲心思优化这种角落情况的可能性。 - sbi

@sbi的批评是正确的，至少对于libstdc++而言。使用std::copy确实比使用std::vector::insert更慢。我刚刚在g++ 4.4.5附带的libstdc++上进行了测试。 - Marc Claesen

@Sergey，尝试将向量附加到自身是未定义行为：https://dev59.com/BGUq5IYBdhLWcg3wF8rw - user184968

Answer 3

在说“编译器可以保留”时，为什么要依赖它呢？自动检测移动语义怎么样？所有这些重复的容器名称和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中上述内容无法编译。在clang中，这个解决方法有效。

- Yakk - Adam Nevraumont

---

我认为你可以简化这个，例如 try_reserve 部分。 - dyp

只添加了"insert-by-move"。 - dyp

使用这种语言的方法是什么？ - Rag

你知道上面的帖子几乎是一个笑话吗？C++有一个完全可图灵编译时子语言，充分利用它往往会创建出只能被写作者理解的代码。这个笑话的关键在于main函数，如果你跳过上面那段混沌代码，你会发现它令人惊讶地易读：这就是幽默所在，“简洁”远非如此。那些难以理解的代码混沌做的事情是向语言中添加了一个命名运算符：C++不支持命名运算符，所以使用了一些奇怪的技巧实现。那段代码也写得不好：我现在已经进步了。 - Yakk - Adam Nevraumont

http://orig05.deviantart.net/07ee/f/2012/132/c/f/the_horror_you_gais_by_ask_salad_fingers-d4zj0jc.png - user2962533

Answer 4

如果您想将向量添加到其自身，那么两种常见的解决方案都会失败：

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" }

- Sergey

---

除了最后一个建议以外，其他所有的建议都是错误的，如其他帖子所述（insert不能获取其操作容器的迭代器，而copy的迭代器会因通过back_inserter进行插入而失效）。你标记为“好”的两个建议之所以有效，是因为没有重新分配空间（因为你调用了reserve函数）。最后一个建议是正确的方法。另一个实际上可以避免使用第二个容器的选项是使用resize而不是reserve，然后将向量的前一半复制到新分配的元素中。 - Nobody moving away from SE