www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - What about putting array.empty in object.d?

reply "Nick Sabalausky" <a a.a> writes:
Hear me out... ;)

Using empty seems to be emerging as the recommended practice for testing 
whether an array is empty. And that makes sense as it's consistent with 
other ranges. I'm all in favor of that.

But I've found myself avoiding empty (and instead doing arr=="" or checking 
the .length) just because empty doesn't work on arrays unless you've already 
imported std.array (unless my knowledge is out-of-date, which is possible 
considering how fast things are moving ;) ). So doing "arr.empty" is a 
little messy and increases my cognitive load, whereas arr=="", arr==[], and 
arr.length == 0, "just work".

Considering that:

1. Arrays are (from the user's perspective) a built-in type that doesn't 
need to be explicitly imported.

2. Calling 'empty' is (for good reason) the recommended standard practice 
for checking if arrays are empty.

...Perhaps it would make sense for empty(T)(T[] a) to be moved into 
object.d, or at least somewhere it will always be implicitly included? Being 
a standard part of arrays and input ranges already effectively elevates 
"empty" to a relatively special status anyway.
Mar 20 2012
next sibling parent Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
On 3/21/12, Nick Sabalausky <a a.a> wrote:
 Hear me out... ;)

Man I would say the same thing about write() functions. I've missed importing std.stdio so many times. It doesn't help that the compiler happily asks me if I've missed an import to std.stdio. But I digress.. I use .length all the time. I also use them on hashes and it sucks that .empty isn't defined for them (it's not in std.array).
Mar 20 2012
prev sibling next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Wed, Mar 21, 2012 at 05:27:01AM +0100, Andrej Mitrovic wrote:
 On 3/21/12, Nick Sabalausky <a a.a> wrote:
 Hear me out... ;)

