Добавление вектора к вектору

Предполагая, что у меня есть 2 стандартных вектора:

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

Также предположим, что у обоих есть около 30 элементов.

  • Как мне добавить вектор b в конец вектора a?

Грязным способом будет итерация через b и добавление каждого элемента через vector<int>::push_back(), хотя я бы не хотел этого делать!


person sub    schedule 31.03.2010    source источник
comment
Думаю, все будут публиковать ответы с помощью итераторов. Я никогда не понимал, почему у вектора нет функции op + = () или append ().   -  person    schedule 31.03.2010
comment
@Neil Потому что insert достаточно?   -  person Andreas Brinck    schedule 31.03.2010
comment
@Andreas Ну, разве нельзя сказать то же самое о std :: string? Конечно, insert () достаточно, но в вашем ответе далеко не очевидно, что на самом деле происходит добавление одного вектора к другому. a + = b делает это прозрачным.   -  person    schedule 31.03.2010
comment
@Andreas: С точки зрения производительности этого может быть достаточно, но его не так легко читать. IMO a.append(b) (или даже a+=b) уловил бы намерение намного лучше, чем a.insert(a.end(), b.begin(), b.end()).   -  person sbi    schedule 31.03.2010
comment
Может быть, кто-нибудь в один прекрасный день добавит функцию добавления в векторный шаблон :)   -  person sub    schedule 31.03.2010
comment
@Neil std::string многие считают эффектным дизайнерским провалом. Нет необходимости добавлять append функцию в vector, если она вам действительно нужна, вы можете написать свою собственную версию как бесплатную функцию.   -  person Andreas Brinck    schedule 31.03.2010
comment
@Neil Цитирует Херба Саттера и Андрея Александреску: std::basic_string - столь же печально известный пример монолитного дизайна классов ...   -  person Andreas Brinck    schedule 31.03.2010
comment
@Andreas Я так понимаю, вы имеете в виду проблему с толстым интерфейсом. Некоторые классы должны иметь толстые интерфейсы, и строки IMHO являются одним из них - я считаю, что std :: string очень удобно использовать, что бы ни говорили пуристы. Я просто думаю, что с этим вектором можно было бы немного прибавить веса, чтобы облегчить жизнь его пользователям и сделать их код более понятным для читателей.   -  person    schedule 31.03.2010
comment
Тот же вопрос для списка: stackoverflow.com/questions/2349098 / c-connected-list-behavior / и, что интересно, те же ответы :-)   -  person Arun    schedule 01.04.2010
comment
@ Нил: Я был с вами на std::vector<T>::append(), и я был с вами на +=, пока не увидел stackoverflow.com/questions/2552839/ 2553683 # 2553683.   -  person sbi    schedule 02.04.2010
comment
На мой взгляд, проблема с operator+() в том, что он подразумевает (хотя и неявно) операцию O (1). Да, у струнных есть это, но у струнных также есть знаменитая ловушка злоупотребления operator+(). Это проблема, и мне нравится подход C ++, который усложняет вам написание неэффективного кода.   -  person wilhelmtell    schedule 21.04.2010
comment
Мне кажется, что многие вещи в stdlib C ++ могут использовать некоторый TLC с точки зрения именования и удобства использования. Я бы полностью поддержал функцию append (), даже если она не сэкономит много времени при вводе кода, при чтении кода она станет более понятной.   -  person Ibrahim    schedule 02.11.2012
comment
Как насчет того, чтобы перейти к Перли и отменить добавление operator.?   -  person John    schedule 31.05.2013
comment
@John operator. не может быть отменен.   -  person Yakk - Adam Nevraumont    schedule 31.05.2013
comment
@anon Цель дизайна - быть универсальной (также известной как независимая от типа данных). Если + поддерживается, то это, вероятно, будет реализовано с использованием +, определенного для типа данных. Это наложило бы большое ограничение на типы данных, которые можно использовать с вектором.   -  person qqqqq    schedule 15.01.2016
comment
@AndreasBrinck Assembly также подходит для любой задачи программирования; это также очень быстро. Это не значит, что им легко пользоваться или даже читать.   -  person Alex Quilliam    schedule 19.03.2018
comment
каждый может просто повторно реализовать базовую, часто используемую функциональность сотни раз - что за классический взгляд на удобство использования «парнем из C ++».   -  person mackenir    schedule 26.06.2019
comment
Для тех, кто бегло просмотрел последний комментарий sbi выше, a+=b можно интерпретировать как поэлементное добавление-присваивание, особенно для тех, кто знаком с библиотеками линейной алгебры, имеющими дело с чем-то, называемым vector (одномерная матрица в математических терминах).   -  person Emile Cormier    schedule 16.02.2020
comment
Есть еще одна проблема (особенно когда дело доходит до читаемости кода: если я пытаюсь добавить вектор, возвращаемый какой-либо функцией, к существующему вектору, мне придется добавить строку для сохранения вектора перед вызовом вставки. Вероятно, то же самое с точки зрения производительности, но определенно менее читабельный.   -  person PixelArtDragon    schedule 23.07.2020


Ответы (4)


a.insert(a.end(), b.begin(), b.end());

or

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));
person Andreas Brinck    schedule 31.03.2010
comment
Мне нужно reserve перед insert? - person Violet Giraffe; 14.08.2013
comment
@VioletGiraffe резерв не требуется, но может быть рекомендован. Разумно использовать резерв, если вы многократно вставляете в вектор, для которого известен окончательный размер, и этот размер большой. В противном случае я бы позволил STL увеличивать ваш вектор по мере необходимости. - person moodboom; 10.09.2013
comment
Это решение не сработает, если вы попытаетесь добавить вектор к самому себе. Он генерирует вектор правильного размера, но добавляет пустые элементы вместо исходных. И он начинает работать, только если вы добавите его с помощью v.reserve (v.size () * 2); (но это может зависеть от реализации STL) - person Sergey; 14.11.2013
comment
@Sergey Я считаю, что в стандарте прямо говорится, что итераторы, данные insert, не должны быть из того же диапазона, что и элементы объекта-получателя, поэтому я полагаю, что технически это UB. - person templatetypedef; 31.01.2014
comment
@sergey хуже этого - итератор end, который вы передаете для конца диапазона vector, становится недействительным при вставке, даже если вы зарезервировали его первым (поскольку он находится в точке вставки или после нее, что делает его недействительным). В режиме отладки std::vector это может быть обнаружено (в большинстве выпусков этого не происходит, и они просто будут работать). - person Yakk - Adam Nevraumont; 30.10.2014
comment
@templatetypedef у вас есть ссылка на это? Обходной путь, о котором я знаю, все еще может вызвать проблемы. - person Yakk - Adam Nevraumont; 30.10.2014
comment
@Yakk В моем проекте стандарта C ++ 14 в таблице 100 (Требования к контейнеру последовательности) в качестве предварительного условия для вызова a.insert(p, i, j) указано, что i и j не являются итераторами в. - person templatetypedef; 30.10.2014
comment
@moodboom оболочка не использует резерв перед одиночной вставкой, если это не последняя вставка. В большинстве реализаций vector :: reserve не увеличивает векторный буфер экспоненциально, он устанавливает размер буфера равным точному количеству зарезервированных вами элементов. Так, например, серия резервных вызовов (size () + 1) имеет квадратичную сложность - person ZAB; 05.03.2015
comment
@ZAB Если вы говорите, что множественные вызовы резервирования - это сомнительная практика, я согласен, и вы должны позволить библиотеке увеличивать вектор по мере необходимости. Вот почему я сказал использовать его (один раз), если вы знаете желаемый окончательный размер. Но это то, что вы говорите? :-) - person moodboom; 06.03.2015
comment
@Sergey, я действительно не знаю эту абривиацию UB - не могли бы вы уточнить, что: это UB. - означает - person serup; 24.01.2017
comment
@serup «UB» относится к неопределенному поведению. en.cppreference.com/w/cpp/language/ub - person cgmb; 24.03.2017

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

