Конкатенация двух стандартных: векторов

688

Как мне соединить два std::vectorс?

emlai
источник
5
Приведенные ответы на самом деле не объединяются. Они добавляют копию. Может быть использование (с точки зрения эффективности) для создания метода конкатенации std :: vector, однако это потребует некоторого сложного совместного использования управления узлами, и, вероятно, поэтому это не было сделано.
FauChristian
8
@FauChristian: Нет, с точки зрения эффективности не может быть пользы. Векторная память должна быть непрерывной, поэтому то, что вы предлагаете, невозможно. Если вы хотите «некоторого сложного совместного использования управления узлами», и если вы хотите изменить векторный класс таким образом, вы получите деку. Даже тогда очень сложно повторно использовать память предложенным способом, хотя она стала бы немного более выполнимой. Я не думаю, что это в настоящее время реализовано. Главное, что при таком совместном использовании узлов управления (deque) конечный узел может быть частично пустым.
Cookie
4
@lecaruyer Вы понимаете, что только что отметили вопрос, который был задан за два года до того, как дубликат
eshirima
9
Я один задаюсь вопросом, почему это не реализовано как a + bили a.concat(b)в стандартной библиотеке? Может быть, реализация по умолчанию будет неоптимальной, но объединение каждого массива не нуждается в
микрооптимизации
10
годы эволюции, самая совершенная перегрузка операторов из любого основного языка, система шаблонов, которая удваивает сложность языка, и все же ответ не v = v1 + v2;
Spike0xff

Ответы:

729
vector1.insert( vector1.end(), vector2.begin(), vector2.end() );
Роберт Гэмбл
источник
53
Я бы добавил код только для того, чтобы сначала получить количество элементов, содержащихся в каждом векторе, и установить вектор1 как самый большой. Если вы делаете иначе, вы делаете много ненужного копирования.
Джо Пинеда
34
У меня вопрос. Будет ли это работать, если vector1 и vector2 одинаковые векторы?
Александр Рафферти
6
Если вы объединяете несколько векторов в один, полезно ли reserveсначала вызывать вектор назначения?
Фахим Митха
33
@AlexanderRafferty: Только если vector1.capacity() >= 2 * vector1.size(). Что нетипично, если вы не позвонили std::vector::reserve(). В противном случае вектор будет перераспределен, делая недействительными итераторы, переданные в качестве параметров 2 и 3.
Дрю Дорманн
28
Жаль, что в стандартной библиотеке нет более краткого выражения. .concatили +=или что - то
мр
194

Если вы используете C ++ 11 и хотите перемещать элементы, а не просто копировать их, вы можете использовать std::move_iterator вместе со insert (или copy):

#include <vector>
#include <iostream>
#include <iterator>

int main(int argc, char** argv) {
  std::vector<int> dest{1,2,3,4,5};
  std::vector<int> src{6,7,8,9,10};

  // Move elements from src to dest.
  // src is left in undefined but safe-to-destruct state.
  dest.insert(
      dest.end(),
      std::make_move_iterator(src.begin()),
      std::make_move_iterator(src.end())
    );

  // Print out concatenated vector.
  std::copy(
      dest.begin(),
      dest.end(),
      std::ostream_iterator<int>(std::cout, "\n")
    );

  return 0;
}

Это не будет более эффективным для примера с целыми числами, поскольку их перемещение не более эффективно, чем их копирование, но для структуры данных с оптимизированными перемещениями можно избежать копирования ненужного состояния:

#include <vector>
#include <iostream>
#include <iterator>

int main(int argc, char** argv) {
  std::vector<std::vector<int>> dest{{1,2,3,4,5}, {3,4}};
  std::vector<std::vector<int>> src{{6,7,8,9,10}};

  // Move elements from src to dest.
  // src is left in undefined but safe-to-destruct state.
  dest.insert(
      dest.end(),
      std::make_move_iterator(src.begin()),
      std::make_move_iterator(src.end())
    );

  return 0;
}

