假设我有一个大小为 N
的 std::vector
(我们称之为 myVec
)。构造一个由元素 X 到 Y 的副本组成的新向量的最简单方法是什么,其中 0 <= X <= Y <= N-1?例如,大小为 150000
的向量中的 myVec [100000]
到 myVec [100999]
。
如果这不能用向量有效地完成,我应该使用另一种 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]);
operator[]
返回一个引用。只有在您读取或写入引用时,它才会成为访问冲突。由于我们什么都不做,而是得到了我们没有调用 UB 的地址。
这个讨论已经很老了,但是最简单的还没有提到,list-initialization:
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;
std::vector<T>(input_iterator, input_iterator)
,在您的情况下是 foo = std::vector<T>(myVec.begin () + 100000, myVec.begin () + 150000);
,例如 here
这些天来,我们使用 span
s!所以你会写:
#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);
获得与 myvec
相同类型的 1000 个元素的跨度。或者更简洁的形式:
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 代表指南支持库。有关 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 而不是 #include
有关跨度的更多信息,请参阅:什么是“跨度”以及何时应该使用跨度?
std::vector 有无数的构造函数,很容易陷入你不打算使用的构造函数中,所以要小心。
cbegin
和 cend
只是为了原则 ;) std::cbegin
等甚至。
如果两者都不会被修改(不添加/删除项目 - 只要您注意线程问题,修改现有项目就可以了),您可以简单地绕过 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
std::vector(myVec.begin () + 100000, myVec.begin () + 150000);
,这个较长版本不会产生完全相同的程序集吗?
std::vector<>(iter, iter)
编译为 memmove()
,如果合适的话(如果构造函数是平凡的,对于平凡的适当定义)。
memcpy
。执行 std::copy
或接受范围(两个迭代器)的构造函数,编译器和 std.library 将在适当时合谋调用 memcpy
。
您可以只使用 insert
vector<type> myVec { n_elements };
vector<type> newVec;
newVec.insert(newVec.begin(), myVec.begin() + X, myVec.begin() + Y);
当 M 是子向量的大小时,您可以使用具有 O(M) 性能的 STL copy。
newvec.reserve(10100 - 10000);
。它绝对是一种选择,从技术上讲它会起作用。但是在这两个中,您要推荐哪个?
投影非线性时间集合的唯一方法是懒惰地这样做,其中生成的“向量”实际上是委托给原始集合的子类型。例如,Scala 的 List#subseq
方法在恒定时间内创建一个子序列。但是,这仅在集合是不可变的并且基础语言支持垃圾收集的情况下才有效。
假设有两个向量。
vector<int> vect1{1, 2, 3, 4};
vector<int> vect2;
方法 1. 使用复制功能。 copy(first_iterator_index, last_iterator_index, back_inserter()) :- 这个函数有 3 个参数,首先是旧向量的第一个迭代器。其次,旧向量的最后一个迭代器和第三个是 back_inserter 函数,用于从后面插入值。
// Copying vector by copy function
copy(vect1.begin(), vect1.end(), back_inserter(vect2));
方法 2. 通过使用分配功能。分配(first_iterator_o,last_iterator_o)。此方法为新向量分配与旧向量相同的值。这需要 2 个参数,第一个迭代器到旧向量,最后一个迭代器到旧向量。
//Copying vector by assign function
vect2.assign(vect1.begin(), vect1.end());
将元素从一个向量轻松复制到另一个向量在此示例中,我使用成对向量以使其易于理解
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));
为其他人发布这个迟到..我敢打赌第一个编码器现在已经完成了。对于简单的数据类型,不需要复制,只需恢复到良好的旧 C 代码方法。
std::vector <int> myVec;
int *p;
// Add some data here and set start, then
p=myVec.data()+start;
然后将指针 p 和 len 传递给任何需要子向量的东西。
注意一定是!! len < myVec.size()-start
不定期副业成功案例分享
O(Y-X)
,或者我们会说O(Z) where Z=Y-X
。vector<T> newVec(myVec.begin() + 100000, myVec.begin() + 101000);
?