首页 文章

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

提问于
浏览 次
215

假设我有 std::vector （让我们称之为 myVec ），大小为 N . 构造由元素X到Y的副本组成的新向量的最简单方法是什么，其中0 <= X <= Y <= N-1？例如， myVec [100000] 到 myVec [100999] 在大小为 150000 的向量中 .

如果使用向量无法有效地完成此操作，是否应该使用另一种STL数据类型？

c++ stl vector range

13 回答

  • 3

    如果两者都不会被修改（没有添加/删除项目 - 只要你注意线程问题就修改现有项目就可以了），你可以简单地传递 data.begin() + 100000 和 data.begin() + 101000 ，并假装它们是 begin() 和 end() 一个较小的矢量 .

    或者，由于矢量存储保证是连续的，您可以简单地传递1000个项目数组：

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

    这两种技术都需要持续时间，但要求数据长度不会增加，从而触发重新分配 .

    回复于
  • 0
    vector<T>::const_iterator first = myVec.begin() + 100000;
vector<T>::const_iterator last = myVec.begin() + 101000;
vector<T> newVec(first, last);

    这是构造新向量的O（N）操作，但实际上并没有更好的方法 .

    回复于
  • 67

    只需使用向量构造函数 .

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

std::vector<int>   sub(&data[100000],&data[101000]);
    回复于
  • 6

    std::vector(input_iterator, input_iterator) ，在你的情况 foo = std::vector(myVec.begin () + 100000, myVec.begin () + 150000); ，见例如here

    回复于
  • 0

    你没有提到 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
    回复于
  • 6

    这些天，我们使用 span ！所以你会写：

    #include <gsl/span>

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

    获得与 myvec 相同类型的1000个元素的 Span . 现在，这不是副本，它只是向量中的数据视图，所以要小心 . 如果你想要一个实际的副本，你可以这样做：

    std::vector<T> new_vec(my_subspan.begin(), my_subspan.end());

    笔记：

    回复于
  • 0

    当M是子向量的大小时，可以使用具有O（M）性能的STL copy .

    回复于
  • 280

    投射非线性时间集合的唯一方法是懒散地进行，其中生成的"vector"实际上是委托给原始集合的子类型 . 例如，Scala的 List#subseq 方法在恒定时间内创建子序列 . 但是，这仅在集合不可变且基础语言运行垃圾收集时才有效 .

    回复于
  • 0

    好 . 这是一个非常古老的讨论 . 但我发现了一些简洁的东西：

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

    回复于
  • 0

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

    回复于
  • 10

    也许GSL库中的array_view/span是一个不错的选择 .

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

    回复于
  • 23

    Copy elements from one vector to another easily
    在这个例子中，我使用了一对矢量来使它易于理解
    `

    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

    回复于
  • 1

    还有一个选项：例如在 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));
    回复于

相关问题