Это можно использовать в случае, если элементы в векторе a не имеют оператора присваивания (например, константный член).

Во всех других случаях этот раствор неэффективен по сравнению с указанным выше раствором вставки.

person Community    schedule 31.03.2010
comment
Обратите внимание, что это, вероятно, будет менее эффективно, чем использование std::vector<>::insert(), потому что std::copy() не может заранее зарезервировать достаточно места (у него нет доступа к самому вектору, только к итератору, который имеет), в то время как std::vector<>::insert(), будучи членом функция, может. (Необходимо выяснить, что итераторы для чтения являются итераторами с произвольным доступом, чтобы предварительно вычислить длину последовательности, но это будет слабая реализация, которая бы этого не сделала.) - person sbi; 31.03.2010
comment
На практике это так, но теоретически std:: разработчик может заставить это работать. Они могут использовать нестандартные расширения внутри. - person MSalters; 31.03.2010
comment
@MSalter: Я знаю, что реализация может сделать это. Вот почему я написал, что он, вероятно, будет менее эффективным. Теоретически разработчик может добавить частный интерфейс к std::back_inserter_iterator<std::vector<T>>, чтобы позволить реализации std::copy() распознать его и использовать этот частный интерфейс для получения std::vector и вызова reserve() на нем. На практике, однако, маловероятно, что кто-либо из разработчиков перескочит через все эти препятствия, чтобы оптимизировать такой угловой случай. - person sbi; 31.03.2010
comment
Критика @sbi верна, по крайней мере, для libstdc ++. std::copy действительно медленнее, чем при использовании std::vector::insert. Я только что протестировал его с помощью libstdc ++, которая идет с g ++ 4.4.5. - person Marc Claesen; 31.05.2013
comment
Это решение генерирует исключение std :: bad_alloc, если вы пытаетесь добавить вектор к самому себе. Но он начинает работать, если вы добавляете его с помощью v.reserve (v.size () * 2); (но это может зависеть от реализации STL) - person Sergey; 14.11.2013
comment
@Sergey, попытка добавить вектор к самому себе - это UB: stackoverflow.com/questions/14791984/ - person ; 14.11.2013
comment
Это также работает, если элементы вектора могут быть построены, но не могут быть присвоены. (например, они содержат нестатические const элементы данных) - person ManuelAtWork; 18.09.2017

