www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Dynamic arrays in D 1.0

reply Edward Diener <eddielee_no_spam_here tropicsoft.com> writes:
In D 1.0 dynamic arrays are the equivalent of C++'s std::vector<T>, with 
slicing replacing iterators in order to access some subrange of the 
sequence. In C++ there is functionality in std::vector::erase for 
erasing elements from the vector and std::vector::insert for inserting 
new elements into the vector. Where is that functionality in D's dynamic 
arrays ?

Furthermore in D 1.0 a char[], a dynamic array of characters, is the 
equivalent of the C++ std::string. In the C++ std::string class there is 
a rich set of functionality for manipulating the char elements in the 
string, for finding particular elements in the string, and for comparing 
the character elements in strings with other strings, but I see little 
of this in dynamic array functionality. What am I missing ?

I am guessing this must be provided in D libraries of functions ( Phobos 
? Tango ? ) templated on the dynamic array type. But, if so, this seems 
a poor way of providing dynamic array functionality as compared to 
built-in dynamic array functionality in order to provide the sort of 
functionality mentioned above, especially as D's dynamic arrays are part 
of the D language as opposed to a separate library like C++'s 
std::vector<T> and std::string.
May 11 2008
next sibling parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Edward Diener wrote:

 In D 1.0 dynamic arrays are the equivalent of C++'s std::vector<T>, with 
 slicing replacing iterators in order to access some subrange of the 
 sequence. In C++ there is functionality in std::vector::erase for 
 erasing elements from the vector and std::vector::insert for inserting 
 new elements into the vector. Where is that functionality in D's dynamic 
 arrays ?


Yes, erase & insert and many other things are conspicuously missing from 
D1 Phobos (not sure about D2 Phobos).  I like the collection of such 
routines provided by the Cashew library in the cashew.utils.Array module.


 Furthermore in D 1.0 a char[], a dynamic array of characters, is the 
 equivalent of the C++ std::string. In the C++ std::string class there is 
 a rich set of functionality for manipulating the char elements in the 
 string, for finding particular elements in the string, and for comparing 
 the character elements in strings with other strings, but I see little 
 of this in dynamic array functionality. What am I missing ?


Those functions are in std.string in Phobos.  And scattered all over the 
place in Tango.


 I am guessing this must be provided in D libraries of functions ( Phobos 
 ? Tango ? ) templated on the dynamic array type. 


Right.  Except for generic arrays, there's nothing in D1 Phobos.


 But, if so, this seems 
 a poor way of providing dynamic array functionality as compared to 
 built-in dynamic array functionality in order to provide the sort of 
 functionality mentioned above, especially as D's dynamic arrays are part 
 of the D language as opposed to a separate library like C++'s 
 std::vector<T> and std::string.


Why?  What's wrong with providing such functionality as a library when a 
library does the trick?

Are you aware of the pseudo-member trick that works for arrays?  Example:

   T get_elem(T)(T[] array, size_t idx) {
      return array[idx];
   }
   ...
   float[] numbers = [1.f, 2,3];
   float first = numbers.get_elem(0);

That works today in D1 and D2.  Any function that takes an array as a 
first element can be treated as if it were a (non-virtual) member of the 
array type.

So given that, I think there's really no reason for the bulk of D's 
array functionality to not be in a library.

--bb
May 11 2008
next sibling parent Edward Diener <eddielee_no_spam_here tropicsoft.com> writes:
Bill Baxter wrote:

 Edward Diener wrote:

 In D 1.0 dynamic arrays are the equivalent of C++'s std::vector<T>, 
 with slicing replacing iterators in order to access some subrange of 
 the sequence. In C++ there is functionality in std::vector::erase for 
 erasing elements from the vector and std::vector::insert for inserting 
 new elements into the vector. Where is that functionality in D's 
 dynamic arrays ?


 
 Yes, erase & insert and many other things are conspicuously missing from 
 D1 Phobos (not sure about D2 Phobos).  I like the collection of such 
 routines provided by the Cashew library in the cashew.utils.Array module.


OK, I will look it up. I did expect such functionlity to be part of the 
D run-time library or the language implementation itself.


 

 Furthermore in D 1.0 a char[], a dynamic array of characters, is the 
 equivalent of the C++ std::string. In the C++ std::string class there 
 is a rich set of functionality for manipulating the char elements in 
 the string, for finding particular elements in the string, and for 
 comparing the character elements in strings with other strings, but I 
 see little of this in dynamic array functionality. What am I missing ?


 
 Those functions are in std.string in Phobos.  And scattered all over the 
 place in Tango.


I see the Phobos std.string. It seems, at first glance, not nearly as 
rich an implementation as the C++ std::string functionality.


 

 I am guessing this must be provided in D libraries of functions ( 
 Phobos ? Tango ? ) templated on the dynamic array type. 


 
 Right.  Except for generic arrays, there's nothing in D1 Phobos.


This is surprising, but I will go with the link above you suggested.


 

 But, if so, this seems a poor way of providing dynamic array 
 functionality as compared to built-in dynamic array functionality in 
 order to provide the sort of functionality mentioned above, especially 
 as D's dynamic arrays are part of the D language as opposed to a 
 separate library like C++'s std::vector<T> and std::string.


 
 Why?  What's wrong with providing such functionality as a library when a 
 library does the trick?


There is nothing instrinsically wrong with it when the library is 
generic enough, as in the C++ standard algorithms which access 
containers through the iterator concept.


 
 Are you aware of the pseudo-member trick that works for arrays?  Example:
 
   T get_elem(T)(T[] array, size_t idx) {
      return array[idx];
   }
   ...
   float[] numbers = [1.f, 2,3];
   float first = numbers.get_elem(0);
 
 That works today in D1 and D2.  Any function that takes an array as a 
 first element can be treated as if it were a (non-virtual) member of the 
 array type.