После перемещения элемент src остается в неопределенном, но безопасном для уничтожения состоянии, а его прежние элементы были переданы непосредственно новому элементу dest в конце.

Alex
источник
6
Метод std :: make_move_iterator () помог мне при попытке объединить std :: vectors из std :: unique_ptr.
Knitschi
Какая разница между этим и std::move(src.begin(), src.end(), back_inserter(dest))?
кшеной
77

Или вы можете использовать:

std::copy(source.begin(), source.end(), std::back_inserter(destination));

Этот шаблон полезен, если два вектора не содержат абсолютно одинаковую вещь, потому что вы можете использовать что-то вместо std :: back_inserter для преобразования из одного типа в другой.

Роджер Липскомб
источник
7
метод копирования не очень хороший способ. Он будет вызывать push_back несколько раз, что означает, что если нужно вставить много элементов, это может означать многократное перераспределение. лучше использовать вставку, поскольку реализация вектора могла бы сделать некоторую оптимизацию, чтобы избежать перераспределений. он может зарезервировать память перед началом копирования
Йогеш Арора
7
@Yogesh: само собой разумеющееся, но ничто не мешает вам позвонить reserveпервым. Причина std::copyиногда полезна, если вы хотите использовать что-то другое back_inserter.
Роджер Липскомб
Когда вы говорите «множественные распределения», это правда - но количество распределений в худшем случае (количество добавленных записей) - это означает, что стоимость добавления записи постоянна в количестве добавленных записей. (По сути, не беспокойтесь об этом, если профилирование не показывает, что вам нужен резерв).
Мартин Боннер поддерживает Монику
Возможно, вы захотите использовать std :: transform для этого.
Мартин Бродхерст
1
копия много отстой, даже с запасом. vector :: insert позволит избежать всех проверок: quick-bench.com/bLJO4OfkAzMcWia7Pa80ynwmAIA
Денис Ярошевский
63

В C ++ 11 я бы предпочел добавить вектор b к a:

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

когда a и bне перекрываются, и bбольше не будут использоваться.


Это std::moveиз <algorithm>, а не обычный std::move с <utility>.

Дэцин
источник
10
Неопределенное поведение, если a на самом деле - b (что нормально, если вы знаете, что этого никогда не произойдет, но стоит знать об этом в коде общего назначения).
Мартин Боннер поддерживает Монику
1
@MartinBonner Спасибо за упоминание этого. Возможно, мне следует вернуться к старому insert, более безопасному способу.
Deqing
15
Ах, ДРУГОЙ std :: move. Весьма сбивает с толку первый раз, когда вы видите это.
xaxxon
1
Это отличается от insert()с move_iteratorс? Если так, то как?
GPhilo
1
Я добавил примечание о том, что std::moveмы здесь говорим, так как большинство людей не знают этой перегрузки. Надеюсь, это улучшение.
YSC
38
std::vector<int> first;
std::vector<int> second;

first.insert(first.end(), second.begin(), second.end());
Джеймс Керран
источник
24

Я предпочитаю тот, который уже упоминался:

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

Но если вы используете C ++ 11, есть еще один общий способ:

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

Кроме того, не является частью вопроса, но желательно использовать reserveперед добавлением для повышения производительности. И если вы соединяете вектор с самим собой, без резервирования он не удастся, так что вам всегда следует reserve.


Итак, в основном то, что вам нужно:

template <typename T>
void Append(std::vector<T>& a, const std::vector<T>& b)
{
    a.reserve(a.size() + b.size());
    a.insert(a.end(), b.begin(), b.end());
}
ST3
источник
2
std::выводится через аргумент-зависимый поиск . end(a)будет достаточно.
Асу
4
@Asu ADL будет добавляться только в том std::случае, если от него aпоступает тип std, который игнорирует общий аспект.
Potatoswatter
хорошая точка зрения. в данном случае это вектор, так что он будет работать в любом случае, но да, это лучшее решение.
Асу
std :: begin () / end () были добавлены для коллекций (таких как массивы), которые не имеют их в качестве функций-членов. Но массивы также не имеют функции-члена insert () и вызывают вопрос «Существует ли коллекция с insert (), но без begin () (которая работает с std :: begin ())?»
Джеймс Керран
12