Man I would say the same thing about write() functions. I've missed importing std.stdio so many times. It doesn't help that the compiler happily asks me if I've missed an import to std.stdio. But I digress.. I use .length all the time. I also use them on hashes and it sucks that .empty isn't defined for them (it's not in std.array).

Good point! I'll have to add .empty to my AA implementation. ;-) T -- A computer doesn't mind if its programs are put to purposes that don't match their names. -- D. Knuth
Mar 20 2012
prev sibling next sibling parent reply "Daniel Murphy" <yebblies nospamgmail.com> writes:
FWIW, I would rather see `if (array)` translated to `if (array.length)` and 
this become the recomended way to check if an array is empty.  Wouldn't that 
remove the dependency on std.array for most of the cases? 
Mar 20 2012
next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 21 Mar 2012 00:54:51 -0400, Daniel Murphy  
<yebblies nospamgmail.com> wrote:

 FWIW, I would rather see `if (array)` translated to `if (array.length)`  
 and
 this become the recomended way to check if an array is empty.  Wouldn't  
 that
 remove the dependency on std.array for most of the cases?

+1 -Steve
Mar 21 2012
prev sibling next sibling parent "Xinok" <xinok live.com> writes:
On Wednesday, 21 March 2012 at 04:54:54 UTC, Daniel Murphy wrote:
 FWIW, I would rather see `if (array)` translated to `if 
 (array.length)` and
 this become the recomended way to check if an array is empty.  
 Wouldn't that
 remove the dependency on std.array for most of the cases?

Nope. .length is a requirement for finite random-access ranges, but not for forward or bidirectional ranges. .empty is the only primitive required by all input ranges. So if you pass an array to a function expecting a forward range, it may not work if the primitive .empty doesn't exist.
Mar 21 2012
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 21 Mar 2012 11:50:46 -0400, Xinok <xinok live.com> wrote:

 On Wednesday, 21 March 2012 at 04:54:54 UTC, Daniel Murphy wrote:
 FWIW, I would rather see `if (array)` translated to `if (array.length)`  
 and
 this become the recomended way to check if an array is empty.  Wouldn't  
 that
 remove the dependency on std.array for most of the cases?

Nope. .length is a requirement for finite random-access ranges, but not for forward or bidirectional ranges. .empty is the only primitive required by all input ranges. So if you pass an array to a function expecting a forward range, it may not work if the primitive .empty doesn't exist.

from std/range.d: module std.range; public import std.array; -Steve
Mar 21 2012
prev sibling next sibling parent reply "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Wednesday, March 21, 2012 15:54:51 Daniel Murphy wrote:
 FWIW, I would rather see `if (array)` translated to `if (array.length)` and
 this become the recomended way to check if an array is empty. Wouldn't that
 remove the dependency on std.array for most of the cases?

The problem with checking whether length == 0 is that it's inefficient for some containers, so it's generally good practice to use empty rather than length. And while length == 0 is fine for arrays, it promotes bad habits in general, so I'm against it and think that code should pretty much always use empty rather than length == 0. if(array) is a bit different, because you're not specifically checking the length, but if(container) doesn't work in the general case, and stuff like if(array || cond) doesn't work. So, making if(array) be equivalent to if(array.length != 0) and if(!array.empty) rather than if(array !is null) may be a good idea, but it doesn't work in the general case. In the general case, you're still going to have to choose between length == 0 and empty, and I definitely think that empty is the correct choice, because it promotes good habits, whereas length == 0 promotes bad habits. So, there's value in putting empty in _object.d regardless of what happens with if. Now, I find that I use enough other stuff in std.array, that it always gets imported anyway, but I don't think that putting empty in _object.d is a bad idea. - Jonathan M Davis
Mar 21 2012
parent "Nick Sabalausky" <a a.a> writes:
"Steven Schveighoffer" <schveiguy yahoo.com> wrote in message 
news:op.wbjc7au8eav7ka localhost.localdomain...
 I don't see why defining empty in object.d is necessary for things that 
 don't involve ranges at all.

But arrays *are* ranges. Or at least they're supposed to be.
 Any time you import a container, it's going to import std.range, which 
 publicly imports std.array.

Arrays and AAs *are* containers, but you *don't* import them.
 Bottom line: if you don't care about ranges, if(array) works just fine 
 (checks if length != 0).  If you care about ranges, you are going to be 
 importing std.range and therefore std.array, and array.empty works just as 
 well.

Yes, but a better bottom line would be: If you want to check if something has no elements, use "empty". Period. Done. Why should it even matter whether it's an array vs some other range? Why can't checking for empty be standardized and consistent? It's a simple and fundamental enough concept.
 As an bonus this gets rid of the controversial behavior of if(array) 
 translating to if(array.ptr).

Yea, I'm not *necessarily* opposed to "if(array)" translating to "if(array.length != 0)" (athough it would break code that relies on the "null vs empty" distinction), but I don't think it's an adequate substitute for array's range-style interface being available whenever arrays are available (ie, always).
Mar 21 2012
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 21 Mar 2012 14:33:58 -0400, Jonathan M Davis <jmdavisProg gmx.com>  
wrote:

 On Wednesday, March 21, 2012 15:54:51 Daniel Murphy wrote:
 FWIW, I would rather see `if (array)` translated to `if (array.length)`  
 and
 this become the recomended way to check if an array is empty. Wouldn't  
 that
 remove the dependency on std.array for most of the cases?

The problem with checking whether length == 0 is that it's inefficient for some containers, so it's generally good practice to use empty rather than length.

But we are specifically talking about arrays, not containers in general. Containers in general are not defined by the language.
 And while length == 0 is fine for arrays, it promotes bad habits in  
 general, so
 I'm against it and think that code should pretty much always use empty  
 rather
 than length == 0.

I think you may misunderstand the proposal. if(array) translating to if(array.length) is *only* for arrays, not for general types. I don't see why defining empty in object.d is necessary for things that don't involve ranges at all. Any time you import a container, it's going to import std.range, which publicly imports std.array. Bottom line: if you don't care about ranges, if(array) works just fine (checks if length != 0). If you care about ranges, you are going to be importing std.range and therefore std.array, and array.empty works just as well. As an bonus this gets rid of the controversial behavior of if(array) translating to if(array.ptr). -Steve
Mar 21 2012
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 21 Mar 2012 16:21:21 -0400, Nick Sabalausky <a a.a> wrote:

 "Steven Schveighoffer" <schveiguy yahoo.com> wrote in message
 news:op.wbjc7au8eav7ka localhost.localdomain...
 I don't see why defining empty in object.d is necessary for things that
 don't involve ranges at all.

But arrays *are* ranges. Or at least they're supposed to be.

They can be. But the language doesn't define them as ranges, phobos does. In order to use arrays as ranges, I have to import std.range or std.array.
 Any time you import a container, it's going to import std.range, which
 publicly imports std.array.

Arrays and AAs *are* containers, but you *don't* import them.

What I meant is any container that defines ranges. In other words, any time you are going to be using ranges, you import std.range. Which makes array.empty work.
 Bottom line: if you don't care about ranges, if(array) works just fine
 (checks if length != 0).  If you care about ranges, you are going to be
 importing std.range and therefore std.array, and array.empty works just  
 as
 well.

Yes, but a better bottom line would be: If you want to check if something has no elements, use "empty". Period. Done.

We have defined range interface requirements. If we want to define .empty for everything other than ranges which can contain things, we can, but it's not done already. If we wanted to do that, then I agree array.empty should go into object.d.
 As an bonus this gets rid of the controversial behavior of if(array)
 translating to if(array.ptr).

Yea, I'm not *necessarily* opposed to "if(array)" translating to "if(array.length != 0)" (athough it would break code that relies on the "null vs empty" distinction)

We have discussed ways of introducing this in the least painful way. I think it should happen, no matter what the pain, since it's the least obvious choice.
 but I don't think it's an adequate substitute
 for array's range-style interface being available whenever arrays are
 available (ie, always).

This goes a step further, saying all the range-style interfaces for arrays should go into object. I certainly don't agree with that. -Steve
Mar 21 2012
prev sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 21 Mar 2012 16:43:28 -0400, Steven Schveighoffer  
<schveiguy yahoo.com> wrote:

 On Wed, 21 Mar 2012 16:21:21 -0400, Nick Sabalausky <a a.a> wrote:

 "Steven Schveighoffer" <schveiguy yahoo.com> wrote in message
 news:op.wbjc7au8eav7ka localhost.localdomain...
 As an bonus this gets rid of the controversial behavior of if(array)
 translating to if(array.ptr).

Yea, I'm not *necessarily* opposed to "if(array)" translating to "if(array.length != 0)" (athough it would break code that relies on the "null vs empty" distinction)

We have discussed ways of introducing this in the least painful way. I think it should happen, no matter what the pain, since it's the least obvious choice.

What I mean is the *current behavior* is the least obvious choice :D -Steve
Mar 21 2012
prev sibling next sibling parent reply Jacob Carlborg <doob me.com> writes:
On 2012-03-21 04:54, Nick Sabalausky wrote:
 Hear me out... ;)

 Using empty seems to be emerging as the recommended practice for testing
 whether an array is empty. And that makes sense as it's consistent with
 other ranges. I'm all in favor of that.

 But I've found myself avoiding empty (and instead doing arr=="" or checking
 the .length) just because empty doesn't work on arrays unless you've already
 imported std.array (unless my knowledge is out-of-date, which is possible
 considering how fast things are moving ;) ). So doing "arr.empty" is a
 little messy and increases my cognitive load, whereas arr=="", arr==[], and
 arr.length == 0, "just work".

 Considering that:

 1. Arrays are (from the user's perspective) a built-in type that doesn't
 need to be explicitly imported.

 2. Calling 'empty' is (for good reason) the recommended standard practice
 for checking if arrays are empty.

 ...Perhaps it would make sense for empty(T)(T[] a) to be moved into
 object.d, or at least somewhere it will always be implicitly included? Being
 a standard part of arrays and input ranges already effectively elevates
 "empty" to a relatively special status anyway.

Sure, why not. Do we want an "any" function as well, that is the opposite? -- /Jacob Carlborg
Mar 21 2012
parent reply "Nick Sabalausky" <a a.a> writes:
"Jacob Carlborg" <doob me.com> wrote in message 
news:jkc321$25pv$1 digitalmars.com...
 On 2012-03-21 04:54, Nick Sabalausky wrote:
 Hear me out... ;)

 Using empty seems to be emerging as the recommended practice for testing
 whether an array is empty. And that makes sense as it's consistent with
 other ranges. I'm all in favor of that.

 But I've found myself avoiding empty (and instead doing arr=="" or 
 checking
 the .length) just because empty doesn't work on arrays unless you've 
 already
 imported std.array (unless my knowledge is out-of-date, which is possible
 considering how fast things are moving ;) ). So doing "arr.empty" is a
 little messy and increases my cognitive load, whereas arr=="", arr==[], 
 and
 arr.length == 0, "just work".

 Considering that:

 1. Arrays are (from the user's perspective) a built-in type that doesn't
 need to be explicitly imported.

 2. Calling 'empty' is (for good reason) the recommended standard practice
 for checking if arrays are empty.

 ...Perhaps it would make sense for empty(T)(T[] a) to be moved into
 object.d, or at least somewhere it will always be implicitly included? 
 Being
 a standard part of arrays and input ranges already effectively elevates
 "empty" to a relatively special status anyway.

Sure, why not. Do we want an "any" function as well, that is the opposite?

I think "!array.empty" is plenty sufficient. Besides, there are other good uses of "any" that have been brought up before.
Mar 21 2012
next sibling parent reply Jacob Carlborg <doob me.com> writes:
On 2012-03-21 09:42, Nick Sabalausky wrote:
 "Jacob Carlborg"<doob me.com>  wrote in message
 Sure, why not. Do we want an "any" function as well, that is the opposite?

I think "!array.empty" is plenty sufficient. Besides, there are other good uses of "any" that have been brought up before.

Actually I was thinking something like "any?" in Ruby: http://www.ruby-doc.org/core-1.8.7/Enumerable.html#method-i-any-3F -- /Jacob Carlborg
Mar 21 2012
parent reply Jacob Carlborg <doob me.com> writes:
On 2012-03-21 21:49, Jonathan M Davis wrote:
 On Wednesday, March 21, 2012 10:17:08 Jacob Carlborg wrote:
 http://www.ruby-doc.org/core-1.8.7/Enumerable.html#method-i-any-3F

So, std.algorithm.canFind then? There has been some discussion of renaming it to any (or at least the overload that just takes the predicate and the range), but canFind gives you the behavior regardless. - Jonathan M Davis

Yes, I didn't see the overload. But the Ruby version has a default predicate, that does this: canFind!("a")([3, 4, 5]); I'm usually using "any?" to check if an array contains any values. -- /Jacob Carlborg
Mar 21 2012
parent Jacob Carlborg <doob me.com> writes:
On 2012-03-21 23:25, Simen Kjærås wrote:

 I hope you mean canFind!("true")([3, 4, 5]);. canFind!"a" fails for
 arrays where all elements are 0.

Yes. I'm not really familiar with canFind or std.algorithms in general. -- /Jacob Carlborg
Mar 25 2012
prev sibling next sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Wednesday, March 21, 2012 10:17:08 Jacob Carlborg wrote:
 On 2012-03-21 09:42, Nick Sabalausky wrote:
 "Jacob Carlborg"<doob me.com> wrote in message
 
 Sure, why not. Do we want an "any" function as well, that is the
 opposite?

I think "!array.empty" is plenty sufficient. Besides, there are other good uses of "any" that have been brought up before.

Actually I was thinking something like "any?" in Ruby: http://www.ruby-doc.org/core-1.8.7/Enumerable.html#method-i-any-3F

So, std.algorithm.canFind then? There has been some discussion of renaming it to any (or at least the overload that just takes the predicate and the range), but canFind gives you the behavior regardless. - Jonathan M Davis
Mar 21 2012
prev sibling parent =?utf-8?Q?Simen_Kj=C3=A6r=C3=A5s?= <simen.kjaras gmail.com> writes:
On Wed, 21 Mar 2012 22:30:17 +0100, Jacob Carlborg <doob me.com> wrote:

 On 2012-03-21 21:49, Jonathan M Davis wrote:
 On Wednesday, March 21, 2012 10:17:08 Jacob Carlborg wrote:
 http://www.ruby-doc.org/core-1.8.7/Enumerable.html#method-i-any-3F

So, std.algorithm.canFind then? There has been some discussion of renaming it to any (or at least the overload that just takes the predicate and the range), but canFind gives you the behavior regardless. - Jonathan M Davis

Yes, I didn't see the overload. But the Ruby version has a default predicate, that does this: canFind!("a")([3, 4, 5]); I'm usually using "any?" to check if an array contains any values.

I hope you mean canFind!("true")([3, 4, 5]);. canFind!"a" fails for arrays where all elements are 0.
Mar 21 2012
prev sibling next sibling parent reply "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Wednesday, March 21, 2012 15:46:12 Steven Schveighoffer wrote:
 On Wed, 21 Mar 2012 14:33:58 -0400, Jonathan M Davis <jmdavisProg gmx.com>
 
 wrote:
 On Wednesday, March 21, 2012 15:54:51 Daniel Murphy wrote:
 FWIW, I would rather see `if (array)` translated to `if (array.length)`
 and
 this become the recomended way to check if an array is empty. Wouldn't
 that
 remove the dependency on std.array for most of the cases?

The problem with checking whether length == 0 is that it's inefficient for some containers, so it's generally good practice to use empty rather than length.

But we are specifically talking about arrays, not containers in general. Containers in general are not defined by the language.

I know that. Much point is that length == 0 is a bad thing to do in general, because it's ineffecient with some containers. The language itself is pretty much irrelevant as far as that goes. As such, I'd argue in pretty much _any_ language that using length == 0 instead of empty is _not_ a good habit to be in. Doing it with arrays will make it much more likely that you'll end up doing it with containers without thinking about it. On the other hand, if you're in the habit of _always_ using empty rather than length == 0, then you don't have the problem.
 And while length == 0 is fine for arrays, it promotes bad habits in
 general, so
 I'm against it and think that code should pretty much always use empty
 rather
 than length == 0.

I think you may misunderstand the proposal. if(array) translating to if(array.length) is *only* for arrays, not for general types.

No. I understand just fine. My point is that doing length == 0 for _any_ type of container is bad, because it promotes bad habits and leads to inefficient code for containers where it _does_ matter. So, I'd argue that if you should always be using empty rather than length == 0 - even with arrays - which currently means that you're almost always importing std.array. Having empty in object.d certainly isn't necessary, but it mitigates the problem, because then you don't have to import it if all you care about is empty. if(array) is a special case. If we want to change it to translate to if(array.length) then fine. That's all tied up in the insanity of an empty array and a null array being considered equal. But even if you want to use that syntax, it only mitigates the length == 0 vs empty issue for arrays rather than eliminating, because it only works directly in if statements and the like. The issue of choosing length == 0 vs empty still remains in many cases. And actually, I'd personally shy away from the if(array) syntax regardless simply because of the inherent ambiguity. Even if the language clearly defines it, I believe that it's the sort of thing that programmers are likely to misunderstand - particularly since if(var) checks for null with all of the other reference types. Experienced D programmers will know, but since newbies probably won't I'd consider it a code smell. I think that muddling null and empty was D's largest mistake with arrays and tend to think that any code that isn't explicit about it is asking for trouble if nothing else because the odds aren't low that the programmer did one thing when they meant another, because they didn't understand how null and empty arrays interact (e.g. arr == null is _always_ a bad sign IMHO).
 I don't see why defining empty in object.d is necessary for things that
 don't involve ranges at all.

It's not necessary, but it would be nice. empty isn't just a range thing. Containers in general use it (across many languages whether ranges are involved or not), and for the reasons that I've already given, I don't think that length == 0 should ever be used in code. So I'd argue that you should always be using empty, which means importing std.array all the time if empty isn't in object.d, even if you _aren't_ doing range-based operations. Now, range-based operations are so common that you pretty much have to import std.range in most code anyway, so it really isn't all that much of a burden to have to import std.array or std.range to get at empty, but putting it in object.d definitely provides some benefit. So, I'm not sure that I care all that much whether std.array.empty gets moved to object.d or not, but I'd strongly argue that code should import std.array and use it rather than checking length == 0 as long as empty is in std.array rather than in object.d. So, if putting empty in object.d promotes the use of empty over length == 0, I'm all for it. - Jonathan M Davis
Mar 21 2012
parent reply "Daniel Murphy" <yebblies nospamgmail.com> writes:
"Jonathan M Davis" <jmdavisProg gmx.com> wrote in message 
news:mailman.985.1332364578.4860.digitalmars-d puremagic.com...
 I know that. Much point is that length == 0 is a bad thing to do in 
 general,
 because it's ineffecient with some containers. The language itself is 
 pretty
 much irrelevant as far as that goes. As such, I'd argue in pretty much 
 _any_
 language that using length == 0 instead of empty is _not_ a good habit to 
 be
 in. Doing it with arrays will make it much more likely that you'll end up
 doing it with containers without thinking about it. On the other hand, if
 you're in the habit of _always_ using empty rather than length == 0, then 
 you
 don't have the problem.

Yes, .length is inefficient on some containers... but so is indexing. That doesn't mean using indexing on arrays is a bad habit. If you're writing general code for ranges, you are going to have to use the range interface. But when you're writing code for arrays only, you can take advantage of the fact that indexing is O(1), length is O(1), slicing is O(1) etc. I'm not even advocating using arr.length == 0 to check for empty. Just use `if (!arr)`.
Mar 21 2012
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 3/21/12 6:56 PM, Jonathan M Davis wrote:
 Except that containers shouldn't provide indexing if it's not efficient. And
 from what I've seen, it's far too common for programmers to check length == 0,
 and they end up doing it on stuff like linked lists where it _is_ inefficient.
 It's considered good practice in C++ to use empty rather than length for
 exactly the reasons that I've listed. D is no different in this regard.

In D it's poor style to define linear-time length. That's called walkLength. Andrei
Mar 21 2012
prev sibling next sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Thursday, March 22, 2012 10:39:23 Daniel Murphy wrote:
 "Jonathan M Davis" <jmdavisProg gmx.com> wrote in message
 news:mailman.985.1332364578.4860.digitalmars-d puremagic.com...
 
 I know that. Much point is that length == 0 is a bad thing to do in
 general,
 because it's ineffecient with some containers. The language itself is
 pretty
 much irrelevant as far as that goes. As such, I'd argue in pretty much
 _any_
 language that using length == 0 instead of empty is _not_ a good habit to
 be
 in. Doing it with arrays will make it much more likely that you'll end up
 doing it with containers without thinking about it. On the other hand, if
 you're in the habit of _always_ using empty rather than length == 0, then
 you
 don't have the problem.

Yes, .length is inefficient on some containers... but so is indexing. That doesn't mean using indexing on arrays is a bad habit.

Except that containers shouldn't provide indexing if it's not efficient. And from what I've seen, it's far too common for programmers to check length == 0, and they end up doing it on stuff like linked lists where it _is_ inefficient. It's considered good practice in C++ to use empty rather than length for exactly the reasons that I've listed. D is no different in this regard.
 If you're writing general code for ranges, you are going to have to use the
 range interface. But when you're writing code for arrays only, you can take
 advantage of the fact that indexing is O(1), length is O(1), slicing is
 O(1) etc.

True, but save for length, those should all be O(1) (or at maybe O(log n) at the worst). So, save for length, those operations are supposed to be efficient for _any_ container. And yes, you can do whatever you want with arrays without regard for other containers if you want to. My point is that if you're in the habit of using length == 0, you'll end up using it with stuff _other_ than arrays - including containers where it's very inefficient. It doesn't help that it seems to be many programmers' natural instinct to check whether a container's length is 0 rather than checking whether it's empty. Using empty rather than length == 0 is all about getting into the habit of doing things the efficient way so that you don't have to think about it, and you're less likely to make mistakes. It's the same as why you should always use the pre-increment operator in C++ if it doesn't matter whether you use pre-increment or post-increment (D's design was smart enough to avoid the problem). It's a habit which doesn't cost you anything and promotes efficient code. But length == 0 is far worse, because it can result in an operation costing O(n) instead of O(1) rather than having a constant cost added to it.
 I'm not even advocating using arr.length == 0 to check for empty. Just use
 `if (!arr)`.

