Лучший способ извлечь подвектор из вектора?
Предположим, у меня есть std::vector (назовем его myVec) размера N. Какой самый простой способ построить новый вектор, состоящий из копии элементов с X по Y, где 0 <= X <= Y <= N-1? Например, от myVec [100000] до myVec [100999] в векторе размером 150000.
Если это не может быть эффективно сделано с вектором, есть ли другой тип данных STL, который я должен использовать вместо этого?
Начиная с C++ 11 существует .data () (cplusplus.com/reference/vector/vector/data). Однако использование указателей в контейнерах stl не рекомендуется, см. stackoverflow.com/questions/31663770/…
Ответы 14
Вы можете использовать Копия STL с производительностью O (M), когда M - размер подвектора.
Проголосовали за, потому что он указал мне в правильном направлении, но я понимаю, почему @LokiAstari предлагает неправильный выбор - поскольку STL :: copy работает с двумя массивами std :: vector <T> одинакового размера и типа. Здесь OP хочет скопировать подраздел в новый, меньший массив, как описано здесь в сообщении OP: «0 <= X <= Y <= N-1»
@Andrew, см. Пример с использованием std :: copy и std :: back_inserter
@LokiAstari, почему бы и нет?
@chrisg: разгадка кроется в имени copy. Чтобы использовать std :: copy, вам нужно сначала создать место назначения (что означает инициализацию всех членов их значением по умолчанию). Затем вы можете скопировать их. Итак, это две разные операции. Почему бы просто не использовать конструктор вектора и не инициализировать члены непосредственно их конечными значениями. Посмотрите красивый ответ, за который проголосовало +50.
@LokiAstari Я имел в виду правку, которая не выдержала экспертной оценки, в которой приведен пример <br/> vector <T> newvec; std :: copy (myvec.begin () + 10000, myvec.begin () +10100, std :: back_inserter (newvec)); <br/> в этом случае вам не нужно сначала создавать место назначения, но, конечно, прямая инициализация более ... прямая.
@chrisg: Это тоже две строки. Кроме того, вам нужно вставить третью строку, чтобы убедиться, что она эффективна. newvec.reserve(10100 - 10000);. Это определенно вариант, и технически он будет работать. Но какой из двух вы порекомендуете?
@LokiAstari а, хорошо, я продана. Потребность в резерве на больших сетах подтолкнула меня к черту. Мне также не нравилось ощущение "под капотом" использования голых указателей, зависимости от базовой детали (или "гарантии", что вектор непрерывен) и неконтролируемого доступа, подобного массиву, потому что они кажутся очень похожими на C и не -С ++ - вроде, но потом я решил, что это не хуже, чем арифметика итератора, используемая для подхода std :: copy
@chrisg: в ответе, получившем наибольшее количество голосов, используются стандартные итераторы и конструктор.
std::vector<T>(input_iterator, input_iterator), в вашем случае foo = std::vector<T>(myVec.begin () + 100000, myVec.begin () + 150000);, см. Например здесь
Поскольку Эндрю пытается построить новый вектор, я бы рекомендовал "std :: vector foo (..." вместо копирования с помощью "foo = std :: vector (..."
Да, конечно, но не имеет значения, набираете ли вы std :: vector <int> foo = std :: vector (...) или std :: vector <int> foo (...).
vector<T>::const_iterator first = myVec.begin() + 100000;
vector<T>::const_iterator last = myVec.begin() + 101000;
vector<T> newVec(first, last);
Это операция O (N) для создания нового вектора, но на самом деле лучшего способа нет.
+1, также это O (Y-X), что меньше или равно O (N) (а в его примере намного меньше)
@orip Ну, тогда все-таки О (Н).
@GregRogers: Нет смысла использовать нотацию большого O, где N - конкретное число. Big-O сообщает скорость роста относительно того, как изменяется N. Иоганн: Лучше не использовать одно имя переменной двумя способами. Обычно мы говорим либо O(Y-X), либо O(Z) where Z=Y-X.
@GregRogers Используя этот способ, нам нужно объявить новый вектор. Есть ли способ изменить исходный вектор? что-то вроде myVec (первый, последний)? Я знаю, что это неправильно, но мне действительно нужно решение, поскольку я хочу использовать рекурсию в своих кодах, и мне нужно многократно использовать один и тот же вектор (хотя и измененный). Спасибо!
@ ulyssis2 Создать новый вектор и поменять местами?
Почему не только vector<T> newVec(myVec.begin() + 100000, myVec.begin() + 101000);?
Кроме того, если newVec уже существует и вы хотите заменить его содержимое, используйте newVec.asign(first, last). Он имеет ту же семантику, что и конструктор в ответе.
что произойдет, если последний итератор выйдет за пределы границ?
Вы также можете использовать auto вместо vector<T>::const_iterator
Просто для моей справки, результирующий вектор - это неглубокая копия, верно? субвектор не является указателем на исходные векторы, лежащие в основе структуры данных, верно? Я в основном хочу знать, что если я вернусь к стеку, внутренние указатели на результирующий субвектор останутся действительными, потому что они отделены от исходного супер-вектора.
Строка 3 - копия? Можно ли таким образом построить ссылочный подвектор?
В качестве побочного примечания конструктор диапазона std :: vector constructs the container with the contents of the range [first, last).
Отличное предложение. Можно ли использовать auto cbegin вместо begin? auto first = myVec.cbegin() + 100000; auto last = myVec.cbegin() + 101000;
Единственный способ спроецировать коллекцию, которая не является линейной по времени, - это делать это лениво, когда результирующий «вектор» на самом деле является подтипом, который делегируется исходной коллекции. Например, метод Scala List#subseq создает подпоследовательность за постоянное время. Однако это работает только в том случае, если сборка неизменна и если базовый язык поддерживает сборку мусора.
в С ++ способ сделать это будет иметь вектор shared_ptr в X вместо вектора X, а затем скопировать SP, но, к сожалению, я не думаю, что это быстрее, потому что атомарная операция связана с cpying SP. Или исходный вектор может быть const shared_ptr of vector, и вы просто берете в нем ссылку на поддиапазон. конечно, вам не нужно делать его shared_ptr вектора, но тогда у вас есть проблемы на время жизни ... все это не в моей голове, может быть неправильно ...
Просто используйте конструктор векторов.
std::vector<int> data();
// Load Z elements into data so that Z > Y > X
std::vector<int> sub(&data[100000],&data[101000]);
Хорошо, я не понимал, что получить итератор из произвольного векторного элемента так просто.
Что ж, вы фактически получаете указатели на элементы, которые в большинстве случаев эквивалентны итераторам. Однако я предполагаю, что они не будут проверяться как итераторы, если у вас есть реализация проверенных итераторов. Может быть какая-то магия, о которой я не подозреваю, хотя это тоже помогает ...
Получение адреса этих векторных элементов - это непереносимый взлом, который сломается, если хранилище векторов на самом деле не является непрерывным. Используйте begin () + 100000 и т. д.
Мое плохое, по-видимому, стандарт гарантирует непрерывность векторного хранилища. Тем не менее, работать с такими адресами - плохая практика, так как это, конечно, не гарантирует работы для всех контейнеров, поддерживающих произвольный доступ, в то время как begin () + 100000 работает.
@j_random_hacker: Извините, что не согласен. Спецификация STL для std :: vector была явно изменена для поддержки этого типа процедуры. Также указатель является допустимым типом итератора. Найдите iterator_traits <>
Да, указатели не обязательно являются действительными std :: vector <T> :: iterator, но они являются действительными итераторами для массива в непрерывном хранилище, как оно и используется.
@Uri: Это всегда будет работать. Но, как и весь код, он ограничен системными ограничениями. Если вы попытаетесь сделать что-то, что физически невозможно, вы получите исключение.
Как бы вы с помощью этого разрезали последний элемент? Если вы сделаете sub (& data [100000], & data [data.size ()]); Это не всегда будет работать и может вызвать нарушение прав доступа?
@ taktak004 Нет. Помните, что operator[] возвращает ссылку. Только в том месте, где вы читаете или записываете ссылку, это может стать нарушением доступа. Поскольку мы не делаем ни того, ни другого, а вместо этого получаем адрес, который мы не вызывали, UB ,.
Это не сработает, если вам нужно скопировать данные до конца исходного вектора.
@bialix: Будет. Я предполагаю, что вы говорите о том, что взяли адрес одного из прошлых, а затем в конце концов стали проблемой. Это предусмотрено стандартом и разрешено. UB разыменовывать эти адреса, но не брать его адрес. Обратите внимание, что определение X[Y] определено в стандарте как *(X + Y). И операторы &*, помещенные вместе, компенсируют друг друга (при условии, что они не были переопределены (что не может быть для указателей)). => &X[Y] => &*(X + Y) => (X + Y). Вот почему 10000[data] является допустимым выражением для доступа к массиву.
Если оба не собираются изменять (не нужно добавлять / удалять элементы - изменение существующих - это нормально, если вы обращаете внимание на проблемы потоковой передачи), вы можете просто передать data.begin() + 100000 и data.begin() + 101000 и представить, что они являются begin() и end() из меньший вектор.
Или, поскольку векторное хранилище гарантированно непрерывно, вы можете просто передать массив из 1000 элементов:
T *arrayOfT = &data[0] + 100000;
size_t arrayOfTLength = 1000;
Оба эти метода требуют постоянного времени, но требуют, чтобы длина данных не увеличивалась, вызывая перераспределение.
Это также хорошо, если вы хотите, чтобы исходный вектор и подвектор были связаны.
Публикация так поздно только для других .. Держу пари, что первый кодировщик уже готов. Для простых типов данных копирование не требуется, просто вернитесь к старым добрым методам кода C.
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
Копирование не выполняется.
Вы не упомянули, какой тип 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
Интересно, если с -O3, @ Anteru "using constructor" std::vector(myVec.begin () + 100000, myVec.begin () + 150000);, не будет ли более длинная версия этого преобразована в точно такую же сборку?
Например, MSVC++ 2015 компилирует std::vector<>(iter, iter) в memmove(), если это необходимо (если конструктор тривиальный, для подходящего определения тривиального).
Не звоните memcpy. Создайте std::copy или конструктор, который принимает диапазон (два итератора), и компилятор и std.library сговорились вызвать memcpy, когда это необходимо.
Возможно, array_view / диапазон в библиотеке GSL - хороший вариант.
Вот также реализация одного файла: array_view.
Пожалуйста, добавьте сюда ответ вместе со ссылкой. Поскольку внешняя ссылка может измениться в будущем
В наши дни мы используем span! Итак, вы бы написали:
#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. Или более сжатая форма:
auto my_subspan = gsl::make_span(myvec).subspan(1000000, 1000);
(но мне это не очень нравится, поскольку значение каждого числового аргумента не совсем понятно; и становится хуже, если length и start_pos имеют одинаковый порядок величины.)
В любом случае, помните, что это не копия, это просто вид данных в векторе, поэтому будьте осторожны. Если вам нужна настоящая копия, вы можете сделать:
std::vector<T> new_vec(my_subspan.cbegin(), my_subspan.cend());
Заметки:
gslрасшифровывается как Guidelines Support Library. Для получения дополнительной информации оgslсм .: http://www.modernescpp.com/index.php/c-core-guideline-the-guidelines-support-library.- Существует несколько реализаций
gsl. Например: https://github.com/martinmoene/gsl-lite - C++ 20 предоставляет реализацию
span. Вы бы использовалиstd::spanи#include <span>, а не#include <gsl/span>. - Для получения дополнительной информации о пролетах см .: Что такое интервал и когда его использовать?
std::vectorимеет миллиард конструкторов, очень легко попасть в тот, который вы не собирались использовать, так что будьте осторожны.
использовал бы cbegin и cend только по принципу;) даже std::cbegin и т. д.
@JHBonarius: Видя, что этот код не основан на шаблоне выбора контейнера, я не вижу особого преимущества; полагаю, дело вкуса.
Легко копируйте элементы из одного вектора в другой
В этом примере я использую вектор пар, чтобы упростить понимание
`
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);
Это довольно старое обсуждение, но самое простое еще не упомянуто, с список-инициализация:
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;
вы говорите, что хотите извлечь подвектор, но мне кажется, что на самом деле вам нужно представление / доступ к подвектору - разница в том, что представление не будет копироваться - старый школьный C++ будет использовать начальный указатель и конечный указатель, учитывая тот факт, что mem в std :: vector является смежным, тогда у вас должна быть возможность выполнять итерацию с использованием указателей и, таким образом, избегать копирования, однако, если вы не против копирования, просто инициализируйте новый вектор с областью действия вашего предыдущего вектор