C++: эффективная копия списка векторов в векторе

Я ищу наиболее эффективный способ скопировать содержимое списка векторов в вектор. Я хочу, насколько это возможно, избежать перераспределения памяти.

Моя проблема заключается в следующем: у меня есть:

  • a std::vector<int> v, содержащий N элементов

  • список векторов std::vector< std::vector<int>* > vlist

  • и я знаю, что общее количество элементов M в векторах vlist равно ‹= N (N и M могут быть очень большими)

Я хочу скопировать все элементы vlist в v (сначала все элементы vlist[0], затем все элементы vlist[1] и т.д...) и в конце уменьшить размер v до M (мой проект не не использовать С++ 2011).

Как сделать это максимально эффективно?

Большое Вам спасибо.

РЕДАКТИРОВАТЬ: примечание: v уже заполнен N элементами, и я хочу заменить их элементами M (‹= N), поступающими из других векторов.


c++ vector stdvector
person Vincent    schedule 15.05.2012    source источник
comment
Если вы хотите избежать выделения памяти, вы не можете получить копию, вы можете получить ссылку. Вы можете либо сослаться на объект, либо создать его копию, вероятно, наиболее интуитивно понятным вариантом является повторное использование памяти при копировании (это сэкономит на выделении памяти). Поскольку ваш вектор содержит int, вы собираетесь поместить их в стек, чтобы это было быстрее, чем выделение в куче.   -  person Kiril    schedule 16.05.2012

Ответы (3)


arrow_upward
1
arrow_downward

Я понятия не имею, является ли это наиболее эффективным способом, но это способ:

std::vector<int> v;
std::vector< std::vector<int>* > vlist;
int j = 0;
for(int i = 0; i < vlist.size(); ++i) {
  std::copy(vlist[i]->begin(), vlist[i]->end(), &v[j]);
  j += vlist[i]->size();
}
v.resize(j);

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

person Robᵩ    schedule 15.05.2012

arrow_upward
0
arrow_downward

Самый действенный способ — не копировать. Что делает ваше приложение, что требует этого? Кроме того, почему у вас vector<* vector<int> > вместо vector<vector<int> >? Создавайте вокруг него, используйте pimpl, ленивое копирование и т. д.

И, в конце концов, я не уверен, что, по вашему мнению, вы можете сделать, чтобы превзойти конструктор копирования std по умолчанию. Вы профилировали свое приложение, чтобы определить, что ctor по умолчанию является узким местом?

person djechlin    schedule 15.05.2012

arrow_upward
0
arrow_downward 

std::vector<int> v;
v.reserve(N);
for(size_t i = 0; i<vlist.size(); i++)
{
   v.insert(v.end(), vlist[i]->begin(), vlist[i]->end());
}

Это должно быть достаточно эффективно, если M близко к N. В противном случае лучше вычислить M перед выделением памяти и использовать v.reserve(M).

person Peter Popov    schedule 15.05.2012
comment
Вы имели в виду использовать резерв вместо изменения размера? Также вы имели в виду это: vlist[i]->begin() и vlist[i]->end() - person Benjamin Lindley; 16.05.2012
comment
используйте v.reserve(N), а не v.resize(N). resize fact сначала устанавливает для данных значение по умолчанию, в то время как backup просто выделяет пространство. - person andre; 16.05.2012