www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - STL like Vector,Pair, Map

reply BLS <nanali nospam-wanadoo.fr> writes:
I guess the most wanted STL containers are (at least for me) Vector, 
Pair, Map.  and yep, I know that we have dyn. and asso. arrays but I 
have to translate and port a lot of C++ stuff, using these containers. 
This also means that the Java like Tango container impl. is not exactly 
what I want.

Ideas ?
Nov 13 2007
next sibling parent reply "Janice Caron" <caron800 googlemail.com> writes:
On Nov 13, 2007 11:48 AM, BLS <nanali nospam-wanadoo.fr> wrote:

 I guess the most wanted STL containers are (at least for me) Vector,
 Pair, Map.  and yep, I know that we have dyn. and asso. arrays but I
 have to translate and port a lot of C++ stuff, using these containers.
 This also means that the Java like Tango container impl. is not exactly
 what I want.

 Ideas ?


Write your own? How hard can it be?
Nov 13 2007
parent reply BLS <nanali nospam-wanadoo.fr> writes:
Janice Caron schrieb:

 On Nov 13, 2007 11:48 AM, BLS <nanali nospam-wanadoo.fr> wrote:

 I guess the most wanted STL containers are (at least for me) Vector,
 Pair, Map.  and yep, I know that we have dyn. and asso. arrays but I
 have to translate and port a lot of C++ stuff, using these containers.
 This also means that the Java like Tango container impl. is not exactly
 what I want.

 Ideas ?


 
 Write your own? How hard can it be?


You are right. Most probabely I can do that. But I am sure this is like 
reinventing the wheel. (Heck, I've made dtl.vector No. 20) But anyway, 
compared to me, much more experienced or simply better programmers live 
in the D world and I hope someone is gentle enough to offer his 
bulletproof implementation. Even better : Having tango.dtl.vector f.i. 
you know :)
kind regards, bjoern
Nov 13 2007
parent reply BLS <nanali nospam-wanadoo.fr> writes:
BLS schrieb:

 Janice Caron schrieb:

 On Nov 13, 2007 11:48 AM, BLS <nanali nospam-wanadoo.fr> wrote:

 I guess the most wanted STL containers are (at least for me) Vector,
 Pair, Map.  and yep, I know that we have dyn. and asso. arrays but I
 have to translate and port a lot of C++ stuff, using these containers.
 This also means that the Java like Tango container impl. is not exactly
 what I want.

 Ideas ?


 Write your own? How hard can it be?


 
 You are right. Most probabely I can do that. But I am sure this is like 
 reinventing the wheel. (Heck, I've made dtl.vector No. 20) But anyway, 
 compared to me, much more experienced or simply better programmers live 
 in the D world and I hope someone is gentle enough to offer his 
 bulletproof implementation. Even better : Having tango.dtl.vector f.i. 
 you know :)
 kind regards, bjoern


Regarding " How hard can it be "
Just an additional remark. I don't think it is a child's play to 
implement data structures in a *professional way.
Thanks Bjoern
Nov 13 2007
parent Ary Manzana <ary esperanto.org.ar> writes:
BLS wrote:

 BLS schrieb:

 Janice Caron schrieb:

 On Nov 13, 2007 11:48 AM, BLS <nanali nospam-wanadoo.fr> wrote:

 I guess the most wanted STL containers are (at least for me) Vector,
 Pair, Map.  and yep, I know that we have dyn. and asso. arrays but I
 have to translate and port a lot of C++ stuff, using these containers.
 This also means that the Java like Tango container impl. is not exactly
 what I want.

 Ideas ?


 Write your own? How hard can it be?


 You are right. Most probabely I can do that. But I am sure this is 
 like reinventing the wheel. (Heck, I've made dtl.vector No. 20) But 
 anyway, compared to me, much more experienced or simply better 
 programmers live in the D world and I hope someone is gentle enough to 
 offer his bulletproof implementation. Even better : Having 
 tango.dtl.vector f.i. you know :)
 kind regards, bjoern


 Regarding " How hard can it be "
 Just an additional remark. I don't think it is a child's play to 
 implement data structures in a *professional way.
 Thanks Bjoern


