c++ - 替换排序范围内的元素

Question

有一个std::vector 数组unique 元素。它排序。众所周知，它包含一个值为 From 的元素。我想用 unique 值 To 以最佳方式替换它，并继续跟踪其 sorted 属性。我可以简单地通过 std::lower_bound 实现它，然后替换并最终将 std::sort 应用于整个数组，但我知道 - 它不是最优的，因为有只是子范围 [std::lower_bound(beg, end, From), std::upper_bound(beg, end, To)) 应该最大程度地重新排序。

int From = 4;
int To = 7;
std::vector< int > v{2, 4, 6, 8};
auto const beg = std::begin(v);
auto const end = std::end(v);
*std::lower_bound(beg, end, From) = To;
std::sort(beg, end);

如何使用STL达到预期效果？

Answer 1

找到要替换的元素的位置，并找到插入元素应该在的位置，一旦它被插入(在这两种情况下使用 lower_bound)。然后替换元素，旋转。

auto p1 = std::lower_bound(beg, end, From);
auto p2 = std::lower_bound(beg, end, To);
*p1 = To;
if (p1 < p2)
{
    std::rotate(p1, p1 + 1, p2);
}
else if (p2 < p1)
{
    std::rotate(p2, p1, p1 + 1);
}