On 11/07/2014 06:11 AM, bearophile wrote:
(This is a partial repost from a recent D.learn thread.)In Phobos we have SortedRange and assumeSorted, but I do find them not very good for a common enough use case. The use case is to keep a sorted array, keep adding items to it (adding larger and larger items at the end. Or sometimes even inserting items in the middle. In both cases I keep the sorting invariant). And while I add items, I also now and then want to perform a binary search on the sorted range. So sometimes I'd like to do something like this (but a SortedRange doesn't have append): struct Foo { int x; } SortedRange!(Foo[], q{ a.x < b.x }) data; data ~= Foo(5); immutable n = data.upperBound(Foo(2)).length; Bye, bearophile
If an array is sorted every time an element is added, then insertion is N.log(N) and searching is log(N). I don't know when that penalty is better than data locality that an array brings.
A more traditional data structure is a binary tree in this case because it has log(N) for both insertion and search.
On the other hand, array wins if the insertions are batched and then there is a single sort before many searches. As Max Klyga said, that single sort better be applied on the container, not on the range.
Ali
