www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Embedded non-assignable containers

reply =?ISO-8859-1?Q?Jos=E9_Armando_Garc=EDa_Sancio?= <jsancio gmail.com> writes:
--e89a8f234cd525196204c8ab2db8
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

Hey,

I recently read an interesting blog Why should I have written ZeroMQ in C,
not C++ (part II) <http://www.250bpm.com/blog:8> by Martin S=FAstrik. The
title is misleading; to me its main observation is that object oriented
program may not lead to the most performant implementation. After reading
the blog I asked myself I would I implement this in D? I thought we could
use mixin and template mixin to implement this in a more
manageable/scalable way. The complete source code is at Embedded
Container<http://dpaste.dzfl.pl/14ddac09>
.

To make a type "double linkable" the developer needs to mixin the following
mixin template:

mixin template DoubleLinkable()
 {
   typeof(this) next;
   typeof(this) prev;
 }

The next and prev pointer can be access with the help of mixin by using the following templates: T* next(T, string name)(T node) pure nothrow const { mixin("return &(node." ~ name ~ ".next);"); } T* prev(T, string name)(T node) pure nothrow const { mixin("return &(node." ~ name ~ ".prev);"); } To use the above abstraction the developer just needs to do the following: class Person
 {
   int age;
   int weight;
   mixin DoubleLinkable people;
 }

void main() { auto list =3D new DoubleLinkedList!(Person, "people")();
   auto person1 =3D new Person(6, 60);

list.pushFront(person1);
   auto person2 =3D new Person(25, 160);

list.pushFront(person2);
   auto person3 =3D new Person(11, 100);

list.pushFront(person3);
   list.erase(person2);

list.erase(person3); list.erase(person1); } I am not a big fan of the template signature 'class DoubleLinkedList(T, string name)' but I couldn't figure out a better way of allowing one object to be embedded in multiple containers. Thoughts? Any idea how this can be improved so that it is easier to use and read? Thanks, -Jose --e89a8f234cd525196204c8ab2db8 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Hey,<br><br>I recently read an interesting blog=A0<a href=3D"http://www.250= bpm.com/blog:8">Why should I have written ZeroMQ in C, not C++ (part II)</a=
 by Martin S=FAstrik. The title is misleading; to me its main observation =

