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

295

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

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

Андрей
источник
7
Вы говорите, что хотите извлечь подвектор, но мне кажется, что вам действительно нужно представление / доступ к подвектору - разница в том, что представление не будет копироваться - в старой школе C ++ будет использовать указатель начала и конца, учитывая тот факт, что mem в std :: vector смежна, у вас должна быть возможность итерировать с помощью указателей и, таким образом, избежать копирования, однако, если вы не возражаете против копирования, просто инициализируйте новый вектор с областью действия вашего предыдущего вектор
serup
Существует .data () ( cplusplus.com/reference/vector/vector/data ) начиная с c ++ 11. Однако использование указателей не рекомендуется в контейнерах stl, см. Stackoverflow.com/questions/31663770/…
Дэвид Тот,

Ответы:

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

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

Грег Роджерс
источник
12
+1, также это O (YX), которое меньше или равно O (N) (и в его примере намного меньше)
orip
74
@orip Ну, тогда это O (N) в конце концов.
Иоганн Герелл
55
@GregRogers: не имеет смысла использовать нотацию big-O, где N - это конкретное число. Big-O сообщает скорость роста относительно того, как изменяется N. Иоганн: Лучше не использовать одно имя переменной двумя способами. Мы обычно говорим либо O(Y-X), либо мы сказали бы O(Z) where Z=Y-X.
Mooing Duck
2
@GregRogers Используя этот способ, мы должны объявить новый вектор. Есть ли способ изменить исходный вектор? что-то вроде myVec (первый, последний)? Я знаю, что это неправильно, но мне действительно нужно решение, так как я хочу использовать рекурсию в своих кодах, и мне нужно многократно использовать один и тот же вектор (хотя и измененный). Спасибо!
ulyssis2
13
Почему не просто vector<T> newVec(myVec.begin() + 100000, myVec.begin() + 101000);?
водная черепаха
88

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

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

std::vector<int>   sub(&data[100000],&data[101000]);
Мартин Йорк
источник
2
Хорошо, я не осознавал, что было так просто получить итератор из произвольного векторного элемента.
AndreW
5
Взятие адреса этих векторных элементов является непереносимым хаком, который сломается, если векторная память на самом деле не является смежной. Используйте begin () + 100000 и т. Д.
j_random_hacker
2
Мой плохой, видимо, стандарт гарантирует, что векторное хранилище является смежным. Тем не менее, работать с подобными адресами - плохая практика, поскольку гарантированно не будет работать для всех контейнеров, поддерживающих произвольный доступ, в то время как begin () + 100000 - это.
j_random_hacker
33
@j_random_hacker: Извините, я не согласен. Спецификация STL для std :: vector была явно изменена для поддержки этого типа процедур. Также указатель является допустимым типом итератора. Посмотрите на iterator_traits <>
Мартин Йорк
6
@ taktak004 Нет. Помните, что operator[]возвращает ссылку. Только когда вы прочитаете или напишите ссылку, это станет нарушением прав доступа. Так как мы не делаем ни, но вместо этого получаем адрес, который мы не вызвали UB ,.
Мартин Йорк,
28

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

Anteru
источник
1
Поскольку Эндрю пытается создать новый вектор, я бы порекомендовал "std :: vector foo (..." вместо копирования с помощью "foo = std :: vector (...")
Дрю Дорманн
4
Да, конечно, но не важно, используете ли вы std :: vector <int> foo = std :: vector (...) или std :: vector <int> foo (...).
Антеру
19

В наши дни мы используем spans! Так что вы бы написали:

#include <gsl/span>

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

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

auto my_subspan = gsl::make_span(myvec).subspan(1000000, 1000);

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

В любом случае, помните, что это не копия, это просто представление данных в векторе, поэтому будьте осторожны. Если вам нужна настоящая копия, вы можете сделать:

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

Ноты:

einpoklum
источник
будет использовать cbeginи cendтолько для принципа;) и std::cbeginт. д. даже.
JHBonarius
1
@JHBonarius: видя, что этот код не основан на выборе контейнера, я не вижу особой выгоды; дело вкуса, я полагаю.
einpoklum
11

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

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

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

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

Затмение
источник
Это также хорошо, если вы хотите, чтобы исходный вектор и подвектор были связаны.
PyRulez
8