Вы должны использовать vector :: insert

v1.insert(v1.end(), v2.begin(), v2.end());
Борис
источник
3
Разве это не то же самое с ответом Тома Риттера и Роберта Гэмбла в 2008 году?
IgNite
9

Общий прирост производительности для СЦЕПИТЬ, чтобы проверить размер векторов. И объединить / вставить меньший с большим.

//vector<int> v1,v2;
if(v1.size()>v2.size()) {
    v1.insert(v1.end(),v2.begin(),v2.end());
} else {
    v2.insert(v2.end(),v1.begin(),v1.end());
}
Викрамджит Рой
источник
Так просто, но я никогда не думал об этом таким образом!
Зимано
2
Пример кода неверен. v1.insert(v2.end()...использует итератор в, v2чтобы указать позицию в v1.
Дэвид Стоун
Вы также можете использовать быстрый обмен. @DavidStone Я отредактировал его, чтобы можно было изменить порядок конкатов. Можно ли добавить в начало вектора?
QWR
Вы можете вставить в начало, но это будет медленнее. Однако для истинного «объединения» порядок обычно имеет значение, и это то, что вам нужно сделать.
Дэвид Стоун
7

Если вы хотите иметь возможность краткого объединения векторов, вы можете перегрузить +=оператор.

template <typename T>
std::vector<T>& operator +=(std::vector<T>& vector1, const std::vector<T>& vector2) {
    vector1.insert(vector1.end(), vector2.begin(), vector2.end());
    return vector1;
}

Тогда вы можете назвать это так:

vector1 += vector2;
Дэниел Гигер
источник
6

Если вы заинтересованы в строгой гарантии исключения (когда конструктор копирования может выдать исключение):

template<typename T>
inline void append_copy(std::vector<T>& v1, const std::vector<T>& v2)
{
    const auto orig_v1_size = v1.size();
    v1.reserve(orig_v1_size + v2.size());
    try
    {
        v1.insert(v1.end(), v2.begin(), v2.end());
    }
    catch(...)
    {
        v1.erase(v1.begin() + orig_v1_size, v1.end());
        throw;
    }
}

Подобное append_moveсо строгой гарантией не может быть реализовано вообще, если конструктор перемещения векторного элемента может бросить (что маловероятно, но все же).

AlexT
источник
Разве не возможно v1.erase(...бросить тоже?
Класс Скелет
insertуже справляется с этим. Кроме того, этот вызов eraseэквивалентен resize.
Potatoswatter
Мне это нравится - спасибо!
натерсоз
5

Добавьте это в свой заголовочный файл:

template <typename T> vector<T> concat(vector<T> &a, vector<T> &b) {
    vector<T> ret = vector<T>();
    copy(a.begin(), a.end(), back_inserter(ret));
    copy(b.begin(), b.end(), back_inserter(ret));
    return ret;
}

и используйте это так:

vector<int> a = vector<int>();
vector<int> b = vector<int>();

a.push_back(1);
a.push_back(2);
b.push_back(62);

vector<int> r = concat(a, b);

r будет содержать [1,2,62]

Степан Яковенко
источник
Не знаю, почему за это проголосовали. Возможно, это не самый эффективный способ сделать это, но это не так и эффективно.
leeor_net
4

Вот решение общего назначения с использованием семантики перемещения C ++ 11:

template <typename T>
std::vector<T> concat(const std::vector<T>& lhs, const std::vector<T>& rhs)
{
    if (lhs.empty()) return rhs;
    if (rhs.empty()) return lhs;
    std::vector<T> result {};
    result.reserve(lhs.size() + rhs.size());
    result.insert(result.cend(), lhs.cbegin(), lhs.cend());
    result.insert(result.cend(), rhs.cbegin(), rhs.cend());
    return result;
}

template <typename T>
std::vector<T> concat(std::vector<T>&& lhs, const std::vector<T>& rhs)
{
    lhs.insert(lhs.cend(), rhs.cbegin(), rhs.cend());
    return std::move(lhs);
}

template <typename T>
std::vector<T> concat(const std::vector<T>& lhs, std::vector<T>&& rhs)
{
    rhs.insert(rhs.cbegin(), lhs.cbegin(), lhs.cend());
    return std::move(rhs);
}

template <typename T>
std::vector<T> concat(std::vector<T>&& lhs, std::vector<T>&& rhs)
{
    if (lhs.empty()) return std::move(rhs);
    lhs.insert(lhs.cend(), std::make_move_iterator(rhs.begin()), std::make_move_iterator(rhs.end()));
    return std::move(lhs);
}

Обратите внимание, как это отличается от appendв vector.

Даниил
источник
4

Вы можете подготовить свой собственный шаблон для оператора +:

template <typename T> 
inline T operator+(const T & a, const T & b)
{
    T res = a;
    res.insert(res.end(), b.begin(), b.end());
    return res;
}

Следующая вещь - просто используйте +:

vector<int> a{1, 2, 3, 4};
vector<int> b{5, 6, 7, 8};
for (auto x: a + b)
    cout << x << " ";
cout << endl;

Этот пример дает вывод:

1 2 3 4 5 6 7 8
Владимир У.
источник
3
Использование T operator+(const T & a, const T & b)опасно, лучше использовать vector<T> operator+(const vector<T> & a, const vector<T> & b).
Матье H
4

Есть алгоритм std::mergeиз C ++ 17 , который очень прост в использовании,

Ниже приведен пример:

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    //DATA
    std::vector<int> v1{2,4,6,8};
    std::vector<int> v2{12,14,16,18};

    //MERGE
    std::vector<int> dst;
    std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(dst));

    //PRINT
    for(auto item:dst)
        std::cout<<item<<" ";

    return 0;
}
Паван Чандака
источник
3
Я не думаю, что это легче использовать, чем std::vector::insert, но это делает что-то другое: объединение двух диапазонов в новый диапазон против вставки одного вектора в конце другого. Стоит упомянуть в ответе?
ДБ
4

