I want to insert a new (unique) element in a known place (usually somewhere in the middle) of the ordered associative container std::set / std::multiset / std::map / std::multimap using insert (w / hint)) or emplace_hint .
During the input operation, I’m absolutely sure that the place to insert is right in front of the prompt tool iterator. Usually I can compare any two neighboring elements in the container, but this operation is very heavy. To avoid overhead, I provide a custom comparator for the container that contains references to pointers to both neighboring elements (they always became known immediately before the insert / place operation).
#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'; }
Current libC ++ / libstdC ++ implementations allow you to use the described comparator, but is there undefined behavior if I rely on their current behavior? Can I rely that insert (the w / hint parameter) or emplace_hint (and the modern insert_or_assign / try_emplace w / hint parameter for map / multimap ) do not touch elements other than pl and pr ? Is this an implementation?
Why do I want this strange thing? IRL I tried to implement the Fortune algorithm to find the Voronoi diagram on the plane using my own self-established binary STL lookup attempts. std::set used to store the current state of a part of the so-called coastline: a chain of sorted endpoints. When I add a new endpoint, I always know where to insert it right before insertion. It would be better if I could add assert(false); earlier or throw std::logic_error{}; / __builtin_unreachable(); instead of the last return in the comparator functor. I can do this only if there is a corresponding logical guarantee. Can I do it?