Это обсуждение довольно старое, но самое простое еще не упомянуто с инициализацией списка :

 vector<int> subvector = {big_vector.begin() + 3, big_vector.end() - 2}; 

Требуется c ++ 11 или выше.

Пример использования:

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

using namespace std;

int main(){

    vector<int> big_vector = {5,12,4,6,7,8,9,9,31,1,1,5,76,78,8};
    vector<int> subvector = {big_vector.begin() + 3, big_vector.end() - 2};

    cout << "Big vector: ";
    for_each(big_vector.begin(), big_vector.end(),[](int number){cout << number << ";";});
    cout << endl << "Subvector: ";
    for_each(subvector.begin(), subvector.end(),[](int number){cout << number << ";";});
    cout << endl;
}

Результат:

Big vector: 5;12;4;6;7;8;9;9;31;1;1;5;76;78;8;
Subvector: 6;7;8;9;9;31;1;1;5;76;
Дэвид Тот
источник
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
MasterHD
источник
2
Интересно, если бы с -O3, «использующим конструктор» @ Anteru std::vector(myVec.begin () + 100000, myVec.begin () + 150000);, разве более длинная версия этого продукта не была бы точно такой же сборкой?
песчаник
1
Например, MSVC ++ 2015 компилируется std::vector<>(iter, iter)в memmove(), если необходимо (если конструктор тривиален, для подходящего определения тривиала).
Пабло Х
1
Не звони memcpy. Сделайте a std::copyили конструктор, который принимает диапазон (два итератора), и компилятор и std.library сговорются вызывать memcpyпри необходимости.
Bulletmagnet
4

Вы могли бы просто использовать insert

vector<type> myVec { n_elements };

vector<type> newVec;

newVec.insert(newVec.begin(), myVec.begin() + X, myVec.begin() + Y);
Матеус Виниций де Андраде
источник
3

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

Юваль Ф
источник
Проголосовал, потому что он указал мне правильное направление, но я могу понять, почему @LokiAstari предлагает, что это неправильный выбор - поскольку STL :: copy работает с двумя массивами std :: vector <T> одного размера и типа. Здесь ОП хочет скопировать подраздел в новый меньший массив, как указано здесь в посте ОП: «0 <= X <= Y <= N-1»
Эндрю
@ Андрей, посмотрите пример использования std :: copy и std :: back_inserter
chrisg
@LokiAstari почему бы и нет?
chrisg
2
@LokiAstari Я имел в виду редактирование этого, которое не выдержало рецензирования, в котором был приведен пример <br/> vector <T> newvec; std :: copy (myvec.begin () + 10000, myvec.begin () +10100, std :: back_inserter (newvec)); <br/> В этом случае вам не нужно сначала создавать пункт назначения, но, конечно, прямая инициализация более ... прямая.
chrisg
1
@ Chrisg: Это также две строки. Кроме того, вам нужно вставить третью строку, чтобы убедиться, что она эффективна. newvec.reserve(10100 - 10000);, Это определенно вариант, и технически это будет работать. Но из двух, которые вы собираетесь рекомендовать?
Мартин Йорк,
1

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

Даниэль Спивак
источник
в c ++ способ сделать это будет иметь вектор shared_ptr в X вместо вектора X и затем копировать SP, но, к сожалению, я не думаю, что это быстрее, потому что атомарная операция связана с шифрованием SP. Или исходный вектор может быть const shared_ptr вектора вместо этого, и вы просто берете ссылку на поддиапазон в нем. ofc вам не нужно делать это shared_ptr для вектора, но тогда у вас есть проблемы на всю жизнь ... все это не в моей голове, может быть неправильно ...
NoSenseEtAl
0

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

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

mrrgu
источник
Это не выполняет копию.
Триларион
0

Возможно, array_view / span в библиотеке GSL - хороший вариант.

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

myd7349
источник
Пожалуйста, добавьте ответ здесь вместе со ссылкой. Поскольку внешняя ссылка может измениться в будущем
Panther
0

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

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

Джишу Дохаре
источник
0

Еще один вариант: полезен, например, при перемещении между a thrust::device_vectorи a 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));
JHBonarius
источник