Yes I remember seeing this in the documentation but did not appreciate 
its importance vis-a-vis an external dynamic array library.


 
 So given that, I think there's really no reason for the bulk of D's 
 array functionality to not be in a library.


Agreed. Unfortunately I had missed where such a library exists, and 
assumed it must be part of the normal distribution.
May 11 2008
prev sibling parent reply Christopher Wright <dhasenan gmail.com> writes:
Bill Baxter wrote:

 Edward Diener wrote:

 In D 1.0 dynamic arrays are the equivalent of C++'s std::vector<T>, 
 with slicing replacing iterators in order to access some subrange of 
 the sequence. In C++ there is functionality in std::vector::erase for 
 erasing elements from the vector and std::vector::insert for inserting 
 new elements into the vector. Where is that functionality in D's 
 dynamic arrays ?


 
 Yes, erase & insert and many other things are conspicuously missing from 
 D1 Phobos (not sure about D2 Phobos).  I like the collection of such 
 routines provided by the Cashew library in the cashew.utils.Array module.


I've been using tango's HashSet instead, since I don't need ordering. 
How do the Cashew collections compare?


 Furthermore in D 1.0 a char[], a dynamic array of characters, is the 
 equivalent of the C++ std::string. In the C++ std::string class there 
 is a rich set of functionality for manipulating the char elements in 
 the string, for finding particular elements in the string, and for 
 comparing the character elements in strings with other strings, but I 
 see little of this in dynamic array functionality. What am I missing ?


 
 Those functions are in std.string in Phobos.  And scattered all over the 
 place in Tango.


If by 'scattered all over the place' you mean 'most everything suitable 
for all array types is in tango.core.Array and everything else is in 
tango.text.*', yes.
May 12 2008
parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Christopher Wright wrote:

 Bill Baxter wrote:

 Edward Diener wrote:

 In D 1.0 dynamic arrays are the equivalent of C++'s std::vector<T>, 
 with slicing replacing iterators in order to access some subrange of 
 the sequence. In C++ there is functionality in std::vector::erase for 
 erasing elements from the vector and std::vector::insert for 
 inserting new elements into the vector. Where is that functionality 
 in D's dynamic arrays ?


 Yes, erase & insert and many other things are conspicuously missing 
 from D1 Phobos (not sure about D2 Phobos).  I like the collection of 
 such routines provided by the Cashew library in the cashew.utils.Array 
 module.


 
 I've been using tango's HashSet instead, since I don't need ordering. 
 How do the Cashew collections compare?


Oh, Cashew doesn't provide collections.  Cashew.utils.Array is just a 
bunch of functions for working on D's built-in arrays.  Things like 
insert, remove, bisection search, etc.


 Furthermore in D 1.0 a char[], a dynamic array of characters, is the 
 equivalent of the C++ std::string. In the C++ std::string class there 
 is a rich set of functionality for manipulating the char elements in 
 the string, for finding particular elements in the string, and for 
 comparing the character elements in strings with other strings, but I 
 see little of this in dynamic array functionality. What am I missing ?


 Those functions are in std.string in Phobos.  And scattered all over 
 the place in Tango.


 
 If by 'scattered all over the place' you mean 'most everything suitable 
 for all array types is in tango.core.Array and everything else is in 
 tango.text.*', yes.


I mean the * part of tango.text.*, which consitutes about 30 different 
files.  Not saying it's a bad design, but it does make it a little 
harder for me to find things.

--bb
May 12 2008
parent "Nick Sabalausky" <a a.a> writes:
"Bill Baxter" <dnewsgroup billbaxter.com> wrote in message 
news:g0a82f$52q$1 digitalmars.com...

 Christopher Wright wrote:

 If by 'scattered all over the place' you mean 'most everything suitable 
 for all array types is in tango.core.Array and everything else is in 
 tango.text.*', yes.


 I mean the * part of tango.text.*, which consitutes about 30 different 
 files.  Not saying it's a bad design, but it does make it a little harder 
 for me to find things.


Don't know if you mean "find things" in the documentation, but if you mean 
importing, there's this:

import tango.group.text;

http://www.dsource.org/projects/tango/docs/current/tango.group.text.html
May 12 2008
prev sibling next sibling parent reply "Janice Caron" <caron800 googlemail.com> writes:
On 11/05/2008, Edward Diener <eddielee_no_spam_here tropicsoft.com> wrote:

 In D 1.0 dynamic arrays are the equivalent of C++'s std::vector<T>, with
 slicing replacing iterators in order to access some subrange of the
 sequence. In C++ there is functionality in std::vector::erase for erasing
 elements from the vector and std::vector::insert for inserting new elements
 into the vector. Where is that functionality in D's dynamic arrays ?


To erase the elements from index i to index j in place:

    array[i..$+i-j][] = array[j..$].dup;
    array = array[0..$+i-j];

I place this code in the public domain. Feel free to turn it into a
function. :-)
If you don't mind making a new copy, it's even easier - you can do that in one.

    array = array[0..i] ~ array[j..$];






 Furthermore in D 1.0 a char[], a dynamic array of characters, is the
 equivalent of the C++ std::string. In the C++ std::string class there is a
 rich set of functionality for manipulating the char elements in the string,
 for finding particular elements in the string, and for comparing the
 character elements in strings with other strings, but I see little of this
 in dynamic array functionality. What am I missing ?


std.string
std.algorithm
May 11 2008
next sibling parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Janice Caron wrote:

 On 11/05/2008, Edward Diener <eddielee_no_spam_here tropicsoft.com> wrote:

 In D 1.0 dynamic arrays are the equivalent of C++'s std::vector<T>, with
 slicing replacing iterators in order to access some subrange of the
 sequence. In C++ there is functionality in std::vector::erase for erasing
 elements from the vector and std::vector::insert for inserting new elements
 into the vector. Where is that functionality in D's dynamic arrays ?


 
 To erase the elements from index i to index j in place:
 
     array[i..$+i-j][] = array[j..$].dup;
     array = array[0..$+i-j];


