{"id":110145,"date":"2024-08-19T07:00:00","date_gmt":"2024-08-19T14:00:00","guid":{"rendered":"https:\/\/devblogs.microsoft.com\/oldnewthing\/?p=110145"},"modified":"2024-08-19T11:02:10","modified_gmt":"2024-08-19T18:02:10","slug":"20240819-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20240819-00\/?p=110145","title":{"rendered":"Constructing nodes of a hand-made linked list, how hard can it be?"},"content":{"rendered":"

Suppose you are writing your own circular doubly-linked list structure.<\/p>\n

struct node\r\n{\r\n    node* prev;\r\n    node* next;\r\n};\r\n<\/pre>\n
A natural choice for the default constructor is to make the node the sole element of a circular doubly-linked list.<\/p>\n
struct node\r\n{\r\n    node* prev = this;\r\n    node* next = this;\r\n};\r\n<\/pre>\n
What if you also want to add a node after an existing node? Well, we could add a constructor for that.<\/p>\n
struct node\r\n{\r\n    node* prev = this;\r\n    node* next = this;\r\n\r\n    node() = default;\r\n\r\n    \/\/ Construct a node after a specific node<\/span>\r\n    node(node* other) :                      <\/span>\r\n        prev(other),                         <\/span>\r\n        next(other->next)                    <\/span>\r\n    {                                        <\/span>\r\n        prev->next = this;                   <\/span>\r\n        next->prev = this;                   <\/span>\r\n    }                                        <\/span>\r\n};\r\n<\/pre>\n
(Note that the “construct after another node” constructor takes the other node<\/code> by pointer, rather than by reference, so that it won’t be mistaken for a copy constructor.)<\/p>\n
But maybe you also want to have a “before” constructor that inserts the new node before an existing node.<\/p>\n
struct node\r\n{\r\n    node* prev = this;\r\n    node* next = this;\r\n\r\n    node() = default;\r\n\r\n    \/\/ Construct a node after a specific node\r\n    node(node* other) :\r\n        prev(other),\r\n        next(other->next)\r\n    {\r\n        prev->next = this;\r\n        next->prev = this;\r\n    }\r\n\r\n    \/\/ Construct a node before a specific node<\/span>\r\n    node(node* other) :                       <\/span>\r\n        prev(other->prev),                    <\/span>\r\n        next(other)                           <\/span>\r\n    {                                         <\/span>\r\n        prev->next = this;                    <\/span>\r\n        next->prev = this;                    <\/span>\r\n    }                                         <\/span>\r\n};\r\n<\/pre>\n
Uh-oh, we have two constructors with the same parameter list. That’s not going to work.<\/p>\n
And really, even if we had only one of the constructors, it would still be a bad design because it’s not clear whether the newly-created item goes before or after.<\/p>\n
A traditional solution to this is to use a factory method, so that the method name tells you whether it’s going before or after.<\/p>\n
struct node\r\n{\r\n    node* prev = this;\r\n    node* next = this;\r\n\r\n    node() = default;\r\n\r\n    static node create_after(node* other) <\/span>\r\n    {                                     <\/span>\r\n        node n{ other->prev, other };     <\/span>\r\n        n.prev->next = &n;                <\/span>\r\n        n.next->prev = &n;                <\/span>\r\n        return n;                         <\/span>\r\n    }                                     <\/span>\r\n    \u00a0                                     <\/span>\r\n    static node create_before(node* other)<\/span>\r\n    {                                     <\/span>\r\n        node n{ other, other->next };     <\/span>\r\n        n.prev->next = &n;                <\/span>\r\n        n.next->prev = &n;                <\/span>\r\n        return n;                         <\/span>\r\n    }                                     <\/span>\r\n};\r\n\r\n\/\/ usage\r\nnode a;\r\nnode b = node::create_after(&a); \/\/ a->b\r\nnode c = node::create_before(&b); \/\/ a->c->b\r\n<\/pre>\n
Unfortunately, this doesn’t work, or at least isn’t guaranteed to work, because copy elision is not guaranteed for named return values.<\/p>\n
I tried to think of ways to get guaranteed copy elision while simultaneously having access to the address of the object, but the only way I could come up with was to overload the constructor, say by using a tag type.<\/p>\n
struct place_after_t {};                       <\/span>\r\ninline constexpr place_after_t place_after{};  <\/span>\r\n\u00a0                                              <\/span>\r\nstruct place_before_t {};                      <\/span>\r\ninline constexpr place_before_t place_before{};<\/span>\r\n\r\nstruct node\r\n{\r\n    node* prev = this;\r\n    node* next = this;\r\n\r\n    node() = default;\r\n\r\n    \/\/ Construct a node after a specific node\r\n    node(place_after_t<\/span>, node* other) :\r\n        prev(other),\r\n        next(other->next)\r\n    {\r\n        prev->next = this;\r\n        next->prev = this;\r\n    }\r\n\r\n    \/\/ Construct a node before a specific node\r\n    node(place_before_t<\/span>, node* other) :\r\n        prev(other->prev),\r\n        next(other)\r\n    {\r\n        prev->next = this;\r\n        next->prev = this;\r\n    }\r\n\r\n    static node create_after(node* other) <\/span>\r\n    {                                     <\/span>\r\n        return { place_after, other };    <\/span>\r\n    }                                     <\/span>\r\n    \u00a0                                     <\/span>\r\n    static node create_before(node* other)<\/span>\r\n    {                                     <\/span>\r\n        return { place_before, other };   <\/span>\r\n    }                                     <\/span>\r\n};\r\n\r\n\/\/ Sample usage 1: Using tags\r\nnode a;\r\nnode b(place_after, &a); \/\/ list is a->b\r\nnode c(place_before, &b); \/\/ list is  a->c->b\r\n\r\n\/\/ Sample usage 2: Using factories\r\nnode a;\r\nnode b = node::create_after(&a); \/\/ list is a->b\r\nnode c = node::create_before(&b); \/\/ list is  a->c->b\r\n<\/pre>\n
Or maybe we are looking at it the wrong way, and really the functionality we want are create_after<\/code> and create_before<\/code> instance methods.<\/p>\n
struct node\r\n{\r\n    node* prev = this;\r\n    node* next = this;\r\n\r\n    node() = default;\r\n\r\n    node create_after() { return { place_after, this }; }\r\n    node create_before() { return { place_before, this }; }\r\n\r\nprivate:\r\n    struct place_after_t {};\r\n    inline constexpr place_after_t place_after{};\r\n\r\n    struct place_before_t {};\r\n    inline constexpr place_before_t place_before{};\r\n\r\n    node(place_after_t, node* other) :\r\n        prev(other),\r\n        next(other->next)\r\n    {\r\n        prev->next = this;\r\n        next->prev = this;\r\n    }\r\n\r\n    node(place_before_t, node* other) :\r\n        prev(other->prev),\r\n        next(other)\r\n    {\r\n        prev->next = this;\r\n        next->prev = this;\r\n    }\r\n};\r\n\r\n\/\/ Sample usage\r\nnode a;\r\nnode b = a.create_after(); \/\/ list is a->b\r\nnode c = b.create_before(); \/\/ list is a->c->b\r\n<\/pre>\n
The moral of the story, I think, is that if you want to force copy elision of an object whose address must be known before it is returned, you have to do it from the constructor, because that’s the only time guaranteed copy elision will give you the object’s address.<\/p>\n","protected":false},"excerpt":{"rendered":"
Trying to force copy elision.<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25],"class_list":["post-110145","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"
Trying to force copy elision.<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/110145","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=110145"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/110145\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=110145"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=110145"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=110145"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}