Если ваша цель состоит в том, чтобы просто перебрать диапазон значений для целей только для чтения, альтернативой является обтекание обоих векторов вокруг прокси (O (1)) вместо их копирования (O (n)), чтобы их можно было быстро увидеть как единый, непрерывный.

std::vector<int> A{ 1, 2, 3, 4, 5};
std::vector<int> B{ 10, 20, 30 };

VecProxy<int> AB(A, B);  // ----> O(1)!

for (size_t i = 0; i < AB.size(); i++)
    std::cout << AB[i] << " ";  // ----> 1 2 3 4 5 10 20 30

Обратитесь к https://stackoverflow.com/a/55838758/2379625 для получения более подробной информации, включая реализацию VecProxy, а также плюсы и минусы.

Рональд Соуза
источник
3
vector<int> v1 = {1, 2, 3, 4, 5};
vector<int> v2 = {11, 12, 13, 14, 15};
copy(v2.begin(), v2.end(), back_inserter(v1));
пример
источник
6
Хотя этот фрагмент кода может решить проблему, он не объясняет, почему и как он отвечает на вопрос. Пожалуйста, включите объяснение вашего кода , так как это действительно помогает улучшить качество вашего сообщения. Флаггеры / рецензенты: для ответов только с кодом, таких как этот, downvote, не удаляйте! (Примечание: этот ответ на самом деле может быть достаточно простым, чтобы дать объяснение, и, следовательно, понизить голосование, излишне. Вы все еще можете добавить объяснение, чтобы предотвратить больше флагов NAA / VLQ.)
Скотт Уэлдон
2

Я реализовал эту функцию, которая объединяет любое количество контейнеров, переходя от rvalue-ссылок и копируя иначе