It can be done more efficiently using memmove to shift contents down. 
Also if you're dropping the tail end, you can just change .length. 
Cashew's erase routine (called "dropRange") does both.

--bb
May 11 2008
next sibling parent reply "Janice Caron" <caron800 googlemail.com> writes:
On 11/05/2008, Bill Baxter <dnewsgroup billbaxter.com> wrote:

 Janice Caron wrote:



 To erase the elements from index i to index j in place:


  It can be done more efficiently using memmove to shift contents down. Also
 if you're dropping the tail end, you can just change .length. Cashew's erase
 routine (called "dropRange") does both.


OK, how about this, using std.algorithm.copy:

    array = copy(array[j..$], array[i..$]);
    array = array[0..$+i-j];

The copy is done in-place, like memmove(), but without the danger of
buffer overrun.
You still need the second line to change the length though.

You can even do it ONE LINE, but I have to confess, the code looks
pretty obfuscated.

    array = array[0..$-copy(array[j..$], array[i..$]).length];
May 11 2008
parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Janice Caron wrote:

 On 11/05/2008, Bill Baxter <dnewsgroup billbaxter.com> wrote:

 Janice Caron wrote:


 

 To erase the elements from index i to index j in place:


  It can be done more efficiently using memmove to shift contents down. Also
 if you're dropping the tail end, you can just change .length. Cashew's erase
 routine (called "dropRange") does both.


 
 OK, how about this, using std.algorithm.copy:
 
     array = copy(array[j..$], array[i..$]);
     array = array[0..$+i-j];
 
 The copy is done in-place, like memmove(), but without the danger of
 buffer overrun.


Std.algorithm's copy(), in its current form, will be less efficient 
because it copies elements one-at-a-time in a loop.  This was what the 
first version of Cashew did, but it was benchmarked and found that 
memmove is faster.

Of course, std.algorithm.copy could probably be tweaked to use memmove 
when possible, and then that would be just as good.  But right now it 
isn't.

Anyway, the existence of such subtleties is why things like erase should 
just be in the darn standard library so the problem only has to be 
solved once.


 You still need the second line to change the length though.
 
 You can even do it ONE LINE, but I have to confess, the code looks
 pretty obfuscated.
 
     array = array[0..$-copy(array[j..$], array[i..$]).length];


Yeh, don't do that.  :-)

--bb
May 11 2008
parent reply "Janice Caron" <caron800 googlemail.com> writes:
On 11/05/2008, Bill Baxter <dnewsgroup billbaxter.com> wrote:

 std.algorithm's copy(), in its current form, will be less efficient because
 it copies elements one-at-a-time in a loop.


That may be what the source code does, but it's the compiler's job to
optimize. If it doesn't, I blame the compiler :-)

Also, memmove can't be used in CTFE.



 Anyway, the existence of such subtleties is why things like erase
 should just be in the darn standard library so the problem only has
 to be solved once.


I agree.

Although, that said, I don't think anyone's really considered it a
"problem" before now.
May 11 2008
parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Janice Caron wrote:

 On 11/05/2008, Bill Baxter <dnewsgroup billbaxter.com> wrote:

 std.algorithm's copy(), in its current form, will be less efficient because
 it copies elements one-at-a-time in a loop.


 
 That may be what the source code does, but it's the compiler's job to
 optimize. If it doesn't, I blame the compiler :-)
 
 Also, memmove can't be used in CTFE.


Does std.algorithm.copy work in CTFE?


 Anyway, the existence of such subtleties is why things like erase
 should just be in the darn standard library so the problem only has
 to be solved once.


 
 I agree.
 
 Although, that said, I don't think anyone's really considered it a
 "problem" before now.


http://d.puremagic.com/issues/show_bug.cgi?id=473

--bb
May 11 2008
parent reply "Janice Caron" <caron800 googlemail.com> writes:
On 11/05/2008, Bill Baxter <dnewsgroup billbaxter.com> wrote:

  Does std.algorithm.copy work in CTFE?


I just tried it, and the answer's no. That seriously surprises me.

Apparently, it can't evaluate begin(target) at compile time.

OK - I withdraw that objection. (Although, of course, memmove will
/never/ be CTFE compatible, whereas copy might be in the future).
May 11 2008
parent Bill Baxter <dnewsgroup billbaxter.com> writes:
Janice Caron wrote:

 On 11/05/2008, Bill Baxter <dnewsgroup billbaxter.com> wrote:

  Does std.algorithm.copy work in CTFE?


 
 I just tried it, and the answer's no. That seriously surprises me.
 
 Apparently, it can't evaluate begin(target) at compile time.
 
 OK - I withdraw that objection. (Although, of course, memmove will
 /never/ be CTFE compatible, whereas copy might be in the future).


Eventually I think we'll need a "static if(is(CTFE))" or equivalent.
In that case functions like copy() could use a simpler fallback 
implementation in the "is(CTFE)" block, and use the fastest possible 
solution (e.g. memmove) in the non-CTFE case.

--bb
May 11 2008
prev sibling parent davidl <davidl 126.com> writes:
在 Mon, 12 May 2008 03:44:38 +0800，Bill Baxter  
<dnewsgroup billbaxter.com> 写道:


 Janice Caron wrote:

 On 11/05/2008, Edward Diener <eddielee_no_spam_here tropicsoft.com>  
 wrote:

 In D 1.0 dynamic arrays are the equivalent of C++'s std::vector<T>,  
 with
 slicing replacing iterators in order to access some subrange of the
 sequence. In C++ there is functionality in std::vector::erase for  
 erasing
 elements from the vector and std::vector::insert for inserting new  
 elements
 into the vector. Where is that functionality in D's dynamic arrays ?


  To erase the elements from index i to index j in place:
      array[i..$+i-j][] = array[j..$].dup;
     array = array[0..$+i-j];


 It can be done more efficiently using memmove to shift contents down.  
 Also if you're dropping the tail end, you can just change .length.  
 Cashew's erase routine (called "dropRange") does both.

 --bb


