c++ - 将剩余的项目添加到另一个 vector

Question

我有一个 std::vector<unsigned int> v带有一些索引(出于性能目的，我不能使用 std::set 。

我想创建 v 的否定版本，即具有所有剩余索引的 vector 。如果，在 [0,10] 范围内, v=[0,2,4,6,8] ，我想要否定版本，nv=[1,3,5,7,9] .

备注:v已排序!

这样做最有效的方法是什么？

Answer 1

是线性时间。

std::vector<unsigned int> getnv(unsigned rangebeg, unsigned rangeend, const std::vector<unsigned int>& v)
{
    std::vector<unsigned int> nv;
    nv.reserve(rangeend - rangebeg - v.size());
    std::vector<unsigned int>::const_iterator next = v.begin();
    // skip out-of-range values in v
    while (next != v.end() && *next < rangebeg) {
        ++next;
    }
    for (unsigned i = rangebeg; i < rangeend; ++i)
    {
         if (next != v.end() && *next == i) {
             ++next;
             continue;
         }
         nv.push_back(i);
    }
    return nv;
}