Лучший способ извлечь подвектор из вектора?

Question

Предположим, у меня есть std::vector (назовем это myVec) размера N.Какой самый простой способ построить новый вектор, состоящий из копии элементов от X до Y, где 0 <= X <= Y <= N-1?Например, myVec [100000] через myVec [100999] в векторе размера 150000.

Если это невозможно эффективно сделать с помощью вектора, есть ли другой тип данных STL, который мне следует использовать вместо этого?

Answer 1

vector<T>::const_iterator first = myVec.begin() + 100000;
vector<T>::const_iterator last = myVec.begin() + 101000;
vector<T> newVec(first, last);

Это операция O (N) для создания нового вектора, но на самом деле лучшего способа нет.

Answer 2

Просто используйте векторный конструктор.

std::vector<int>   data();
// Load Z elements into data so that Z > Y > X

std::vector<int>   sub(&data[100000],&data[101000]);

Answer 3

std::vector(input_iterator, input_iterator), в вашем случае foo = std::vector(myVec.begin () + 100000, myVec.begin () + 150000);, см., например, здесь

Answer 4

В наши дни мы используем spanс!Итак, вы бы написали:

#include <gsl/span>

...
auto start_pos = 100000;
auto length = 1000;
auto my_subspan = gsl::make_span(myvec).subspan(start_pos, length);

чтобы получить диапазон из 1000 элементов того же типа, что и myvecх.Теперь это не копия, это просто просмотр данных в векторе, поэтому будьте осторожны.Если вам нужна реальная копия, вы можете сделать:

std::vector<T> new_vec(my_subspan.cbegin(), my_subspan.cend());

Примечания:

• gsl означает «Библиотека поддержки рекомендаций».Для получения дополнительной информации о gsl, видеть: http://www.modernescpp.com/index.php/c-core-guideline-the-guidelines-support-library.
• За одну реализацию gsl, видеть: https://github.com/Microsoft/GSL
• C++20 обеспечивает реализацию span.Вы бы использовали std::span и #include <span> скорее, чем #include <gsl/span>.
• Дополнительные сведения о интервалах см. в разделах: Что такое «промежуток» и когда его следует использовать?
• std::vector имеет миллионы конструкторов, очень легко попасть в тот, который вы не собирались использовать, поэтому будьте осторожны.

Answer 5

Если и то, и другое не будет изменено (не добавляйте / не удаляйте элементы - изменение существующих можно, если вы обращаете внимание на проблемы с многопоточностью), вы можете просто обойти data.begin() + 100000 и data.begin() + 101000 и сделать вид, что они являются begin() и end() меньшего вектора.

Или, поскольку векторное хранилище гарантированно будет смежным, вы можете просто передать массив из 1000 элементов:

T *arrayOfT = &data[0] + 100000;
size_t arrayOfTLength = 1000;

Оба этих метода занимают постоянное время, но требуют, чтобы длина данных не увеличивалась, что вызывает перераспределение.

Answer 6

Вы не упомянули, что такое тип std::vector<...> myVec, но если это простой тип или структура / класс, которые не содержат указателей, и вы хотите добиться максимальной эффективности, то вы можете сделать прямую копию памяти (которую я думаю, будет быстрее, чем другие ответы, представленные). Вот общий пример для std::vector<type> myVec, где type в данном случае int:

typedef int type; //choose your custom type/struct/class
int iFirst = 100000; //first index to copy
int iLast = 101000; //last index + 1
int iLen = iLast - iFirst;
std::vector<type> newVec;
newVec.resize(iLen); //pre-allocate the space needed to write the data directly
memcpy(&newVec[0], &myVec[iFirst], iLen*sizeof(type)); //write directly to destination buffer from source buffer

Answer 7

Вы можете использовать копию STL с производительностью O (M), когда M размер подвектора.

Answer 8

Единственный способ проецировать коллекцию, которая не имеет линейного времени, - это делать это лениво, где результирующий " vector " на самом деле это подтип, который делегирует исходную коллекцию. Например, метод Scala List#subseq создает подпоследовательность за постоянное время. Однако это работает только в том случае, если коллекция является неизменной, и если основной язык содержит сборщик мусора.

Answer 9

Хорошо.Это довольно старая дискуссия.Но я только что обнаружил кое-что интересное:

срез_массив - Может ли это быть быстрой альтернативой?Я не проверял это.

Answer 10

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

std::vector <int>   myVec;
int *p;
// Add some data here and set start, then
p=myVec.data()+start;

Затем передайте указатель p и len всему, что нуждается в подвекторе.

notelen должно быть !! len < myVec.size()-start

Answer 11

Может быть, array_view / span в библиотеке GSL - хороший вариант.

Вот также реализация одного файла: array_view .

Answer 12

Легко копируйте элементы из одного вектора в другой
В этом примере я использую вектор пар, чтобы было проще понять.
`

vector<pair<int, int> > v(n);

//we want half of elements in vector a and another half in vector b
vector<pair<lli, lli> > a(v.begin(),v.begin()+n/2);
vector<pair<lli, lli> > b(v.begin()+n/2, v.end());


//if v = [(1, 2), (2, 3), (3, 4), (4, 5), (5, 6)]
//then a = [(1, 2), (2, 3)]
//and b = [(3, 4), (4, 5), (5, 6)]

//if v = [(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7)]
//then a = [(1, 2), (2, 3), (3, 4)]
//and b = [(4, 5), (5, 6), (6, 7)]

'
Как вы можете видеть, вы можете легко копировать элементы из одного вектора в другой. Если вы хотите скопировать элементы, например, с индексом 10 по 16, мы бы использовали

vector<pair<int, int> > a(v.begin()+10, v.begin+16);

и если вам нужны элементы с индексом 10 до некоторого индекса с конца, то в этом случае

vector<pair<int, int> > a(v.begin()+10, v.end()-5);

надеюсь, это поможет, просто помните в последнем случае v.end()-5 > v.begin()+10

Answer 13

Еще один вариант: Полезно, например, при перемещении между thrust::device_vector и thrust::host_vector, где нельзя использовать конструктор.

std::vector<T> newVector;
newVector.reserve(1000);
std::copy_n(&vec[100000], 1000, std::back_inserter(newVector));

Также должна быть сложность O (N)

Вы можете комбинировать это с верхним кодом ответа

vector<T>::const_iterator first = myVec.begin() + 100000;
vector<T>::const_iterator last = myVec.begin() + 101000;
std::copy(first, last, std::back_inserter(newVector));

Answer 14

Вы можете просто использовать insert

vector<type> myVec { n_elements };

vector<type> newVec;

newVec.insert(newVec.begin(), myVec.begin() + X, myVec.begin() + Y);