As an example, you can see the container classes in .Net :-)
Nov 13 2007
prev sibling next sibling parent reply torhu <no spam.invalid> writes:
BLS wrote:

 I guess the most wanted STL containers are (at least for me) Vector, 
 Pair, Map.  and yep, I know that we have dyn. and asso. arrays but I 
 have to translate and port a lot of C++ stuff, using these containers. 
 This also means that the Java like Tango container impl. is not exactly 
 what I want.
 
 Ideas ?


You could try Indigo as a starting point.  It's got STL-compatible 
Vector and Map.  Be warned that it's a long since dead project, but I 
updated it to at least build with DMD 1.014.  No guarantees that it 
won't blow up your computer.  The license is LGPL, so I think you need 
to publish either the source, or at least the object files of any app 
you link it statically with.

http://www.dsource.org/projects/indigo
Nov 13 2007
parent reply Bruce Adams <tprtpose_74 yeah.who.co.uk> writes:
torhu Wrote:


 BLS wrote:

 I guess the most wanted STL containers are (at least for me) Vector, 
 Pair, Map.  and yep, I know that we have dyn. and asso. arrays but I 
 have to translate and port a lot of C++ stuff, using these containers. 
 This also means that the Java like Tango container impl. is not exactly 
 what I want.
 
 Ideas ?


 
 You could try Indigo as a starting point.  It's got STL-compatible 
 Vector and Map.  Be warned that it's a long since dead project, but I 
 updated it to at least build with DMD 1.014.  No guarantees that it 
 won't blow up your computer.  The license is LGPL, so I think you need 
 to publish either the source, or at least the object files of any app 
 you link it statically with.
 
 http://www.dsource.org/projects/indigo


I thought the whole purpose of the LGPL is to avoid that. You should be fine
with linking but should include a link to the source for the library itself
somewhere in your docs. Only if its the full GPL do you have to release your
app's source as well.

Regards,

Bruce.
Nov 13 2007
parent Sebastian Beschke <s.beschke gmx.de> writes:
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Bruce Adams schrieb:

 torhu Wrote:

 You could try Indigo as a starting point.  It's got STL-compatible 
 Vector and Map.  Be warned that it's a long since dead project, but I 
 updated it to at least build with DMD 1.014.  No guarantees that it 
 won't blow up your computer.  The license is LGPL, so I think you need 
 to publish either the source, or at least the object files of any app 
 you link it statically with.

 http://www.dsource.org/projects/indigo


 
 I thought the whole purpose of the LGPL is to avoid that. You should be fine
with linking but should include a link to the source for the library itself
somewhere in your docs. Only if its the full GPL do you have to release your
app's source as well.
 
 Regards,
 
 Bruce.
 


If I recall correctly, the LGPL requires you to release your program in
a way that enables it to be linked with a different version of the
LGPL'd library. That is, either you use a dynamically linked version of
said library, or you provide the object files for your program.

Sebastian
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.7 (MingW32)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFHOecjKb/1n5A2TAMRAnS6AJ9Talk21bg4zGdG2rCFBn3oggPt2gCfTJ4W
NlnAtveV1Ix9k1xoSRbXIcU=
=T1B2
-----END PGP SIGNATURE-----
Nov 13 2007
prev sibling next sibling parent reply Sean Kelly <sean f4.ca> writes:
BLS wrote:

 I guess the most wanted STL containers are (at least for me) Vector, 
 Pair, Map.  and yep, I know that we have dyn. and asso. arrays but I 
 have to translate and port a lot of C++ stuff, using these containers. 
 This also means that the Java like Tango container impl. is not exactly 
 what I want.


Someday when I get the time I'm going to do this.  However, I believe 
there is a red-black tree implementation in scrapple.


Sean
Nov 13 2007
parent BLS <nanali nospam-wanadoo.fr> writes:
Sean Kelly schrieb:

 BLS wrote:

 I guess the most wanted STL containers are (at least for me) Vector, 
 Pair, Map.  and yep, I know that we have dyn. and asso. arrays but I 
 have to translate and port a lot of C++ stuff, using these containers. 
 This also means that the Java like Tango container impl. is not 
 exactly what I want.


 
 Someday when I get the time I'm going to do this.  However, I believe 
 there is a red-black tree implementation in scrapple.
 
 
 Sean