I will imagine D already calls memmove to perform array overlap copy.

-- 
使用 Opera 革命性的电子邮件客户程序: http://www.opera.com/mail/
May 11 2008
prev sibling parent reply Edward Diener <eddielee_no_spam_here tropicsoft.com> writes:
Janice Caron wrote:

 Furthermore in D 1.0 a char[], a dynamic array of characters, is the
 equivalent of the C++ std::string. In the C++ std::string class there is a
 rich set of functionality for manipulating the char elements in the string,
 for finding particular elements in the string, and for comparing the
 character elements in strings with other strings, but I see little of this
 in dynamic array functionality. What am I missing ?


 
 std.string
 std.algorithm


I do not see a std.algorithm in the D 1.0 Phobos docuemntation.
May 11 2008
next sibling parent "Janice Caron" <caron800 googlemail.com> writes:
On 11/05/2008, Edward Diener <eddielee_no_spam_here tropicsoft.com> wrote:

  I do not see a std.algorithm in the D 1.0 Phobos docuemntation.


It's in D2.
May 11 2008
prev sibling parent Frits van Bommel <fvbommel REMwOVExCAPSs.nl> writes:
Edward Diener wrote:

 Janice Caron wrote:

 Furthermore in D 1.0 a char[], a dynamic array of characters, is the
 equivalent of the C++ std::string. In the C++ std::string class there 
 is a
 rich set of functionality for manipulating the char elements in the 
 string,
 for finding particular elements in the string, and for comparing the
 character elements in strings with other strings, but I see little of 
 this
 in dynamic array functionality. What am I missing ?


 std.string
 std.algorithm


 
 I do not see a std.algorithm in the D 1.0 Phobos docuemntation.


That's because D1 doesn't have it. Janice tends to be a bit more 
D2-oriented...

There's a port of D2 std.algorithm (and other D2 Phobos modules) 
available from <http://www.dsource.org/projects/std2>, but it's based on 
an older version (2.008) of Phobos. I have no idea if this is 
substantially different from the current D2 Phobos.
It might be worth checking out if you need the stuff it contains.
May 11 2008
prev sibling next sibling parent Robert Fraser <fraserofthenight gmail.com> writes:
Edward Diener wrote:

 I am guessing this must be provided in D libraries of functions ( Phobos 
 ? Tango ? ) templated on the dynamic array type. But, if so, this seems 
 a poor way of providing dynamic array functionality as compared to 
 built-in dynamic array functionality in order to provide the sort of 
 functionality mentioned above, especially as D's dynamic arrays are part 
 of the D language as opposed to a separate library like C++'s 
 std::vector<T> and std::string.


I disagree. Having it in a library mans its more extensible and can be 
rewritten/altered more easily (for example, if more efficient algorithms 
are found).
May 11 2008
prev sibling next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Edward Diener:

 I see the Phobos std.string. It seems, at first glance, not nearly as 
 rich an implementation as the C++ std::string functionality.


A module of strings functions and the like is a work of the art of balance.
More isn't always better. You have to put there the best/right functions, and
throw away the useless ones, the more confusing ones, etc etc.

Bye,
bearophile
May 11 2008
next sibling parent reply Edward Diener <eddielee_no_spam_here tropicsoft.com> writes:
bearophile wrote:

 Edward Diener:

 I see the Phobos std.string. It seems, at first glance, not nearly as 
 rich an implementation as the C++ std::string functionality.


 
 A module of strings functions and the like is a work of the art of balance.
More isn't always better. You have to put there the best/right functions, and
throw away the useless ones, the more confusing ones, etc etc.


I am one of those who really likes the C++ std::string class. I would 
not have chosen all the redundancy with C strings in the various 
functionality, since a std::string can always be constructed from a C 
string, but other than that I think it is excellent. I don't understand 
why D would not have wanted to create a std.string which mirrors that 
functionality, leaving out the C-isms except for construction. Maybe I 
will just do it myself and post it somewhere as I play around with D 
some more.

I think D has sometime tried not to be C++ to its detriment, and this is 
one more case of that ( there are plenty others ).
May 11 2008
parent reply Tower Ty <tytower hotmail.com> writes:
Edward Diener Wrote:


 bearophile wrote:

 Edward Diener:

 I see the Phobos std.string. It seems, at first glance, not nearly as 
 rich an implementation as the C++ std::string functionality.


 
 A module of strings functions and the like is a work of the art of balance.
More isn't always better. You have to put there the best/right functions, and
throw away the useless ones, the more confusing ones, etc etc.


 
 I am one of those who really likes the C++ std::string class. I would 
 not have chosen all the redundancy with C strings in the various 
 functionality, since a std::string can always be constructed from a C 
 string, but other than that I think it is excellent. I don't understand 
 why D would not have wanted to create a std.string which mirrors that 
 functionality, leaving out the C-isms except for construction. Maybe I 
 will just do it myself and post it somewhere as I play around with D 
 some more.
 
 I think D has sometime tried not to be C++ to its detriment, and this is 
 one more case of that ( there are plenty others ).


I use tango and D1 but I for one would like to see strings available as a type
rather than char[] which I just find confusing . So if you create a better
string please do it in tango also.

