On Wednesday, 18 May 2016 at 19:54:19 UTC, Andrei Alexandrescu
wrote:
...
No worries. Please take anything you need from there for your
code, make it better, and contribute it back to the stdlib! --
Andrei
As it turns out, easier said than done. I've been thinking about
it for a few days now but I don't see a simple way to optimally
merge the two techniques. The way that I alternate between
iterating "lo" and "hi" (or lef/rig in my code) doesn't really
work when you need to keep the iterator stationary until
something fills the vacancy.
This is the best solution I have so far and it doesn't feel like
a good solution at that:
for (;;)
{
++lo;
for (;;)
{
if(r[lo] < p) ++lo; else break;
if(r[lo] <= p) ++lo; else break;
}
if(lo > hi) lo = hi;
r[hi] = r[lo];
--hi;
for (;;)
{
if(p < r[hi]) --hi; else break;
if(p <= r[hi]) --hi; else break;
}
if(lo >= hi) break;
r[lo] = r[hi];
}
The idea is simple: alternate the check for equality in hopes of
skipping some equal elements. Unfortunately, this modification
requires a little more work and TWO sentinels at either end of
the range because it may skip over the first.
In most real-world data, there's only marginal gains to be made
in skipping over equal elements, too small to justify
compromising the gains achieved by using sentinels and vacancies.
So unless an optimal solution exists, it's just not worth it.
