提取向量的每隔一个元素

Question

提取向量的每隔一个元素

c++stdvector

7

将一个 std::vector 拆分成两个半尺寸的 std::vectors（其中一个包含奇数索引的值，另一个包含偶数索引的值），是否有比迭代原始向量并比较每个索引的 index%2==0 更快的方法？

- user1504193

我不知道它是否有帮助：你尝试过copy_if了吗？ - PaperBirdMaster

可以使用增量为2而不是1来将其分成两个步骤，但几乎肯定比您已经拥有的％2版本慢。 - Ylisar

在这里，“更好”的定义是什么？代码更易读？更快？输入更少的代码？ - PlasmaHH

@user1504193，我修改了你的问题，让它更加快速。 - Mark B

3个回答

6

// Make sure the vector is not empty
if(!v.empty()){
    for(size_t i = 0; i < (v.size() - 1); i+=2){
        v1.push_back(v[i]);
        v2.push_back(v[i + 1]);
    }

    if(v.size() % 2) v1.push_back(v.back());
}

正如多个人在评论中指出的那样，您必须检查向量是否为空。您可以通过在循环之前调整两个向量的大小来避免使用推回调用，即：

// Make sure the vector is not empty
if(!v.empty()){
    v1.resize((v.size() + 1) / 2);
    v2.resize(v.size() / 2);
    for(size_t i = 0, j = 0; i < (v.size() - 1); i+=2, j++){
        v1[j] = (v[i]);
        v2[j] = (v[i + 1]);
    }

    if(v.size() % 2) v1.push_back(v.back());
}

- GWW

需要注意的是，向量不应为空，因为在这种情况下，循环条件将失败。 - betabandido

我不明白这种方法怎么比%2的方式更快... 如果push_back、i+1和operator[]的复杂度都是c，那么这个方法大概是N/25c... 而%2循环遍历每个元素，难道你会得到类似于N2c的结果吗？我猜operator[]可能比其他两个函数要快得多，但直觉上这似乎不太可能。你能详细解释一下吗？ - Moritz

2

@Moritz 这种方式每次迭代可以节省一个分支和一个除法，所以很容易看到它会更快。但是请注意，如果大小为零，则初始循环将运行多次迭代。 - Mark B

谢谢你们两位的评论，我已经调整了我的答案。 - GWW

你可以使用.reserve()，然后使用.push_back()而不必担心昂贵的重新分配。 - liborm

-2

虽然这个问题已经有一段时间了，但因为没有人建议使用迭代器和std::next，我想提一下：

// assert myvec.size() % 2 == 0
const unsigned long n = myvec.size() / 2;
std::vector<T> v1(n), v2(n);
std::vector<T>::iterator it = myvec.begin(), i1 = v1.begin(), i2 = v2.begin();
while (it != myvec.end()) {
    v1[*i1] = myvec[*it];
    it = std::next(it);
    i1 = std::next(i1);
    v2[*i2] = myvec[*it];
    it = std::next(it);
    i2 = std::next(i2);
}

- mpadge

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- hmjd · Accepted Answer

我不确定"better"是什么意思，但如果使用C++11，您可以使用std::partition_copy：

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

int main()
{
    std::vector<int> v1;
    for (int i = 0; i < 100; i++) v1.push_back(i);

    std::vector<int> v2;
    std::vector<int> v3;

    bool toggle = false;
    std::partition_copy(v1.begin(),
                        v1.end(),
                        std::back_inserter(v2),
                        std::back_inserter(v3),
                        [&toggle](int) { return toggle = !toggle; });

    std::cout << v2.size() << "\n";
    std::cout << v3.size() << "\n";

    return 0;
}

可以查看在线演示：http://ideone.com/pa9rW。