Sean.
I am not eating algos at breakfast ... I prefer to go fishing. (in 
doubt, without having breakfast )

Bjoern
Nov 13 2007
prev sibling next sibling parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
BLS wrote:

 I guess the most wanted STL containers are (at least for me) Vector, 
 Pair, Map.  and yep, I know that we have dyn. and asso. arrays but I 
 have to translate and port a lot of C++ stuff, using these containers. 
 This also means that the Java like Tango container impl. is not exactly 
 what I want.
 
 Ideas ?


I have some of these that I used to aid in porting OpenMesh from C++.
http://www.dsource.org
They started life as some code from ArcLib, but I added more 
STL-compatibility stuff (like iterators) and rounded out the 
functionality a bit.  It's not a complete STL interface, but it was good 
enough to get OpenMesh working.  There's ListT.d, MapT.d, SetT.d.  I 
also have some adapters for creating STL-like iterators to D arrays.

License on those particular files is ZLIB/LibPNG.  The rest of 
OpenMesh/D is LGPL, though.


http://www.dsource.org/projects/openmeshd

--bb
Nov 13 2007
parent BLS <nanali nospam-wanadoo.fr> writes:
Bill Baxter schrieb:

 BLS wrote:

 I guess the most wanted STL containers are (at least for me) Vector, 
 Pair, Map.  and yep, I know that we have dyn. and asso. arrays but I 
 have to translate and port a lot of C++ stuff, using these containers. 
 This also means that the Java like Tango container impl. is not 
 exactly what I want.

 Ideas ?


 
 I have some of these that I used to aid in porting OpenMesh from C++.
 http://www.dsource.org
 They started life as some code from ArcLib, but I added more 
 STL-compatibility stuff (like iterators) and rounded out the 
 functionality a bit.  It's not a complete STL interface, but it was good 
 enough to get OpenMesh working.  There's ListT.d, MapT.d, SetT.d.  I 
 also have some adapters for creating STL-like iterators to D arrays.
 
 License on those particular files is ZLIB/LibPNG.  The rest of 
 OpenMesh/D is LGPL, though.
 
 
 http://www.dsource.org/projects/openmeshd
 
 --bb


Thanks Bill, (wonder how often I have to say that...)  any chance that 
you strip the code out of it's current environment. ?
Nov 13 2007
prev sibling parent reply "David B. Held" <dheld codelogicconsulting.com> writes:
BLS wrote:

 I guess the most wanted STL containers are (at least for me) Vector, 
 Pair, Map.  and yep, I know that we have dyn. and asso. arrays but I 
 have to translate and port a lot of C++ stuff, using these containers. 
 This also means that the Java like Tango container impl. is not exactly 
 what I want.


It will be very hard to provide STL containers until we get struct 
d'tors and copy c'tors (contrary to how Janice trivializes the task ;). 
  D doesn't support value types as well as C++ does, but expect this to 
change.

Dave
Nov 13 2007
parent reply Sean Kelly <sean f4.ca> writes:
David B. Held wrote:

 
 It will be very hard to provide STL containers until we get struct 
 d'tors and copy c'tors (contrary to how Janice trivializes the task ;). 


Why?


Sean
Nov 13 2007
parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Sean Kelly wrote:

 David B. Held wrote:

 It will be very hard to provide STL containers until we get struct 
 d'tors and copy c'tors (contrary to how Janice trivializes the task ;). 




Yes, defintely do watch out for that BLS.

 
 Why?


STL containers act like value types.

std::vector<int> a,b;
...// put some stuff in vector a
b = a;  // now b has a copy of every element of a
a[4] = 9;  //b[4] unchanged


In D currently to get that behavior have to do .dup:
int[] a,b;
b = a.dup;

So my STL-like interfaces have D-ish dup functions to make value copies.

But BLS, you should watch out for any such assignments of STL containers 
in your code, and change them to a = b.dup type things.

