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:
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
Sep 01 2012
parent reply "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
parent =?ISO-8859-1?Q?Jos=E9_Armando_Garc=EDa_Sancio?= <jsancio gmail.com> writes:
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 =


C,

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




e

 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=


l/intrusive/intrusive_vs_nontrusive.html>

 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=


r)

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


8/cpp1.png>) this probably leads to faster traversal times.


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





 Sep 04 2012