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

Question

有一个由唯一元素组成的数组std::vector。已经排序了众所周知，它包含一个值为 From 的元素。我想以最佳方式将其替换为唯一值To，继续跟踪其排序属性。我可以简单地通过 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);
}