Лучший способ извлечь подвектор из вектора?
Вопрос
Предположим, у меня есть std::vector
(назовем это myVec
) размера N
.Какой самый простой способ построить новый вектор, состоящий из копии элементов от X до Y, где 0 <= X <= Y <= N-1?Например, myVec [100000]
через myVec [100999]
в векторе размера 150000
.
Если это невозможно эффективно сделать с помощью вектора, есть ли другой тип данных STL, который мне следует использовать вместо этого?
Решение
vector<T>::const_iterator first = myVec.begin() + 100000;
vector<T>::const_iterator last = myVec.begin() + 101000;
vector<T> newVec(first, last);
Это операция O (N) для создания нового вектора, но на самом деле лучшего способа нет.
Другие советы
Просто используйте векторный конструктор.
std::vector<int> data();
// Load Z elements into data so that Z > Y > X
std::vector<int> sub(&data[100000],&data[101000]);
std::vector(input_iterator, input_iterator)
, в вашем случае foo = std::vector(myVec.begin () + 100000, myVec.begin () + 150000);
, см., например, здесь
В наши дни мы используем 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
имеет миллионы конструкторов, очень легко попасть в тот, который вы не собирались использовать, поэтому будьте осторожны.
Если и то, и другое не будет изменено (не добавляйте / не удаляйте элементы - изменение существующих можно, если вы обращаете внимание на проблемы с многопоточностью), вы можете просто обойти data.begin() + 100000
и data.begin() + 101000
и сделать вид, что они являются begin()
и end()
меньшего вектора.
Или, поскольку векторное хранилище гарантированно будет смежным, вы можете просто передать массив из 1000 элементов:
T *arrayOfT = &data[0] + 100000;
size_t arrayOfTLength = 1000;
Оба этих метода занимают постоянное время, но требуют, чтобы длина данных не увеличивалась, что вызывает перераспределение.
Вы не упомянули, что такое тип 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
Вы можете использовать копию STL с производительностью O (M), когда M размер подвектора.
Единственный способ проецировать коллекцию, которая не имеет линейного времени, - это делать это лениво, где результирующий " vector " на самом деле это подтип, который делегирует исходную коллекцию. Например, метод Scala List#subseq
создает подпоследовательность за постоянное время. Однако это работает только в том случае, если коллекция является неизменной, и если основной язык содержит сборщик мусора.
Хорошо.Это довольно старая дискуссия.Но я только что обнаружил кое-что интересное:
срез_массив - Может ли это быть быстрой альтернативой?Я не проверял это.
Опоздание только для других ... Держу пари, первый кодер уже готов. Для простых типов данных копирование не требуется, просто вернитесь к старым добрым методам кода Си.
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
Р>
Может быть, array_view / span в библиотеке GSL - хороший вариант.
Вот также реализация одного файла: array_view .
Легко копируйте элементы из одного вектора в другой
В этом примере я использую вектор пар, чтобы было проще понять.
`
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
Еще один вариант:
Полезно, например, при перемещении между 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));
Вы можете просто использовать insert
vector<type> myVec { n_elements };
vector<type> newVec;
newVec.insert(newVec.begin(), myVec.begin() + X, myVec.begin() + Y);