Когда говорят «компилятор может зарезервировать», зачем на это полагаться? А как насчет автоматического определения семантики хода? А как насчет всего этого повторения имени контейнера с begins и ends?

Разве вы не хотели бы чего-нибудь попроще?

(Прокрутите вниз до 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);
}

хе-хе.

Теперь с помощью move-data-from-rhs, append-array-to-container, append-forward_list-to-container, move-container-from-lhs, благодаря помощи @DyP.

Обратите внимание, что приведенное выше не компилируется в clang благодаря технике EnableFunctionIf<>.... В clang это временное решение работает.

person Yakk - Adam Nevraumont    schedule 30.05.2013
comment
Я думаю, вы можете упростить это, например try_reserve часть - person dyp; 31.05.2013
comment
Где вы используете size_at_least? (Я вижу только декларацию / определение, но не звоню ..) - person dyp; 31.05.2013
comment
Добавлен только insert-by-move - person dyp; 31.05.2013
comment
@dyp Предполагается, что он находится в резервном вызове, поэтому мы можем добавлять списки к векторам. На телефоне не до редактирования. Исправлю позже. - person Yakk - Adam Nevraumont; 31.05.2013
comment
@DyP Я имею в виду, я хочу, чтобы он поддерживал необработанные массивы C, которые имеют итераторы с произвольным доступом, но не имеют size и forward_lists (без эффективного способа создания size) и диапазоны прямых итераторов. Ваша пошаговая вставка не компилируется, если RHS является const контейнером. - person Yakk - Adam Nevraumont; 31.05.2013
comment
Вы проверяли, что он не компилируется? Когда вы комментируете try_reserve, он отлично работает с const int arr[] = {6,7,8}; a +append= std::move(arr); Конечно, size_at_least нужно добавить, чтобы исправить try_reserve часть. Однако, вероятно, произойдет сбой, если тип не перемещается (например, удаленное присвоение перемещения). Это просто исправить. - person dyp; 31.05.2013
comment
@DyP а, нет, я просто предположил, что make_move_iterator не будет работать с const_iterator. Ба, мой EnableFunctionIf трюк не компилируется на clang (я не уверен, что clang прав и в этой неудачной компиляции) - person Yakk - Adam Nevraumont; 31.05.2013
comment
Как кто-нибудь использует этот язык - person Brian Gordon; 04.02.2014
comment
@BrainGordon Вы знаете, что этот пост в значительной степени шутка? В C ++ есть подъязык времени компиляции с полным по Тьюрингу, использование его в полной мере нередко приводит к созданию кода, доступного только для записи. Изюминка шутки находится в main, где, если вы пропустите приведенный выше код-салат, он шокирует читаемость: юмор в том, что это проще, что далеко, далеко, далеко не так. Этот нечитаемый кодовый салат добавляет к языку именованный оператор: в C ++ нет поддержки именованных операторов, поэтому он делает это с помощью странных уловок. Также плохо написано: с тех пор мне стало лучше. - person Yakk - Adam Nevraumont; 04.02.2014

Если вы захотите добавить вектор к самому себе, оба популярных решения потерпят неудачу:

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" }
person Sergey    schedule 14.11.2013
comment
За исключением последнего, все ваши предложения неверны, как указано в других сообщениях (insert не должен помещать итераторы в контейнер, в котором он работает, и итераторы copy становятся недействительными при вставке через back_inserter). Два, которые вы отметили как хорошие, похоже, работают, потому что перераспределения нет (из-за вашего reserve вызова). Последний вариант - это то, что нужно. Другой вариант, который фактически позволил бы избежать второго контейнера, - это использовать изменение размера вместо резерва, а затем скопировать первую половину вектора во вновь выделенные элементы. - person Nobody moving away from SE; 26.11.2014