I think there may be something there already but I havn't had time to
investigate.
May 11 2008
parent Robert Fraser <fraserofthenight gmail.com> writes:
Tower Ty wrote:

 Edward Diener Wrote:
 

 bearophile wrote:

 Edward Diener:

 I see the Phobos std.string. It seems, at first glance, not nearly as 
 rich an implementation as the C++ std::string functionality.


 A module of strings functions and the like is a work of the art of balance.
More isn't always better. You have to put there the best/right functions, and
throw away the useless ones, the more confusing ones, etc etc.


 I am one of those who really likes the C++ std::string class. I would 
 not have chosen all the redundancy with C strings in the various 
 functionality, since a std::string can always be constructed from a C 
 string, but other than that I think it is excellent. I don't understand 
 why D would not have wanted to create a std.string which mirrors that 
 functionality, leaving out the C-isms except for construction. Maybe I 
 will just do it myself and post it somewhere as I play around with D 
 some more.

 I think D has sometime tried not to be C++ to its detriment, and this is 
 one more case of that ( there are plenty others ).


 
 I use tango and D1 but I for one would like to see strings available as a type
rather than char[] which I just find confusing . So if you create a better
string please do it in tango also.
 
 I think there may be something there already but I havn't had time to
investigate.


There's mtext: http://www.dprogramming.com/mtext.php
May 11 2008
prev sibling parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
bearophile wrote:

 Edward Diener:

 I see the Phobos std.string. It seems, at first glance, not nearly as 
 rich an implementation as the C++ std::string functionality.


 
 A module of strings functions and the like is a work of the art of balance.
More isn't always better. You have to put there the best/right functions, and
throw away the useless ones, the more confusing ones, etc etc.


How does std.string measure up to your standards?  No "erase" function 
for removing a subrange efficiently, but yet it contains "soundex()"?

--bb
May 11 2008
parent bearophile <bearophileHUGS lycos.com> writes:
Bill Baxter:

 How does std.string measure up to your standards?  No "erase" function 
 for removing a subrange efficiently, but yet it contains "soundex()"?


I am not an expert of string APIs yet, but I have already posted here few lists
of comments, where I have expressed some of my comments. I think std.string:
- Sometimes it's good enough
- it has 1-3 functions that I think can be removed/renamed
- will enjoy some general array algorithms instead of just string ones, it may
mean some functions can be generalized and moved elsewhere (like Tango has
done, I think).
- a better unicode management may be in order
- a lazy xslice function plus few other may be added, see my d.string module in
my d libs for some functions I think are missing.
- Most functions are slow and they can improved, for example see my string
module again for a _much_ faster case-changing function. And Tango shows that
it's positive to give you optional ways to avoid heap activity.

Bye,
bearophile
May 11 2008
prev sibling parent reply Walter Bright <newshound1 digitalmars.com> writes:
Edward Diener wrote:

 In D 1.0 dynamic arrays are the equivalent of C++'s std::vector<T>, with 
 slicing replacing iterators in order to access some subrange of the 
 sequence. In C++ there is functionality in std::vector::erase for 
 erasing elements from the vector and std::vector::insert for inserting 
 new elements into the vector. Where is that functionality in D's dynamic 
 arrays ?


The D string library is oriented more towards COW (copy-on-write) 
operations rather than in-place modification. Hence, things are biased 
towards slicing and concatenating strings.


 Furthermore in D 1.0 a char[], a dynamic array of characters, is the 
 equivalent of the C++ std::string. In the C++ std::string class there is 
 a rich set of functionality for manipulating the char elements in the 
 string, for finding particular elements in the string,


std.string.find() for basic searches, std.regexp for more advanced ones.


 and for comparing 
 the character elements in strings with other strings,


== works for array contents, too


 but I see little 
 of this in dynamic array functionality. What am I missing ?


Can you be a bit more specific about what operation(s) you want to do?


 I am guessing this must be provided in D libraries of functions ( Phobos 
 ? Tango ? ) templated on the dynamic array type. But, if so, this seems 
 a poor way of providing dynamic array functionality as compared to 
 built-in dynamic array functionality in order to provide the sort of 
 functionality mentioned above, especially as D's dynamic arrays are part 
 of the D language as opposed to a separate library like C++'s 
 std::vector<T> and std::string.


I don't really understand your point. It sounds like you're suggesting 
that, by analogy, all floating point operations should be core language 
operations since floating point arithmetic is.
May 11 2008
parent reply Edward Diener <eddielee_no_spam_here tropicsoft.com> writes:
Walter Bright wrote:

 Edward Diener wrote:

 In D 1.0 dynamic arrays are the equivalent of C++'s std::vector<T>, 
 with slicing replacing iterators in order to access some subrange of 
 the sequence. In C++ there is functionality in std::vector::erase for 
 erasing elements from the vector and std::vector::insert for inserting 
 new elements into the vector. Where is that functionality in D's 
 dynamic arrays ?


 
 The D string library is oriented more towards COW (copy-on-write) 
 operations rather than in-place modification. Hence, things are biased 
 towards slicing and concatenating strings.
 

 Furthermore in D 1.0 a char[], a dynamic array of characters, is the 
 equivalent of the C++ std::string. In the C++ std::string class there 
 is a rich set of functionality for manipulating the char elements in 
 the string, for finding particular elements in the string,


 
 std.string.find() for basic searches, std.regexp for more advanced ones.


OK, slicing gives much functionality for grabbing substrings and I 
appreciate the syntax ( I have programmed in Python ).


 

 and for comparing the character elements in strings with other strings,


 
 == works for array contents, too


OK, good.


 

 but I see little of this in dynamic array functionality. What am I 
 missing ?


 
 Can you be a bit more specific about what operation(s) you want to do?


In the dynamic array world I would have expected functionlaity for 
erasing part of the array, inserting a new array at some point in the 
array, and for replacing any part of the array with another array of any 
  length. The replace is merely an erase + insert under the covers. Of 
