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

Question

Предположим, у меня есть std::vector (назовем это myVec) размера N. Какой самый простой способ построить новый вектор, состоящий из копии элементов от X до Y, где 0 <= X <= Y <= N-1? Например, от <code>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 имеет gazillion конструкторов, очень легко попасть в тот, который вы не собирались использовать, так что будьте осторожны.

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 copy с производительностью O (M), когда M - это размер субвектора.

Answer 8

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

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

Answer 9

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

Answer 10

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

vector<type> myVec { n_elements };

vector<type> newVec;

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