[erlang-questions] Ordered set with lower_bound

Igor Ribeiro Sucupira <>
Fri Oct 9 02:05:10 CEST 2009


Hello.

Indeed, I "have hoped for O (1) after the first O (log N) call".

But, thinking again at my case, I don't really need the iterator.
Given a key K, I believe it will be enough to find the smallest key
that is greater or equals K.
So, ets:lookup/2, maybe followed by ets:next/2, would do.

Thanks for the answers.
Igor.

On Thu, Oct 8, 2009 at 8:32 PM, Paul Mineiro <> wrote:
> On Thu, 8 Oct 2009, Igor Ribeiro Sucupira wrote:
>
>> Hi.
>>
>> I need some ordered set that allows me to "search and then iterate"
>> efficiently. In other words, I need this functionality:
>> http://www.cplusplus.com/reference/stl/set/lower_bound/
>>
>> After looking at the documentation for gb_sets and ordsets, I have
>> concluded that Erlang does not provide that functionality and I'll
>> have to roll my own. Is it the right conclusion?  :-)
>
> ets:next/2 on an ordered_set table acts like that.  "efficiently" ...
> well, it'll be O (log N) per call, you might have hoped for O (1) after
> the first O (log N) call.  also you might not like the constant factors.
> benchmark to be sure.
>
> -- p
>
> p.z. perhaps ets:slot/2 is faster?
>
> ________________________________________________________________
> erlang-questions mailing list. See http://www.erlang.org/faq.html
> erlang-questions (at) erlang.org
>
>



-- 
"The secret of joy in work is contained in one word - excellence. To
know how to do something well is to enjoy it." - Pearl S. Buck.


More information about the erlang-questions mailing list