course I am also talking about arrays of the same type.


 

 I am guessing this must be provided in D libraries of functions ( 
 Phobos ? Tango ? ) templated on the dynamic array type. But, if so, 
 this seems a poor way of providing dynamic array functionality as 
 compared to built-in dynamic array functionality in order to provide 
 the sort of functionality mentioned above, especially as D's dynamic 
 arrays are part of the D language as opposed to a separate library 
 like C++'s std::vector<T> and std::string.




Since dynamic arrays are part of the language and not a separate library 
I would have expected built-in functionality to manipulate them easily. 
Of course it can be in a library, but it seems even a general purpose 
dynamic array library does not exist for D 1.0, so that seems odd to me.
May 11 2008
next sibling parent Walter Bright <newshound1 digitalmars.com> writes:
Edward Diener wrote:

 In the dynamic array world I would have expected functionlaity for 
 erasing part of the array, inserting a new array at some point in the 
 array, and for replacing any part of the array with another array of any 
  length. The replace is merely an erase + insert under the covers. Of 
 course I am also talking about arrays of the same type.


I agree.


 Since dynamic arrays are part of the language and not a separate library 
 I would have expected built-in functionality to manipulate them easily. 
 Of course it can be in a library, but it seems even a general purpose 
 dynamic array library does not exist for D 1.0, so that seems odd to me.


It's demand driven <g>. Some of the functions in std.string may seem odd 
for someone coming from the C++ world, but they are functionally 
equivalent to Python's and Ruby's string functions.
May 11 2008
prev sibling next sibling parent reply "Me Here" <p9e883002 sneakemail.com> writes:
Edward Diener wrote:


 but it seems even a general purpose dynamic array library does not exist for
 D 1.0, so that seems odd to me.


Yep. Me too.

Coming back to D was a real shock. 

Kinda returning to the Ferrari factory after a similar period, having
previously seen the prototype F450,When you left, it had clean lines, parred
down framework and a great engine.

When you return you discover it's been fitted a hybrid drive train, a 1/4 tonne
of batteries and the slick, 7-speed floor-shift has been swapped out for a
3-speed auto box.

The last thing I ever thought I would see, was D become "buzz-word complient".
It's such a shame to see such a promising beginning get sidetracked off into a
world of academic theory and computer science correctness. The promise was that
because one guy with a pragmatic vision and the skills to make them so, held
the ropes and was steering the thing, that D wouldn't be subject to the pull &
push of academic group think nor the quagmire of design by committee.

b.
--
May 11 2008
parent reply "Saaa" <empty needmail.com> writes:
Which buzz-word would that be?

I find your remark/analogy off-topic.

Walter clearly states that Phobos is demand driven.
Also, his floating point analogy is right on mark.


 The last thing I ever thought I would see, was D become "buzz-word 
 complient".
 It's such a shame to see such a promising beginning get sidetracked off 
 into a
 world of academic theory and computer science correctness. The promise was 
 that
 because one guy with a pragmatic vision and the skills to make them so, 
 held
 the ropes and was steering the thing, that D wouldn't be subject to the 
 pull &
 push of academic group think nor the quagmire of design by committee.

 b.
 --
May 11 2008
parent reply "Me Here" <p9e883002 sneakemail.com> writes:
Saaa wrote:


 Which buzz-word would that be?


"const", "invariant", "pure", take your pick.

 
 I find your remark/analogy off-topic.


The topic is "dynamic arrays in Dv1". I replied to a post suggesting that the
support for dynamic arrays in Dv1 was missing some fundamental features. I
concur.

Analogies are, by their nature "off-topic". They seek to clarify a point by
reference to something more easiily understood.


 
 Walter clearly states that Phobos is demand driven.
 Also, his floating point analogy is right on mark.
 


You like Walter's analogy. Okay.

Not all flosting point operations have to be built-in to the compiler. But if
you had to resort to bit-twiddling the IEEE format in order to  do
exponentiation, you might wonder at the competeness., Or if summing an bunch of
reals caused a new 10-bytes to be allocated to accomodate each intermediary
subtotal, you might be a little taken aback.

Dynamic arrays are superior to fixed sized arrays, not just because you don't
have to know their size at compile time, but because they grow and shrink to
accomodate the demands the algorithm places upon them. Insert and delete are
about as fundamental to strings and exponentiation is to reals.

b.
--
May 11 2008
parent reply "Saaa" <empty needmail.com> writes:
 Which buzz-word would that be?


 "const", "invariant", "pure", take your pick.


It sounded like you meant buzz-word to cover a broader audience than this 
newsgroup.
I didn't know those where buzz-words in that sense, I just thought they were 
keywords in the whole const-discussion on this newsgroup.


 I find your remark/analogy off-topic.


 The topic is "dynamic arrays in Dv1". I replied to a post suggesting that 
 the
 support for dynamic arrays in Dv1 was missing some fundamental features. I
 concur.

 Analogies are, by their nature "off-topic". They seek to clarify a point 
 by
 reference to something more easiily understood.


By this definition I can't agree that analogies are by nature off-topic, but 
going further into this would certainly yield that way and would end in a 
good old fashioned dictionary fight ;)


 Walter clearly states that Phobos is demand driven.
 Also, his floating point analogy is right on mark.


 You like Walter's analogy. Okay.

 Not all flosting point operations have to be built-in to the compiler. But 
 if
 you had to resort to bit-twiddling the IEEE format in order to  do
 exponentiation, you might wonder at the competeness., Or if summing an 
 bunch of
 reals caused a new 10-bytes to be allocated to accomodate each 
 intermediary
 subtotal, you might be a little taken aback.

 Dynamic arrays are superior to fixed sized arrays, not just because you 
 don't
 have to know their size at compile time, but because they grow and shrink 
 to
 accomodate the demands the algorithm places upon them. Insert and delete 
 are
 about as fundamental to strings and exponentiation is to reals.


