How to use lowerBound and upperBound effectively?
A. Bressan
invalid at nospam.donotuse
Tue Jul 2 09:27:52 UTC 2019
Hi, I am translating the following C++ code to D and I have some
trouble to achieve it using ranges.
#include <vector>
#include <algorithm>
typedef std::vector<int>::const_iterator iter;
std::pair<iter,iter> getSubVector(iter beg, iter end, int val,
int shift)
{
return {std::upper_bound(beg,end,val)-shift,end};
}
My best result is the following convoluted code, is there a
better way?
auto getSubVector(T)(const ref T vec, int val, int shift)
if (isInstanceOf!(SortedRange, T))
{
auto
begin=vec.length-assumeSorted!"a>b"(retro(vec)).lowerBound().length-shift;
return vec[begin..$];
}
The difficulty I have is that, contrary to C++, lowerBound and
upperBound give the same piece of information because they return
complementary sub-ranges.
To get the elements that are equal to val outside of the
upperBound I need to reverse the range.
I tried to use lowerBound on a range sorted by "a<=b", but it
triggers an error that does not seem to be relevant to binary
search strategies:
std/algorithm/sorting.d(178): Predicate for isSorted is not
antisymmetric. Both pred(a, b) and pred(b, a) are true for
certain values.
More information about the Digitalmars-d-learn
mailing list