I don't like that either, because of the potential ambiguity for newbies (given the whole null vs empty mess and the fact that if(var) checks for null with all other reference types), but at least that's not going to cost you anything in terms of efficiency, whereas if you're in the habit of always using length == 0, you're likely to use it when it would really cost you. So, if(arr) is more of a style choice and is more debatable, I think, whereas I'd consider the issue of length == 0 vs empty to be more black and white. - Jonathan M Davis
Mar 21 2012
prev sibling next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 21 Mar 2012 19:56:41 -0400, Jonathan M Davis <jmdavisProg gmx.com>  
wrote:


 Except that containers shouldn't provide indexing if it's not efficient.  
 And
 from what I've seen, it's far too common for programmers to check length  
 == 0,
 and they end up doing it on stuff like linked lists where it _is_  
 inefficient.

Wait, if someone provides inefficient length, what makes you think they won't provide inefficient indexing? -Steve
Mar 21 2012
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 3/21/12 7:53 PM, Jonathan M Davis wrote:
 Actually, it looks like std.container _does_ guarantee that length is O(1),
 unlike C++'s STL, in which case it's not the same issue that it is in C++.

Here we learned from a small mistake of C++. (BTW it's O(log n).) Andrei
Mar 21 2012
prev sibling next sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Wednesday, March 21, 2012 20:17:06 Steven Schveighoffer wrote:
 On Wed, 21 Mar 2012 19:56:41 -0400, Jonathan M Davis <jmdavisProg gmx.com>
 
 wrote:
 Except that containers shouldn't provide indexing if it's not efficient.
 And
 from what I've seen, it's far too common for programmers to check length
 == 0,
 and they end up doing it on stuff like linked lists where it _is_
 inefficient.

Wait, if someone provides inefficient length, what makes you think they won't provide inefficient indexing?

Both C++'s STL and D's std.container put requirements on the algorithmic complexity of various operations. O(n) indexing would violate them, whereas they allow O(n) length/size. So, as long as you use standard containers, you can rely on the efficiency of indexing but not that of length/size. And I'd argue that 3rd party containers which violate those algorithmic requirements are generally doing something wrong (possibly with some exceptions for specific situations but not in general). So, as long as you use standard containers, it's a non-issue. And if you're dealing with a 3rd party library that doesn't provide appropriate algorithmic guarantees for its containers, you should probably rethink using it. It _is_ true that some languages and libraries are completely idiotic about it though (e.g. Java providing a get function to LinkedList which takes an index - which would be the equivalent of providing horribly efficient indexing if they had operator overloading in Java). Those are broken APIs IMHO though, in which case, you must tread carefully. Well-designed libraries _do_ guarantee efficient indexing. - Jonathan M Davis
Mar 21 2012
prev sibling next sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Wednesday, March 21, 2012 20:46:05 Jonathan M Davis wrote:
 On Wednesday, March 21, 2012 20:17:06 Steven Schveighoffer wrote:
 On Wed, 21 Mar 2012 19:56:41 -0400, Jonathan M Davis <jmdavisProg gmx.com>
 
 wrote:
 Except that containers shouldn't provide indexing if it's not efficient.
 And
 from what I've seen, it's far too common for programmers to check length
 == 0,
 and they end up doing it on stuff like linked lists where it _is_
 inefficient.

Wait, if someone provides inefficient length, what makes you think they won't provide inefficient indexing?

Both C++'s STL and D's std.container put requirements on the algorithmic complexity of various operations. O(n) indexing would violate them, whereas they allow O(n) length/size.

Actually, it looks like std.container _does_ guarantee that length is O(1), unlike C++'s STL, in which case it's not the same issue that it is in C++. I'd still tend to argue that checking for empty is better, but I guess that it's not as big a deal. In C++, it's a definite problem when programmers keep checking that size() == 0, since inevitably, it ends up happening with linked lists and the like, making for inefficient code, and simply being in the habit of using empty() rather than size() == 0 avoids such problems. - Jonathan M Davis
Mar 21 2012
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Wednesday, March 21, 2012 21:12:36 Andrei Alexandrescu wrote:
 On 3/21/12 7:53 PM, Jonathan M Davis wrote:
 Actually, it looks like std.container _does_ guarantee that length is
 O(1), unlike C++'s STL, in which case it's not the same issue that it
 is in C++.


Yes. It looks that way. I'd forgotten that length had better guarantees in D than in C++.
 (BTW it's O(log n).)

What's O(log n)? length in D? According to std.container, it's supposed to be O(1). - Jonathan M Davis
Mar 21 2012
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 21 Mar 2012 20:53:42 -0400, Jonathan M Davis <jmdavisProg gmx.com>  
wrote:

 On Wednesday, March 21, 2012 20:46:05 Jonathan M Davis wrote:
 On Wednesday, March 21, 2012 20:17:06 Steven Schveighoffer wrote:
 On Wed, 21 Mar 2012 19:56:41 -0400, Jonathan M Davis  

 wrote:
 Except that containers shouldn't provide indexing if it's not  


 And
 from what I've seen, it's far too common for programmers to check  


 == 0,
 and they end up doing it on stuff like linked lists where it _is_
 inefficient.

Wait, if someone provides inefficient length, what makes you think

 won't provide inefficient indexing?

Both C++'s STL and D's std.container put requirements on the algorithmic complexity of various operations. O(n) indexing would violate them, whereas they allow O(n) length/size.

Actually, it looks like std.container _does_ guarantee that length is O(1), unlike C++'s STL, in which case it's not the same issue that it is in C++. I'd still tend to argue that checking for empty is better, but I guess that it's not as big a deal. In C++, it's a definite problem when programmers keep checking that size() == 0, since inevitably, it ends up happening with linked lists and the like, making for inefficient code, and simply being in the habit of using empty() rather than size() == 0 avoids such problems.

Yes, that was my point. Note that the default std::list has O(1) length (as does dcollections' LinkedList). It's not as inevitable as you think. -Steve
Mar 22 2012
prev sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Thursday, March 22, 2012 07:12:22 Steven Schveighoffer wrote:
 Note that the default std::list has O(1) length (as does dcollections'
 LinkedList). It's not as inevitable as you think.

It depends on bothe container its implementation as to how efficient length/size is (and in the case of linked lists, it's generally a question of whether you want splicing to be efficient or size/length to be efficient). But you don't have to worry about how efficient length/size's implementation is when checking whether a container is empty if you just always use empty rather than length == 0, so it's a good habit to get into. There's generally no advantage to using length == 0 over empty. There's a slight advantage with D and arrays only in that empty isn't built into arrays, so you have to import std.array to use empty, and empty is just a wrapper around length == 0, which will then be _slightly_ less efficient without -inline, but I'd still argue for using empty, because it avoids the whole issue of length/size's efficiency. Regardless, fortunately, it's not as big an issue in D as in C++ thanks to the fact that Phobos defines length to be O(1) - and it's good that dcollections does the same. - Jonathan M Davis
Mar 22 2012