I won't go into the being superior part, but why hasn't anybody asked about 
delete and inserts before? (not rhetorical)
I think slicing and concatenation are fundamental in D.
May 11 2008
parent reply boyd <gaboonviper gmx.net> writes:
I think it's because erase and insert are really just the inverse of  =

slicing and concatenation.

int[] a, c;

// insert
c =3D a.insert(b, 10);
c =3D a[0..10] ~ b ~ a[10..$];

// delete
c =3D a.delete(&a[10..20]);
c =3D a[0..10] ~ a[20..$];

I essence delete and insert are just another way of expressing slices an=
d  =

concatenations. Personally I prefer slicing and concatting stuff, becaus=
e  =

it expresses better what's actually happening.

Delete and Insert on the other hand are higher level and generally more =
 =

intuitive. They leave optimization to the compiler/library. And I think =
 =

most D-users like more control of optimizations than users of more high =
 =

level languages.

Cheers,
Boyd

---------
On Mon, 12 May 2008 06:11:35 +0200, Saaa <empty needmail.com> wrote:


 I won't go into the being superior part, but why hasn't anybody asked =


 =


 about
 delete and inserts before? (not rhetorical)
 I think slicing and concatenation are fundamental in D.
May 12 2008
next sibling parent reply "Me Here" <p9e883002 sneakemail.com> writes:
boyd wrote:


 Delete and Insert on the other hand are higher level and generally more  
 intuitive. They leave optimization to the compiler/library. And I think  
 most D-users like more control of optimizations than users of more high  
 level languages.


You really think that slice and join will be more efficient, or afford greater
opportunities for optimisation than insert & delete?

Can I suggest that you produce a simple (or complex) benchmark to demonstrate
that?

b.
--
May 12 2008
parent reply boyd <gaboonviper gmx.net> writes:
I'm not saying either way is more efficient. I'm saying that slicing and  
concatenation are lower level functionality than insert and delete. So  
most optimizations when using slicing and concatenation will be done by  
the programmer, rather than the compiler or library.

In the end any delete or insert function implementation will have to use  
lower level functionality like concatenating, slicing, memory movement or  
something like that, whereas concatenation and slicing are about as low as  
you can get.

Cheers,
Boyd

----------
On Mon, 12 May 2008 18:36:59 +0200, Me Here <p9e883002 sneakemail.com>  
wrote:


 boyd wrote:


 Delete and Insert on the other hand are higher level and generally more
 intuitive. They leave optimization to the compiler/library. And I think
 most D-users like more control of optimizations than users of more high
 level languages.


 You really think that slice and join will be more efficient, or afford  
 greater
 opportunities for optimisation than insert & delete?

 Can I suggest that you produce a simple (or complex) benchmark to  
 demonstrate
 that?

 b.
May 12 2008
parent reply "Me Here" <p9e883002 sneakemail.com> writes:
boyd wrote:


 I'm not saying either way is more efficient. I'm saying that slicing and
 concatenation are lower level functionality than insert and delete. So  most
 optimizations when using slicing and concatenation will be done by  the
 programmer, rather than the compiler or library.


You don't think that this is stuff that should be got right once and then just
reused?
You're not a /real D programmer/ unless reimplement these well-documented
algorithms yourself?

b.
--
May 12 2008
parent boyd <gaboonviper gmx.net> writes:
I haven't said any of the sort.

--------
On Mon, 12 May 2008 20:40:42 +0200, Me Here <p9e883002 sneakemail.com>  
wrote:


 boyd wrote:


 I'm not saying either way is more efficient. I'm saying that slicing and
 concatenation are lower level functionality than insert and delete. So   
 most
 optimizations when using slicing and concatenation will be done by  the
 programmer, rather than the compiler or library.


 You don't think that this is stuff that should be got right once and  
 then just
 reused?
 You're not a /real D programmer/ unless reimplement these well-documented
 algorithms yourself?

 b.
May 12 2008
prev sibling parent reply Edward Diener <eddielee_no_spam_here tropicsoft.com> writes:
boyd wrote:

 I think it's because erase and insert are really just the inverse of 
 slicing and concatenation.
 
 int[] a, c;
 
 // insert
 c = a.insert(b, 10);
 c = a[0..10] ~ b ~ a[10..$];
 
 // delete
 c = a.delete(&a[10..20]);
 c = a[0..10] ~ a[20..$];
 
 I essence delete and insert are just another way of expressing slices 
 and concatenations. Personally I prefer slicing and concatting stuff, 
 because it expresses better what's actually happening.
 
 Delete and Insert on the other hand are higher level and generally more 
 intuitive. They leave optimization to the compiler/library. And I think 
 most D-users like more control of optimizations than users of more high 
 level languages.


You make a good point that things like delete, insert, and replace can 
be done with slicing and concatentaion. Thanks for bringing up these 
solutions. Having used Python extensively, where slicing is also a big 
part of lists, I should have realized that such operations are largely 
subsumed by slicing and concatenation in D. I have to take my C++ hat 
off and put my Python hat one when dealing with dynamic arrays in D.
May 12 2008
parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Edward Diener wrote:

 boyd wrote:

 I think it's because erase and insert are really just the inverse of 
 slicing and concatenation.

 int[] a, c;

 // insert
 c = a.insert(b, 10);
 c = a[0..10] ~ b ~ a[10..$];

 // delete
 c = a.delete(&a[10..20]);
 c = a[0..10] ~ a[20..$];

 I essence delete and insert are just another way of expressing slices 
 and concatenations. Personally I prefer slicing and concatting stuff, 
 because it expresses better what's actually happening.

 Delete and Insert on the other hand are higher level and generally 
 more intuitive. They leave optimization to the compiler/library. And I 
 think most D-users like more control of optimizations than users of 
 more high level languages.


 
 You make a good point that things like delete, insert, and replace can 
 be done with slicing and concatentaion. Thanks for bringing up these 
 solutions. 