namespace internal {

// Implementation detail of Concatenate, appends to a pre-reserved vector, copying or moving if
// appropriate
template<typename Target, typename Head, typename... Tail>
void AppendNoReserve(Target* target, Head&& head, Tail&&... tail) {
    // Currently, require each homogenous inputs. If there is demand, we could probably implement a
    // version that outputs a vector whose value_type is the common_type of all the containers
    // passed to it, and call it ConvertingConcatenate.
    static_assert(
            std::is_same_v<
                    typename std::decay_t<Target>::value_type,
                    typename std::decay_t<Head>::value_type>,
            "Concatenate requires each container passed to it to have the same value_type");
    if constexpr (std::is_lvalue_reference_v<Head>) {
        std::copy(head.begin(), head.end(), std::back_inserter(*target));
    } else {
        std::move(head.begin(), head.end(), std::back_inserter(*target));
    }
    if constexpr (sizeof...(Tail) > 0) {
        AppendNoReserve(target, std::forward<Tail>(tail)...);
    }
}

template<typename Head, typename... Tail>
size_t TotalSize(const Head& head, const Tail&... tail) {
    if constexpr (sizeof...(Tail) > 0) {
        return head.size() + TotalSize(tail...);
    } else {
        return head.size();
    }
}

}  // namespace internal

/// Concatenate the provided containers into a single vector. Moves from rvalue references, copies
/// otherwise.
template<typename Head, typename... Tail>
auto Concatenate(Head&& head, Tail&&... tail) {
    size_t totalSize = internal::TotalSize(head, tail...);
    std::vector<typename std::decay_t<Head>::value_type> result;
    result.reserve(totalSize);
    internal::AppendNoReserve(&result, std::forward<Head>(head), std::forward<Tail>(tail)...);
    return result;
}
Нарисовалась
источник
1

Если то, что вы ищете, - это способ добавить вектор к другому после создания, то vector::insertэто ваша лучшая ставка, на которую уже отвечали несколько раз, например:

vector<int> first = {13};
const vector<int> second = {42};

first.insert(first.end(), second.cbegin(), second.cend());

К сожалению, нет способа построить const vector<int>, как выше, вы должны построить, а затем insert.


Если то, что вы на самом деле ищете, является контейнером для объединения этих двух элементов vector<int>, вам может быть доступно что-то лучше, если:

  1. Ваш vector содержит примитивы
  2. Ваши содержащиеся примитивы имеют размер 32 бита или меньше
  3. Вы хотите constконтейнер

Если все вышеприведенное верно, я бы предложил использовать тот, basic_stringкто char_typeсоответствует размеру примитива, содержащегося в вашем vector. Вы должны включить static_assertв свой код, чтобы подтвердить соответствие этих размеров:

static_assert(sizeof(char32_t) == sizeof(int));

С этим подтверждением вы можете просто сделать:

const u32string concatenation = u32string(first.cbegin(), first.cend()) + u32string(second.cbegin(), second.cend());

Для получения дополнительной информации о различиях между stringи vectorвы можете посмотреть здесь: https://stackoverflow.com/a/35558008/2642059

Живой пример этого кода вы можете посмотреть здесь: http://ideone.com/7Iww3I

Джонатан Ми
источник
0

Это решение может быть немного сложным, но boost-rangeесть и другие приятные предложения.

#include <iostream>
#include <vector>
#include <boost/range/algorithm/copy.hpp>

int main(int, char**) {
    std::vector<int> a = { 1,2,3 };
    std::vector<int> b = { 4,5,6 };
    boost::copy(b, std::back_inserter(a));
    for (auto& iter : a) {
        std::cout << iter << " ";
    }
    return EXIT_SUCCESS;
}

Часто намерение состоит в том, чтобы объединить вектор aи bпросто перебрать его, выполнив некоторую операцию. В этом случае есть смешная простая joinфункция.

#include <iostream>
#include <vector>
#include <boost/range/join.hpp>
#include <boost/range/algorithm/copy.hpp>

