Ted Kremenek
2009-Feb-11 18:57 UTC
[LLVMdev] Some enhancements to ImmutableSet and FoldingSet
On Feb 11, 2009, at 10:54 AM, Bill Wendling wrote:> On Wed, Feb 11, 2009 at 10:36 AM, Ben Laurie <benl at google.com> wrote: >> I needed these for some work I'm doing in clang... >> > Yes sir! At least this message was informative. One thing: > > + int size() const { > + int n = 0; > + for(iterator i = begin() ; i != end() ; ++n, ++i) > + ; > + return n; > + } > + bool empty() const { > + return size() == 0; > + } > > empty() here isn't a constant-time method. Can you make it's time > complexity O(1)? > > -bwBill's right; empty can be made constant time. e.g., "return Root == 0"; -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20090211/c57eec74/attachment.html>
Ted Kremenek
2009-Feb-11 20:24 UTC
[LLVMdev] Some enhancements to ImmutableSet and FoldingSet
Actually, neither of these methods are needed for ImmutableSet. ImmutableSet already has an 'isEmpty()' method and I have never really seen a case where "size()" needs to be explicitly calculated. If you need size() itself, however, this seems like a perfectly valid addition. On Feb 11, 2009, at 10:57 AM, Ted Kremenek wrote:> > On Feb 11, 2009, at 10:54 AM, Bill Wendling wrote: > >> On Wed, Feb 11, 2009 at 10:36 AM, Ben Laurie <benl at google.com> wrote: >>> I needed these for some work I'm doing in clang... >>> >> Yes sir! At least this message was informative. One thing: >> >> + int size() const { >> + int n = 0; >> + for(iterator i = begin() ; i != end() ; ++n, ++i) >> + ; >> + return n; >> + } >> + bool empty() const { >> + return size() == 0; >> + } >> >> empty() here isn't a constant-time method. Can you make it's time >> complexity O(1)? >> >> -bw > > Bill's right; empty can be made constant time. e.g., "return Root > == 0";-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20090211/5b2664b8/attachment.html>
Chris Lattner
2009-Feb-12 00:50 UTC
[LLVMdev] Some enhancements to ImmutableSet and FoldingSet
On Feb 11, 2009, at 12:24 PM, Ted Kremenek wrote:> Actually, neither of these methods are needed for ImmutableSet. > ImmutableSet already has an 'isEmpty()' method and I have never > really seen a case where "size()" needs to be explicitly > calculated. If you need size() itself, however, this seems like a > perfectly valid addition.I agree, "size" should also return 'unsigned' not int. -Chris
Ben Laurie
2009-Feb-12 04:14 UTC
[LLVMdev] Some enhancements to ImmutableSet and FoldingSet
On Wed, Feb 11, 2009 at 8:24 PM, Ted Kremenek <kremenek at apple.com> wrote:> Actually, neither of these methods are needed for ImmutableSet. > ImmutableSet already has an 'isEmpty()' method and I have never really seen > a case where "size()" needs to be explicitly calculated. If you need size() > itself, however, this seems like a perfectly valid addition.I need to check for size() == 1 (in order to test whether a range set has a single possible value).
Reasonably Related Threads
- [LLVMdev] Some enhancements to ImmutableSet and FoldingSet
- [LLVMdev] Some enhancements to ImmutableSet and FoldingSet
- [LLVMdev] Some enhancements to ImmutableSet and FoldingSet
- [LLVMdev] Some enhancements to ImmutableSet and FoldingSet
- [LLVMdev] Some enhancements to ImmutableSet and FoldingSet