c++ - 更新已排序 vector 的一个条目

Question

假设我有一个排序的 std::vector<int>称为 v .我增加了 v[i] 的值我想重新排序 vector 。假设我希望增加 v[i]只有一点点。下面肯定是错误的。

// (WRONG)
int x = v[i]; // the new v[i], that is
v.erase(v.begin() + i);
v.insert(
    std::upper_bound(v.begin() + i, v.end(), x),
    x
);

这是错误的，因为我在删除时将几乎整个数组向后移动，在插入时向前移动，而且我可能只会增加 v[i]一点点，这只需要移动一些条目。另一个想法可能是:

int x = v[i]; // the new v[i], that is
if (/* new v[i] is > old v[i] */) {
    size_t j = i + 1;
    while (v[j] < x && j < v.size()) {
        std::swap(v[j-1], v[j])
        j++;
    }
}

同样，如果我减少了 v[i]而不是增加它。这是最好的吗？

假设我无权访问 boost::flat_set . (不确定它是否可以轻松地做到这一点。)如果已经回答，我们深表歉意；搜索未找到答案。

Answer 1

使用std::rotate将元素移动到新位置。如果您真的认为它不会移动太远，则线性搜索新位置可能会更快(或应用混合方法，通过检查与旧位置的双倍距离来找到 upper_bound).