int main(int, char**) {
    std::vector<int> a = { 1,2,3 };
    std::vector<int> b = { 4,5,6 };
    std::vector<int> c = { 7,8,9 };
    // Just creates an iterator
    for (auto& iter : boost::join(a, boost::join(b, c))) {
        std::cout << iter << " ";
    }
    std::cout << "\n";
    // Can also be used to create a copy
    std::vector<int> d;
    boost::copy(boost::join(a, boost::join(b, c)), std::back_inserter(d));
    for (auto& iter : d) {
        std::cout << iter << " ";
    }
    return EXIT_SUCCESS;
}

Для больших векторов это может быть преимуществом, так как нет копирования. Его также можно использовать для простого копирования обобщений в несколько контейнеров.

По какой-то причине нет ничего подобного boost::join(a,b,c), что может быть разумным.

Aleph0
источник
0

Вы можете сделать это с помощью предварительно реализованных алгоритмов STL, используя шаблон для использования полиморфного типа.

#include <iostream>
#include <vector>
#include <algorithm>

template<typename T>

void concat(std::vector<T>& valuesa, std::vector<T>& valuesb){

     for_each(valuesb.begin(), valuesb.end(), [&](int value){ valuesa.push_back(value);});
}

int main()
{
    std::vector<int> values_p={1,2,3,4,5};
    std::vector<int> values_s={6,7};

   concat(values_p, values_s);

    for(auto& it : values_p){

        std::cout<<it<<std::endl;
    }

    return 0;
}

Вы можете очистить второй вектор, если не хотите использовать его дальше ( clear()метод).

rekkalmd
источник
-1

Соединить два std::vector-sс forпетлей в одном std::vector.

Пример:

std::vector <int> v1 {1, 2, 3};//declare vector1
std::vector <int> v2 {4, 5};//declare vector2
std::vector <int> suma;//declare vector suma

for(int i = 0; i < v1.size();i++)//for loop 1
{
     suma.push_back(v1[i]);
}

for(int i = 0; i< v2.size();i++)/for loop 2
{
     suma.push_back(v2[i]);
}

for(int i = 0; i < suma.size(); i++)//for loop 3-output
{
     std::cout<<suma[i];
}

Напишите этот код в main().

GobeRadJem32
источник
Вы forне правы. Допустимые индексы в векторе от 0 до size()-1. Вы должны выполнить условия завершения i < v1.size(), используя <not <=. Использование неправильного условия обращается к памяти за пределами контейнера.
Доменная печь
кроме того, что он не работает, этот код сильно не идиоматичен. Вы должны по крайней мере использовать autoитераторы вместо ручной индексации. Вам не важно, какой индекс вы объединяете, только то, что он выполняется последовательно.
Тарик Веллинг
Можете ли вы объяснить, почему вы используете size()-1два условия цикла? Это пропускает последние векторные элементы. Третий цикл является единственным правильным сейчас.
Доменная печь
-3

Если честно, вы можете быстро объединить два вектора, скопировав элементы из двух векторов в другой или просто добавив только один из двух векторов !. Это зависит от вашей цели.

Способ 1: назначить новый вектор с его размером является суммой размеров двух исходных векторов.

vector<int> concat_vector = vector<int>();
concat_vector.setcapacity(vector_A.size() + vector_B.size());
// Loop for copy elements in two vectors into concat_vector

Способ 2: добавить вектор A, добавив / вставив элементы вектора B.

// Loop for insert elements of vector_B into vector_A with insert() 
function: vector_A.insert(vector_A .end(), vector_B.cbegin(), vector_B.cend());
nvnhcmus
источник
4
Что добавляет ваш ответ, который еще не был представлен в других ответах?
Мат
13
@Mat: жирные буквы.
marcv81
Если исходный вектор (ы) больше не нужен после, возможно, лучше использовать его, std::move_iteratorчтобы элементы перемещались, а не копировались. (см. en.cppreference.com/w/cpp/iterator/move_iterator ).
августа
Что такое setcapacity? Что такое function: ?
LF
@ Л.Ф. Я думаю, он говорит о resizeметоде.
Матье H