c++ - 如何快速从已排序的 vector 中获取已排序的子 vector

Question

我有这样的数据结构:

struct X {
  float value;
  int id;
};

一个 vector (大小 N(认为 100000)，按值排序(在程序执行期间保持不变):

std::vector<X> values;

现在，我想写一个函数

void subvector(std::vector<X> const& values, 
               std::vector<int> const& ids, 
               std::vector<X>& out /*, 
               helper data here */);

用 值 的排序子集填充 out 参数，由传递的 ids 给出(大小 M <N(大约是 N 的 0.8 倍)，快速(内存不是问题，这个会反复做，所以构建 lookuptables (来自函数参数的辅助数据)或其他只做一次的东西是完全可以的。

到目前为止我的解决方案:
构建包含 id 的查找表 lut -> values 中的偏移量(准备，因此运行时不变)
创建 std::vector<X> tmp ，大小 N，填充无效 ID(线性 N)
对于每个 ID，复制 values[lut[id]]至 tmp[lut[id]] (线性 M)
遍历tmp，将项目复制到out(线性N)

这在 N 中是线性的(因为它比 M 大)，但是临时变量和重复复制让我很烦。有没有比这更快的方法？请注意，M 将接近于 N，因此 O(M log N) 是不利的。

编辑:http://ideone.com/xR8Vp是上述算法的示例实现，以明确所需的输出并证明它在线性时间内是可行的 - 问题是关于避免临时变量或以其他方式加速它的可能性，非线性的东西不是更快:).

Answer 1

您可以尝试的另一种方法是使用哈希表而不是 vector 在以下位置查找 ID:

void subvector(std::vector<X> const& values, 
               std::unordered_set<int> const& ids, 
               std::vector<X>& out) {

    out.clear();
    out.reserve(ids.size());
    for(std::vector<X>::const_iterator i = values.begin(); i != values.end(); ++i) {
        if(ids.find(i->id) != ids.end()) {
            out.push_back(*i);
        }
    }
}

这在线性时间内运行，因为 unordered_set::find 是恒定的预期时间(假设我们没有散列整数问题)。但是我怀疑它在实践中可能不如您最初描述的使用 vector 的方法快。