mentation. After reading the blog I asked myself I would I implement this i= n D? I thought we could use mixin and template mixin to implement this in a= more manageable/scalable way. The complete source code is at=A0<a href=3D"= http://dpaste.dzfl.pl/14ddac09">Embedded Container</a>.<div> <br></div><div>To make a type &quot;double linkable&quot; the developer nee= ds to mixin the following mixin template:</div><div><br></div><div><blockqu= ote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left-wid= th:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-l= eft:1ex"> mixin template DoubleLinkable()<br>{<br>=A0 typeof(this) next;<br>=A0 typeo= f(this) prev;<br>}</blockquote><div><br></div><div>The next and prev pointe= r can be access with the help of mixin by using the following templates:</d= iv> <div><br></div></div><div><blockquote class=3D"gmail_quote" style=3D"margin= :0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204)= ;border-left-style:solid;padding-left:1ex">T* next(T, string name)(T node) = pure nothrow const=A0</blockquote> <blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-= left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;p= adding-left:1ex">{=A0</blockquote><blockquote class=3D"gmail_quote" style= =3D"margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(20= 4,204,204);border-left-style:solid;padding-left:1ex"> =A0 mixin(&quot;return &amp;(node.&quot; ~ name ~ &quot;.next);&quot;);=A0<= /blockquote><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0= .8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-s= tyle:solid;padding-left:1ex"> }=A0</blockquote><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px = 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-l= eft-style:solid;padding-left:1ex">=A0=A0</blockquote><blockquote class=3D"g= mail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left-width:1px;border-= left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"> T* prev(T, string name)(T node) pure nothrow const=A0</blockquote><blockquo= te class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left-widt= h:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-le= ft:1ex"> {=A0</blockquote><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px = 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-l= eft-style:solid;padding-left:1ex">=A0 mixin(&quot;return &amp;(node.&quot; = ~ name ~ &quot;.prev);&quot;);=A0</blockquote> <blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-= left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;p= adding-left:1ex">}</blockquote><div><br></div><div>To use the above abstrac= tion the developer just needs to do the following:</div> <div><br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0p= x 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-lef= t-style:solid;padding-left:1ex">class Person<br>{<br>=A0 int age;<br>=A0 in= t weight;<br> =A0 mixin DoubleLinkable people;<br>}=A0</blockquote><blockquote class=3D"g= mail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left-width:1px;border-= left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">=A0</= blockquote> <blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-= left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;p= adding-left:1ex">void main()</blockquote><blockquote class=3D"gmail_quote" = style=3D"margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:r= gb(204,204,204);border-left-style:solid;padding-left:1ex"> {</blockquote><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px= 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left= -style:solid;padding-left:1ex">=A0 auto list =3D new DoubleLinkedList!(Pers= on, &quot;people&quot;)();</blockquote> <blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-= left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;p= adding-left:1ex"><br></blockquote><blockquote class=3D"gmail_quote" style= =3D"margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(20= 4,204,204);border-left-style:solid;padding-left:1ex"> =A0 auto person1 =3D new Person(6, 60);</blockquote><blockquote class=3D"gm= ail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left-width:1px;border-l= eft-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">=A0 li= st.pushFront(person1);</blockquote> <blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-= left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;p= adding-left:1ex"><br></blockquote><blockquote class=3D"gmail_quote" style= =3D"margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(20= 4,204,204);border-left-style:solid;padding-left:1ex"> =A0 auto person2 =3D new Person(25, 160);</blockquote><blockquote class=3D"= gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left-width:1px;border= -left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">=A0 = list.pushFront(person2);</blockquote> <blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-= left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;p= adding-left:1ex"><br></blockquote><blockquote class=3D"gmail_quote" style= =3D"margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(20= 4,204,204);border-left-style:solid;padding-left:1ex"> =A0 auto person3 =3D new Person(11, 100);</blockquote><blockquote class=3D"= gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left-width:1px;border= -left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">=A0 = list.pushFront(person3);</blockquote> <blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-= left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;p= adding-left:1ex"><br></blockquote><blockquote class=3D"gmail_quote" style= =3D"margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(20= 4,204,204);border-left-style:solid;padding-left:1ex"> =A0 list.erase(person2);</blockquote><blockquote class=3D"gmail_quote" styl= e=3D"margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(2= 04,204,204);border-left-style:solid;padding-left:1ex">=A0 list.erase(person= 3);</blockquote> <blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-= left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;p= adding-left:1ex">=A0 list.erase(person1);</blockquote><blockquote class=3D"= gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left-width:1px;border= -left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"> }</blockquote><div><br></div><div><br></div><div>I am not a big fan of the = template signature &#39;class DoubleLinkedList(T, string name)&#39; but I c= ouldn&#39;t figure out a better way of allowing one object to be embedded i= n multiple containers. Thoughts? Any idea how this can be improved so that = it is easier to use and read?</div> <div><br></div><div>Thanks,</div><div>-Jose=A0</div></div> --e89a8f234cd525196204c8ab2db8--
Sep 01 2012
next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
José Armando García Sancio:

 I recently read an interesting blog Why should I have written 
 ZeroMQ in C,
 not C++ (part II) <http://www.250bpm.com/blog:8> by Martin 
 Sústrik. The
 title is misleading; to me its main observation is that object 
 oriented
 program may not lead to the most performant implementation.

Isn't he talking about Boost intrusive lists? http://www.boost.org/doc/libs/1_51_0/doc/html/intrusive/intrusive_vs_nontrusive.html One advantage of the NOT intrusive stl list is that if you have to transverse the linked list very often, the L1 cache only sees the smal(ler) "helpers" (see this image: http://250bpm.wdfiles.com/local--files/blog:8/cpp1.png ) this probably leads to faster traversal times. On the other hand linked lists are kind of dead, today their need is uncommon. Bye, bearophile
Sep 01 2012
prev sibling parent =?ISO-8859-1?Q?Jos=E9_Armando_Garc=EDa_Sancio?= <jsancio gmail.com> writes:
--20cf3074d9ee646c1804c8e293b1
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

On Sat, Sep 1, 2012 at 6:40 PM, bearophile <bearophileHUGS lycos.com> wrote=
:

 Jos=E9 Armando Garc=EDa Sancio:

  I recently read an interesting blog Why should I have written ZeroMQ in =

 not C++ (part II) <http://www.250bpm.com/blog:8> by Martin S=FAstrik. Th=


 title is misleading; to me its main observation is that object oriented
 program may not lead to the most performant implementation.

Isn't he talking about Boost intrusive lists? http://www.boost.org/doc/libs/**1_51_0/doc/html/intrusive/** intrusive_vs_nontrusive.html<http://www.boost.org/doc/libs/1_51_0/doc/htm=

 Basically.

 One advantage of the NOT intrusive stl list is that if you have to
 transverse the linked list very often, the L1 cache only sees the smal(le=

 "helpers" (see this image: http://250bpm.wdfiles.com/**
 local--files/blog:8/cpp1.png<http://250bpm.wdfiles.com/local--files/blog:=


Maybe. But I suspect that you are traversing the list to at least read into the object so I think this become a wash if not worst.

On the other hand linked lists are kind of dead, today their need is
 uncommon.

How so? Immutable single linked list are nice for multi-threaded programming. They are heavily used by functional languages like Haskell, Scala, Clojure, etc. Bye,
 bearophile

--20cf3074d9ee646c1804c8e293b1 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable On Sat, Sep 1, 2012 at 6:40 PM, bearophile <span dir=3D"ltr">&lt;<a href=3D= "mailto:bearophileHUGS lycos.com" target=3D"_blank">bearophileHUGS lycos.co= m</a>&gt;</span> wrote:<br><div class=3D"gmail_quote"><blockquote class=3D"= gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-= left:1ex"> Jos=E9 Armando Garc=EDa Sancio:<br> <br> <blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p= x #ccc solid;padding-left:1ex"><div class=3D"im"> I recently read an interesting blog Why should I have written ZeroMQ in C,<= br></div> not C++ (part II) &lt;<a href=3D"http://www.250bpm.com/blog:8" target=3D"_b= lank">http://www.250bpm.com/blog:8</a>&gt; by Martin S=FAstrik. The<div cla= ss=3D"im"><br> title is misleading; to me its main observation is that object oriented<br> program may not lead to the most performant implementation.<br> </div></blockquote> <br> Isn&#39;t he talking about Boost intrusive lists?<br> <br> <a href=3D"http://www.boost.org/doc/libs/1_51_0/doc/html/intrusive/intrusiv= e_vs_nontrusive.html" target=3D"_blank">http://www.boost.org/doc/libs/<u></= u>1_51_0/doc/html/intrusive/<u></u>intrusive_vs_nontrusive.html</a><br> <br></blockquote><div>Basically.</div><div>=A0</div><blockquote class=3D"gm= ail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-le= ft:1ex"> One advantage of the NOT intrusive stl list is that if you have to transver= se the linked list very often, the L1 cache only sees the smal(ler) &quot;h= elpers&quot; (see this image: <a href=3D"http://250bpm.wdfiles.com/local--f= iles/blog:8/cpp1.png" target=3D"_blank">http://250bpm.wdfiles.com/<u></u>lo= cal--files/blog:8/cpp1.png</a> ) this probably leads to faster traversal ti= mes.<br> </blockquote><div><br></div><div>Maybe. But I suspect that you are traversi= ng the list to at least read into the object so I think this become a wash = if not worst.</div><div>=A0</div><blockquote class=3D"gmail_quote" style=3D= "margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> =A0</blockquote><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8e= x;border-left:1px #ccc solid;padding-left:1ex"> On the other hand linked lists are kind of dead, today their need is uncomm= on.<br></blockquote><div><br></div><div>How so? Immutable single linked lis= t are nice for multi-threaded programming. They are heavily used by functio= nal languages like Haskell, Scala, Clojure, etc.=A0</div> <div><br></div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex= ;border-left:1px #ccc solid;padding-left:1ex"> Bye,<br> bearophile<br> </blockquote></div><br> --20cf3074d9ee646c1804c8e293b1--
Sep 04 2012