Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Here’s an awesome thing: you actually can make a cyclic doubly linked list in C++ with references, in a manner defined by the standard!

    #include <iostream>

    struct node {
      node(node& previous, node& next, int value)
        : previous(previous), next(next), value(value) {}
      node& previous;
      node& next;
      int value;
    };

    int main(int argc, char** argv) {
      char buffer[2 * sizeof(node)];
      node* a = reinterpret_cast<node*>(buffer);
      node* b = a + 1;
      node nil(nil, nil, 0);
      new(a) node(nil, nil, 0);
      new(b) node(nil, nil, 0);
      new(a) node(*b, *b, 1);
      new(b) node(*a, *a, 2);
      std::cout << a->next.next.next.value << '\n';
    }
§3.8¶4 says:

“A program may end the lifetime of any object by reusing the storage which the object occupies or by explicitly calling the destructor for an object of a class type with a non-trivial destructor.”

We don’t need to call the destructor because we have a POD type and we don’t depend on the side effects of the destructor—there aren’t any—so we can simply reinitialise the objects. However, we have to bootstrap these with valid objects in the first place, because we have to be able to dereference “b” and “a” in order to construct the references.



Nice example! I think that can be simplified:

  node a(nil, nil, 0);
  node b(a, a, 2);
  new(&a) node(b, b, 1);
One thing I am not 100% sure about is whether the standard guarantees that those references to the old 'a' are valid references to the new 'a'.

Also, the above works in the general case where there is a nontrivial destructor or when the runtime checks the validity of those references or traverses them at destruction time (might happen when running under a tool looking for memory leaks, for instance, or when using a reference-counting garbage collector under the hood)


The standard doesn’t seem to specify it directly, but I think your simplification is also correct.


I don't think that node is a POD type because it holds two reference members. More on this here: http://stackoverflow.com/questions/4178175/what-are-aggregat...

In particular, node does not have a trivial copy-assignment operator. Further below it seems that classes/structs containing references do not have a standard layout. Hence, it is not a POD.

Also, the standard does not guarantee anything about your usage of reinterpret_cast.

Maybe the code you provided works on your particular implementation, but I'm willing to bet that it violates the standard in several ways.

EDIT: cool trick though. I forgot that a name is in scope and refers to itself just after it is declared, i.e., that you can refer to nil while constructing nil.


Ah, you’re right, it’s not POD, but it should still be safe to reuse the storage in this way. You’re also right about the reinterpret_cast, but it’s not necessary for this example because placement new takes a “void” pointer—I just did it to get the convenience of “+ 1” instead of “+ sizeof(node)”.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: