从向量中提取子向量的最佳方法？

Question

假设我有一个 std::vector （我们称之为 myVec）的大小 N. 。构造一个由元素 X 到 Y 的副本组成的新向量（其中 0 <= X <= Y <= N-1）的最简单方法是什么？例如， 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);，请参阅例如 page = vector.html“rel =”noreferrer“>这里

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 有无数的构造函数，很容易陷入你不打算使用的构造函数，所以要小心。

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

当M具有O（M）性能时，您可以使用 STL副本是子向量的大小。

Answer 8

投影非线性时间的集合的唯一方法是懒散地进行，结果<！>“vector <！>”;实际上是一个委托给原始集合的子类型。例如，Scala的List#subseq方法在恒定时间内创建子序列。但是，这仅在集合不可变且基础语言运行垃圾收集时才有效。

Answer 9

确定。这是一个非常古老的讨论。但我刚刚发现了一些整洁的东西：

slice_array - 这可能是一个快速的选择？我还没有测试过。

Answer 10

仅为其他人发布这个晚了。我打赌第一个编码器现在完成了。 对于简单的数据类型，不需要复制，只需恢复到良好的旧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

Answer 11

也许 array_view / span GSL库中的一个很好的选择。

这也是单个文件实现： array_view 。

Answer 12

轻松地将元素从一个向量复制到另一个向量 点击 在这个例子中，我使用了一对矢量来使它易于理解 点击 `

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中的元素到end的某个索引，那么在那种情况下

vector<pair<int, int> > a(v.begin()+10, v.end()-5);

希望这会有所帮助，请记住在最后一种情况v.end()-5 > v.begin()+10

Answer 13

另一种选择： 例如，在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));

Answer 14

你可以使用insert

vector<type> myVec { n_elements };

vector<type> newVec;

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