比较有序关联容器的插入与提示的保证

Question

我想将新的(唯一的)元素插入到有序关联容器中的已知位置(通常位于中间某处)std::set/ std::multiset/ std::map/ std::multimap使用insert(w/hint)或emplace_hint.

在插入操作期间,我绝对肯定,插入的位置正好在"提示"迭代器之前.通常我可以比较容器中的任何两个非相邻元素,但这个操作非常重量级.为了避免开销,我为容器提供了自定义比较器,它包含对两个neigbouring元素的指针的引用(它们总是在插入/放置操作之前就已知).

#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 /提示参数)或emplace_hint(和现代insert_or_assign/ try_emplacew代表/提示参数map/ multimap)不接触任何其他元素其他然后指向pl和pr？它是实现定义的东西吗？

为什么我想要这个奇怪的东西？IRL我尝试使用本机STL的自平衡二进制搜索尝试来实现Fortune算法在平面上查找Voronoi图.std::set用于存储所谓的海滩线的一部分的当前状态:一系列已排序的端点.当我添加一个新端点时,我总是知道在插入之前插入它的位置.如果我可以在比较器仿函数中添加assert(false);之前或throw std::logic_error{};/ __builtin_unreachable();而不是最后添加,那将是最好的return.如果有相应的逻辑保证,我才能做到.我可以这样做吗？