有条件地将一个矢量复制到另一个矢量的最快方法

Question

这个问题与现有问题有关:快速将一个向量复制到另一个向量

我有一个矢量源矢量S,我想创建一个目标矢量D,它只有满足特定条件的S元素(比如元素是偶数).注意,源向量是常量向量.

我可以想到两个STL算法来做到这一点:

• copy_if
• 的remove_if

在这两种方法中,我都需要确保目标向量D的大小足够大.因此,我需要创建与S大小相同的初始向量D.此外,在这两种方法中,我想将向量D压缩为与其中元素数量相同的长度.我不知道哪一个更快或更方便但我不知道有条件地复制矢量的更好的方法？

Answer 1

最简单的方法是:

auto const predicate = [](int const value) { return value % 2 == 0; };
std::copy_if(begin(src), end(src), back_inserter(dest), predicate);

它依赖于push_back.

现在,的确,这可能会触发内存重新分配.但是我想强调push_back已经分摊了常​​数的复杂性,这意味着平均值是O(1),这是通过具有指数增长行为来实现的(因此执行的分配数量是O(log N)).

另一方面,如果你有100万个元素,其中只有5个是偶数,它不会预先分配4MB的内存,只是稍后放弃它只有20个字节.

因此:

• 当分布偏向奇数时,它是最优的,因为它不会过多分配
• 否则它接近最优,因为它不会重新分配太多

更有趣的是,如果您对预先分配有所了解,可以使用resize和shrink_to_fit:

// 90% of the time, 30% of the numbers are even:
dest.reserve(src.size() * 10 / 3);

auto const predicate = [](int const value) { return value % 2 == 0; };
std::copy_if(begin(src), end(src), back_inserter(dest), predicate);

dest.shrink_to_fit();

这条路:

• 如果少于30%,shrink_to_fit 可能会削减多余的
• 如果有30%,宾果游戏
• 如果超过30%,则根据需要触发重新分配,仍然遵循O(log N)模式

个人经验告诉我,呼叫reserve很少(如果有的话)值得,摊销不变的复杂性非常有利于降低成本.

注意:shrink_to_fit是非绑定的,没有保证的方式让它capacity等于size,实现选择什么是最好的.

Answer 2

好吧,你可以使用back_inserter:

std::vector<int> foo = {...whatever...};
std::vector<int> bar;
std::back_insert_iterator< std::vector<int> > back_it (bar);

std::copy_if (foo.begin(), foo.end(), back_it, MyPredicate);

或计数元素:

std::vector<int> foo = {...whatever...};
int mycount = count_if (foo.begin(), foo.end(), MyPredicate);
std::vector<int> bar (mycount);

std::copy_if (foo.begin(), foo.end(), bar.begin(), MyPredicate );

第三种解决方案:

std::vector<int> foo = {...whatever...};
std::vector<int> bar (foo.size());

auto it = std::copy_if (foo.begin(), foo.end(), bar.begin(), MyPredicate );
bar.resize(std::distance(bar.begin(),it));