Implementing std::list emplace method( setting tail node to point to the right location)

[TheToaster]

First of all, your operator-- returns a reference, and thus you are returning a reference to a local iterator that is going to be destroyed at the end of the function. You will thus be returning an invalid reference.

Secondly, when you checked for nullptr, you didn't actually change what the iterator is pointing to. You need node to be the same as tail when it is a nullptr, then you have to return the object itself. You need to actually change "this" in the case of nullptr to be tail.

Remember what operator--() is supposed to do. It decrements, and then stores the result to the actual variable being operated on. When you do --X, X is actually changed. You don't just return a copy of a decremented X.

[hbcpp]

Secondly, when you checked for nullptr, you didn't actually change what the iterator is pointing to. You need node to be the same as tail when it is a nullptr, then you have to return the object itself.

Do you mean something like this:

         iterator& operator--()
        {
            if(node == nullptr)
            {
                node = tail->prev;

                return *this;
            }

            node = node->prev;
            return *this;
        }

I had tried that and it also threw errors.

[TheToaster]

node = tail->prev;

No. Why are you skipping the tail node?

Also, it isn't really helpful to say "it threw errors" when you don't specify what errors you receive

[hbcpp]

No. Why are you skipping the tail node?

No specific reason, just was like the regular implementation. Just wanted to see if it works.

Also, it isn't really helpful to say "it threw errors" when you don't specify what errors you receive

Sorry, here is the error:
List.h|84|error: invalid use of non-static data member 'List<int>::tail'|

I tried making tail static just to see what would happen and it complained about it needing constexpr. Added it and it threw an error wherever the tail was used like this for instance:
head = tail = new_node;

The error:
\List.h|682|error: assignment of read-only variable 'List<Point>::tail'|

[TheToaster]

Because it seems that tail is not a data member of iterator. It seems you might have to work around that somehow then. You might need to change the end() implementation to somehow convey to the iterator type that it is pointing to "past" the tail node. How you do this is up to you. The iterator does not know what "tail" is because it is not a member of List. It is separate. This could be done through, for example, a boolean flag set by end() in the iterator. You could follow the other approach where it wraps around to the node at the beginning, etc.

[hbcpp]

Ok, I will try to come up with a solution.
I will let you know when I do it. Thanks

[hbcpp]

I came up with a workaround solution:
I added another Node pointer and a constructor that would take that Node pointer.
So my iterator class is like this:

class iterator : public std::input_iterator_tag
{
    Node * node = nullptr;
    Node* tail_t = nullptr;

    friend class List;

    iterator(Node* p) : node(p) {}
    iterator(Node* p, Node* t) : node(p), tail_t(t) {}

public:
    
    //...

    reference operator*()
    {
        if( ! node)
            return tail_t->data;

        return node->data;
    }

    //...

    iterator& operator--()
    {
        if(node == nullptr)
        {
            node = tail_t->prev;
            return *this;
        }

        node = node->prev;
        return *this;
    }

    //...

    iterator operator--(int)
    {
        if(node == nullptr)
        {
            Node* temp = this->node;
            node = tail_t->prev;

            return temp;
        }

        Node* temp = this->node;
        node = node->prev;
        return temp;
    }

    // ...
};

And my end() is now like this:

template<typename T>
typename List<T>::iterator List<T>::end() noexcept
{
    return iterator(nullptr, tail);
}

However, I came across the same problem I faced with reverser iterators:

for(auto e = some_list.end(); e != some_list.begin(); e--)

This for loop will not print the last element that is contained in the head Node. The prob is here in begin():

template<typename T>
typename List<T>::iterator List<T>::begin() noexcept
{
    return iterator(head);
}

When comparing the loop iterator against the begin(), it will eventually get to head and breaking and thus leaving out the data form head.

I have been trying to come up with a workaround for the past few hours but nothing yet.

[TheToaster]

for(auto e = some_list.end(); e != some_list.begin(); e--)

This is not a reverse iterator. This is a regular iterator. Technically it shouldn't even work because you are dereferencing the end() element, which is invalid. https://en.cppreference.com/w/cpp/iterator/make_reverse_iterator

See mbozzi's example of how he implemented reverse iterators.

[hbcpp]

@TheToaster
Sorry for the late reply, I got distracted by some other stuffs this past week.

This is not a reverse iterator.

No, I didn't say it was a reverse iterator, just said that with this,
for(auto e = some_list.end(); e != some_list.begin(); e--)
I had the same probs I had with reverse iterators from my code.

[hbcpp]

@mbozzi
I have been going over the code you gave me. I am trying to understand how new elements are added into the list but it is proving hard to understand.

The mechanism used and the approach syntax is very is being a little difficult for me to understand.

When I say 'undestand' I mean understand it enough to be able to reproduce / implement it in my code by my own in my code.

[mbozzi]

I am trying to understand how new elements are added into the list but it is proving hard to understand.

Because the prototypical code does not attempt to support allocators, the code can be simplified somewhat.

Here is an improved version of the list class template:
http://coliru.stacked-crooked.com/a/abd5ae010f58210c
Hopefully the most confusing parts have been removed.

I've discussed some aspects of the original code I posted with @TheToaster over several days last week. It might be helpful. Here's our discussion, somewhat edited. Hopefully I did an acceptable job of piecing the email back together.