--bb
Nov 13 2007
parent reply Tim Keating <mrtact+dnewsgroup gmail.com> writes:
Bill Baxter Wrote:


 Why?


 
 STL containers act like value types.
 
 std::vector<int> a,b;
 ...// put some stuff in vector a
 b = a;  // now b has a copy of every element of a
 a[4] = 9;  //b[4] unchanged
 
 
 In D currently to get that behavior have to do .dup:
 int[] a,b;
 b = a.dup;


But . . . the reason the STL uses value types is to minimize the complexity
inherent in determining who owns objects passed by reference. Doesn't that
problem just _go away_ in a garbage-collected language?

Could you not build an interface-compatible set of STL containers that use
reference semantics instead? Admittedly, that's a big caveat for porting, but I
wonder how much code you would actually have to change . . . 

TK
Nov 14 2007
next sibling parent Regan Heath <regan netmail.co.nz> writes:
Tim Keating wrote:

 Bill Baxter Wrote:
 

 Why?


 STL containers act like value types.
 
 std::vector<int> a,b; ...// put some stuff in vector a b = a;  //
 now b has a copy of every element of a a[4] = 9;  //b[4] unchanged
 
 
 In D currently to get that behavior have to do .dup: int[] a,b; b =
 a.dup;


 
 But . . . the reason the STL uses value types is to minimize the
 complexity inherent in determining who owns objects passed by
 reference. Doesn't that problem just _go away_ in a garbage-collected
 language?


To some extent yes.  To the extent that you no longer need to figure out 
if you can free the memory associated with it.  However not to the 
extent that if you have say, a string/char[] and want to know if you 
need to dup it in order to modify it.

In the latter case if following D guidelines you would 'copy on write' 
AKA make a dup and write to the dup.  However, in the case where you had 
the only reference to the object this is less efficient.

Reference counting could be used but I suspect the overhead of managing 
them probably cancels out any gains.

I just wondered if the garbage collector could calculate reference 
counts on the fly... however I guess these could only be relied on 
immediately after they were generated and would therefore be of limited use.


 Could you not build an interface-compatible set of STL containers
 that use reference semantics instead? Admittedly, that's a big caveat
 for porting, but I wonder how much code you would actually have to
 change . . .


If you also used copy on write when modifying objects in the collection 
then you could, and you'd even gain some performance as copies are only 
made when changes are made to the objects.

Regan
Nov 14 2007
prev sibling parent reply James Dennett <jdennett acm.org> writes:
Tim Keating wrote:

 Bill Baxter Wrote:
 

 Why?


 STL containers act like value types.

 std::vector<int> a,b;
 ...// put some stuff in vector a
 b = a;  // now b has a copy of every element of a
 a[4] = 9;  //b[4] unchanged


 In D currently to get that behavior have to do .dup:
 int[] a,b;
 b = a.dup;


 
 But . . . the reason the STL uses value types is to minimize
 the complexity inherent in determining who owns objects passed
 by reference. Doesn't that problem just _go away_ in a 
garbage-collected language?


Only one (trivial) aspect of it does.  In the presence of
mutability, shared ownership is very different from value
semantics.


 Could you not build an interface-compatible set of STL containers
 that use reference semantics instead? Admittedly, that's a big 
 caveat for porting, but I wonder how much code you would actually
 have to change . . .


Plenty, though admittedly many containers are *not* copied
so some code would port easily.  The pain would be in finding
places where copy semantics were needed; the best way to do
that would probably be to artificially disable copying in the
C++ code and check where sharing would be viable.

-- james
Nov 14 2007
parent "David B. Held" <dheld codelogicconsulting.com> writes:
James Dennett wrote:

 [...]
 Plenty, though admittedly many containers are *not* copied
 so some code would port easily.  The pain would be in finding
 places where copy semantics were needed; the best way to do
 that would probably be to artificially disable copying in the
 C++ code and check where sharing would be viable.


Every STL container I know about gives you full-on value/copy semantics 
when you want it.  If I assign one map<> to another, there is no 
sharing.  Same for list<>, vector<>, deque<>, etc.  If you allow 
sharing, you are not offering value semantics (which is fine if that is 
what you are advertising).  The only time sharing is indistinguishably 
safe is for const containers.

Dave
Nov 18 2007