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

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

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

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?

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?

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