>>>>>Hi mbozzi,
>>>>>
>>>>>I just saw your code for making a linked list and I had a few
>>>>>questions about your approach. First, what is the technique you are
>>>>>using in which you derive the list nodes from a nontemplate abstract
>>>>>base class, but have list node itself be a template? I have seen this
>>>>>elsewhere but I'm not sure what it is useful for or in what
>>>>>situations to use it.
>>>>>
>>>>Hi Toaster,
>>>>
>>>>I made a design mistake. There shouldn't be any inheritance in the
>>>>definition of list_node.
>>>I see.  Also, what is the purpose of using std::aligned_storage to
>>>manually construct/destroy the object in that buffer? What's the
>>>benefit of doing this versus using new/delete?
>>
>>It's a demonstration. It isn't strictly necessary because
>>the list doesn't provide allocator support.
>>
>>It's a more-or-less attractive solution because it avoids an
>>additional allocation per node and an extra indirection for element
>>access - which would be required given a definition like
>>
>>template <typename T> struct list_node: public list_node_base
>>{
>>  T* data_;
>>};
>>
>>Those two factors (overhead from allocation and indirection) are
>>primary reasons why linked data structures perform so badly
>>relative to arrays.
>>
>>We could also define list_node<T> as
>>
>>template <typename T> struct list_node: public list_node_base
>>{
>>  // This constrctor template conflicts with copy & move constructors.
>>  template <typename... Args> list_node(Args&&... args)
>>    : data(std::forward<Args>(args)...) {}
>>
>>  T data_;
>>};
>>
>>But a perfect-forwarding constructor must be provided to avoid
>>default-constructing T. This seems to be viable.
>>
>>>Also, what is the purpose of having the root_ node be a
>>>size_type?
>>That's the design mistake we've both noticed. It's not really the
>>inheritance that is an issue - it's this.
>>
>>The idea was to have root_ store the size of the list. This
>>is a patently stupid choice.
>>
>>>Maybe this is why you had it as a base class? So that the next node
>>>for root_ wouldn't have to be a list_node<size_type>, but it could
>>>be a list_node<T> for some type T?
>>
>>Yes, that's exactly why. A much better alternative is to define the
>>representation of list<T> as
>>
>>template <typename T> class list
>>{
>>  size_type size_;
>>  list_node_base root_;
>>public:
>> // ...
>>};
>>
>>And maintain the list's size outside of the aligned buffer.
>>
>>>But even so, what is the purpose of root in the first place and why
>>>does begin() return root_.next?
>>
>>root_ represents both
>>a.) the node after the last element in the list; and
>>b.) the node before the beginning of the list.
>>
>>We're able to use the same node for both purposes because the list is
>>circular. Hopefully the diagram helps:
>>
>>1st and 2nd are the first and second nodes inserted before the end
>>node as-if by emplace(end(), x):
>>
>>     end               end
>>      +                 +
>>     |                 |
>>   +--v--+           +--v--+     +-----+     +-----+
>>+-->root_<--+     +-->root_<-----> 1st <-----> 2nd <--+
>>|  +--^--+  |     |  +-----+     +--^--+     +-----+  |
>>|     |     |     |                 |                 |
>>|     +     |     |                 +                 |
>>|   begin   |     |               begin               |
>>|           |     |                                   |
>>+-----------+     +-----------------------------------+
>>
>>
>>This representation is chosen because it provides a simplifying invariant:
>>every node always has adjacent nodes. This way we never need to
>>consider the special case where a link is the null pointer.
>
>You said a better way to define the list class is as follows:
>
>template <typename T> class list
>{
>  size_type size_;
>  list_node_base root_;
>public:
> // ...
>};
>
>Where, I assume, list_node_base is a struct that looks like this,
>right?:
>
>struct list_node_base
>{
>    list_node_base* next;
>    list_node_base* prev;
>};
>
>But if that's the case, that means inheritance would still need to be
>involved and that there would still need to be a list_node template
>class that derives from list_node_base, correct? What's the point of
>creating the base class in this instance if list_node<T> will always
>be a single type (like list_node<int> or list_node<double>)? Couldn't
>you just put the next and prev pointers inside the list_node<T> class
>itself and thus the list class definition would look like this?
>
>template <typename T> class list
>{
>  size_type size_;
>  list_node<T> root_;
>public:
> // ...
>};

The problem is that sizeof(list_node<T>) could be arbitrarily
large depending on T. Since the list's
root_ node doesn't maintain any list element, it's a waste of
the user's memory to include storage for one.

Consider:

template <typename T> struct list_a
{
  size_type size_;
  list_node_base root_;
};

template <typename T> struct list_b
{
  size_type size_;
  list_node<T> root_;
};

struct big { char x[100'000'000]; };

int main()
{
  std::cout << "sizeof(list_a): " << sizeof(list_a<big>) << '\n';
  std::cout << "sizeof(list_b): " << sizeof(list_b<big>) << '\n';
}
http://coliru.stacked-crooked.com/a/8667c7d430038a12

>What operations does an iterator need to 
>provide in order to be able to construct a reverse iterator from it
>using std::make_reverse_iterator?

The underlying iterator must be a BidirectionalIterator:
http://eel.is/c++draft/reverse.iterators#reverse.iter.requirements-1
I added a note to the cppreference page.