Part of the comment, though, was that delete/insert are "higher-level 
and generally more intuitive".  With that I agree.


 Having used Python extensively, where slicing is also a big
 part of lists, I should have realized that such operations are largely 
 subsumed by slicing and concatenation in D. I have to take my C++ hat 
 off and put my Python hat one when dealing with dynamic arrays in D.


Fine point, except Python lists also have append, extend, index, insert, 
pop, and remove methods which you can use when they express your intent 
better than fidgety slicing expressions.

--bb
May 12 2008
next sibling parent reply Robert Fraser <fraserofthenight gmail.com> writes:
 Fine point, except Python lists also have append, extend, index, insert, 
 pop, and remove methods which you can use when they express your intent 
 better than fidgety slicing expressions.
 
 --bb


It's all a matter of taste. Making those functions is trivial in D; most 
are one-liners.
May 13 2008
parent Bill Baxter <dnewsgroup billbaxter.com> writes:
Robert Fraser wrote:

 Fine point, except Python lists also have append, extend, index, 
 insert, pop, and remove methods which you can use when they express 
 your intent better than fidgety slicing expressions.

 --bb


 
 It's all a matter of taste. Making those functions is trivial in D; most 
 are one-liners.


And so we come around full circle.  We've been doing a lot of that on 
the newsgroup recently.

They are relatively trivial, but there are still some gotchas in making 
them safe and maximally efficient (e.g. using memmove for better 
performance, etc).

--bb
May 13 2008
prev sibling parent Edward Diener <eddielee_no_spam_here tropicsoft.com> writes:
Bill Baxter wrote:

 Edward Diener wrote:

 boyd wrote:

 I think it's because erase and insert are really just the inverse of 
 slicing and concatenation.

 int[] a, c;

 // insert
 c = a.insert(b, 10);
 c = a[0..10] ~ b ~ a[10..$];

 // delete
 c = a.delete(&a[10..20]);
 c = a[0..10] ~ a[20..$];

 I essence delete and insert are just another way of expressing slices 
 and concatenations. Personally I prefer slicing and concatting stuff, 
 because it expresses better what's actually happening.

 Delete and Insert on the other hand are higher level and generally 
 more intuitive. They leave optimization to the compiler/library. And 
 I think most D-users like more control of optimizations than users of 
 more high level languages.


 You make a good point that things like delete, insert, and replace can 
 be done with slicing and concatentaion. Thanks for bringing up these 
 solutions. 


 
 Part of the comment, though, was that delete/insert are "higher-level 
 and generally more intuitive".  With that I agree.
 
  > Having used Python extensively, where slicing is also a big

 part of lists, I should have realized that such operations are largely 
 subsumed by slicing and concatenation in D. I have to take my C++ hat 
 off and put my Python hat one when dealing with dynamic arrays in D.


 
 Fine point, except Python lists also have append, extend, index, insert, 
 pop, and remove methods which you can use when they express your intent 
 better than fidgety slicing expressions.


I don't know if slicing expressions are really "fidgety" but Python has 
more flexiblity in its mutable sequence functionality than D, even using 
slicing syntax.

It hijacks its own 'del' keyword to express 'remove' of some inner 
sequence using possible slicing notation, so maybe D can hijack 'delete' 
for a similar purpose with its dynamic array. It does have both a more 
flexible 'replace' than D, where the number of elements in the 
replacement does not have to equal the number of elements being 
replaced, as it has to in D. Finally it has a neat 'insert' which lets 
you insert another sequence, possibly using slicing, at any index.

Obviously D, or Python itself, can do these things purely through 
slicing-concatenation-reassignment but I agree the "higher level" 
equivalent syntax in Python is easier to understand, as well as possibly 
being bettered optimized.
May 13 2008
prev sibling parent reply Sean Kelly <sean invisibleduck.org> writes:
Edward Diener wrote:

 
 Since dynamic arrays are part of the language and not a separate library 
 I would have expected built-in functionality to manipulate them easily. 
 Of course it can be in a library, but it seems even a general purpose 
 dynamic array library does not exist for D 1.0, so that seems odd to me.


What would you suggest adding to tango.core.Array?  I assume insert and 
remove at some position... perhaps others as well?


Sean
May 11 2008
parent Edward Diener <eddielee_no_spam_here tropicsoft.com> writes:
Sean Kelly wrote:

 Edward Diener wrote:

 Since dynamic arrays are part of the language and not a separate 
 library I would have expected built-in functionality to manipulate 
 them easily. Of course it can be in a library, but it seems even a 
 general purpose dynamic array library does not exist for D 1.0, so 
 that seems odd to me.


 
 What would you suggest adding to tango.core.Array?  I assume insert and 
 remove at some position... perhaps others as well?


Actually once I realized that slicing and concatenation can do what is 
necessary to emulate 'remove', 'insert', and 'replace' fairly easily I 
understood that D covers array manipulation based on indices pretty 
well. Your tango.core.array emulates C++ algorithms on containers pretty 
nicely so I have nothing particular to suggest there since I have not 
tried it out enough. You just might want to take a look at the C++ 
container algorithms, if you have not already done so, to see if there 
is anything there you may have left out which you feel might be 
worthwhile doing in tango.core.Array. But I have no real criticism or 
suggestion for your module.

The only real problem with the slicing/concatenation model may be 
optimization. That may be a reason to still pursue the C++ model of 
dynamic array, aka std::vector, manipulations in Tango.core.array. But I 
have little objection if the design is clear, even if the code is not 
highly optimized.
May 12 2008