Сравните гарантии на вставку с подсказкой для заказанных ассоциативных контейнеров

Я хочу вставить новый (уникальный) элемент в известное место (обычно где-то посередине) упорядоченного ассоциативного контейнера std::set/std::multiset/std::map/std::multimap с помощью insert (с подсказкой) или emplace_hint,

Во время операции вставки я абсолютно уверен, что место для вставки находится прямо перед итератором «подсказка». Обычно я могу сравнивать любые два несмежных элемента в контейнере, но эта операция очень тяжелая. Чтобы избежать накладных расходов, я предоставляю пользовательский компаратор для контейнера, который содержит ссылки на указатели на оба соседних элемента (они всегда становились известны прямо перед операцией вставки / размещения).

#include <map>
#include <set>

static std::size_t counter = 0;

template< typename T >
struct less
{

T const * const & pl;
T const * const & pr;

bool operator () (T const & l, T const & r) const
{
if (&l == &r) {
return false;
}
if (pl) {
if (&l == pl) {
return true;
}
if (&r == pl) {
return false;
}
}
if (pr) {
if (&r == pr) {
return true;
}
if (&l == pr) {
return false;
}
}
++counter;
return l < r; // very expensive, it is desirable this line to be unrecheable
}

};

#include <iostream>
#include <algorithm>
#include <iterator>

#include <cassert>

int main()
{
using T = int;
T const * pl = nullptr;
T const * pr = nullptr;
less< T > less_{pl, pr};
std::set< T, less< T > > s{less_};
s.insert({1, 2,/* 3, */4, 5});
std::copy(std::cbegin(s), std::cend(s), std::ostream_iterator< T >(std::cout, " "));
std::cout << '\n';
auto const hint = s.find(4);
// now I want to insert 3 right before 4 (and, of course, after 2)
pl = &*std::prev(hint); // prepare comparator to make a cheap insertion
pr = &*hint;
// if hint == std::end(s), then pr = nullptr
// else if hint == std::begin(s), then pl = nullptr
// if I tried to insert w/o hint, then pl = pr = nullptr;
{
std::size_t const c = counter;
s.insert(hint, 3);
assert(counter == c);
}
std::copy(std::cbegin(s), std::cend(s), std::ostream_iterator< T >(std::cout, " "));
std::cout << '\n';
}

Текущий Libc ++/libstdc ++ реализации позволяют мне использовать описанный компаратор, но есть ли неопределенное поведение, если я полагаюсь на их текущее поведение? Могу ли я рассчитывать, что insert (параметр w / hint) или emplace_hint (и современный insert_or_assign/try_emplace параметр w / hint для map/multimapне касайтесь других элементов, кроме указанных pl а также pr? Это вещь, определяемая реализацией?

Почему я хочу эту странную вещь? IRL я пытался реализовать Алгоритм фортуны найти Диаграмма Вороного в самолете, используя самобалансированные попытки двоичного поиска в STL. std::set используется для хранения текущего состояния части так называемого линия пляжа: цепочка отсортирована конечные точки. Когда я добавляю новый конечная точка Я всегда знаю место, где вставить его прямо перед вставкой. Было бы лучше, если бы я мог добавить assert(false); до или throw std::logic_error{};/__builtin_unreachable(); вместо последнего return в компараторе функтор. Я могу сделать это только при наличии соответствующей логической гарантии. Я могу это сделать?