Implement std::list emplace method

[hbcpp]

After these two discussions(links below) about implementing SFINAE I was ready to start coding the operations of a doubly linked list.
https://www.cplusplus.com/forum/beginner/270540/
https://www.cplusplus.com/forum/beginner/270488/

So I began by trying to implement the constructors which I did for 4 ctors which seem to be working fine, although I am not sure the implementation is correct.

But going over the methods I noticed that by implementing the emplace(const iterator& pos, Args&&... args) method it would make it possible for me to use it in many other methods including making the ones I have already implemented a lot shorter.

So I began implementing and it works fine when the iterator passed is from the method begin() but it is failing when the iterator is changed to end().
Which got me thinking that maybe I missing something, the tail node is not pointing to where it should be pointing and i haven't yet figure it how to fix it.That is the problem I need help with.

#include <iostream>


using namespace std;

template <typename T>
class List
{
    struct Node
    {
        T data;
        Node* prev = nullptr;
        Node*next = nullptr;

        Node() = default;
        Node(T d) : data(d), prev(nullptr), next(nullptr) {}
    };

    Node* head = nullptr;
    Node *tail = nullptr;
    std::size_t l_size = 0;

    //SFINAE
    template <typename Iter>
    using required_input_iterator = std::enable_if<std::is_base_of_v<std::input_iterator_tag,
          typename std::iterator_traits<Iter>::iterator_category >>;

public:
    using reference = T&;
    using const_reference = const T&;
    using size_type = std::size_t;

    class const_iterator
    {
        Node* node = nullptr;

        friend class List;

        const_iterator (Node* p) : node(p) {}

    public:
        using value_type = std::remove_reference_t<T>;

        using difference_type = std::ptrdiff_t;

        using pointer = value_type*;

        using reference = value_type&;

        using iterator_category = std::bidirectional_iterator_tag;

    public:
        const_iterator ()  = default;
        const_iterator(const const_iterator& other) : node(other.node) {}

        reference operator*()
        {
            return node->data;
        }

        T* operator->()
        {
            return node->data;
        }

        // prefix operators
        const_iterator& operator++()
        {
            node = node->next;
            return *this;
        }

        const_iterator& operator--()
        {
            node = node->prev;
            return *this;
        }

        // postfix operators
        const_iterator operator++(int)
        {
            Node* temp = this->node;
            node = node->next;
            return temp;
        }

        const_iterator operator--(int)
        {
            Node* temp = this->node;
            node = node->prev;
            return temp;
        }

        friend bool operator== (const const_iterator& lhs, const const_iterator& rhs) noexcept
        {
            return lhs.node == rhs.node;
        }

        friend bool operator!= (const const_iterator& lhs, const const_iterator& rhs) noexcept
        {
            return lhs.node != rhs.node;
        }
    };

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

        friend class List;

        iterator(Node* p) : node(p) {}

    public:
        using value_type = std::remove_reference_t<T>;

        using difference_type = std::ptrdiff_t;

        using pointer = value_type*;

        using reference = value_type&;

        using iterator_category = std::bidirectional_iterator_tag;

    public:
        iterator ()  = default;

        reference operator*()
        {
            return node->data;
        }

        reference operator->()
        {
            return node->data;
        }

        // prefix operators
        iterator& operator++()
        {
            node = node->next;
            return *this;
        }

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

        // postfix operators
        iterator operator++(int)
        {
            Node* temp = this->node;
            node = node->next;
            return temp;
        }

        iterator operator--(int)
        {
            Node* temp = this->node;
            node = node->prev;
            return temp;
        }

        friend bool operator== (const iterator& lhs, const iterator& rhs) noexcept
        {
            return lhs.node == rhs.node;
        }

        friend bool operator!= (const iterator& lhs, const iterator& rhs) noexcept
        {
            return lhs.node != rhs.node;
        }
    };

    using reverse_iterator = std::reverse_iterator<iterator>;
    using const_reverse_iterator = std::reverse_iterator<const_iterator>;

    List() = default;
    explicit List(size_type n);
    List(size_type n, const_reference v);
    List(const std::initializer_list<T>& i_list);
    template<typename InputIterator, typename = required_input_iterator<InputIterator>>
    List(InputIterator first, InputIterator last);
    List(const List& src);
    List& operator=(List src);
    List(List&& src);
    //~List();


    void assign(size_type n, const_reference v);
    void assign(const std::initializer_list<T>& i_list);
    template<typename InputIterato, typename = required_input_iterator<InputIterator>> void assign(InputIterator first, InputIterator last);

    // element acces
    reference front();
    const_reference front() const;
    reference back();
    const_reference back() const;

    // iterators
    iterator begin() noexcept
    {
        return iterator(head);
    }
    const_iterator begin() const noexcept
    {
        return iterator(head);
    }
    iterator end() noexcept
    {
        return iterator(tail);
    }
    const_iterator end() const noexcept
    {
        return iterator(tail);
    }
    const_iterator cbegin() const noexcept;
    const_iterator  cend() const;
    reverse_iterator rbegin() noexcept;
    const_reverse_iterator crbegin() const noexcept;
    reverse_iterator rend() noexcept;
    const_reverse_iterator crend() const noexcept;

    // capacity
    size_type size() const noexcept;
    bool empty() const noexcept;

    // modifiers
    void clear() noexcept;
    iterator insert(const_iterator pos, const_reference v);
    iterator insert(const_iterator pos, const T&& v);
    iterator insert(const_iterator pos, size_type n, const_reference v);
    template<typename InputIterato, typename = required_input_iterator<InputIterator>> iterator insert(InputIterator first, InputIterator last);
    iterator insert(const_iterator pos, std::initializer_list<T> i_list);
    template<typename... Args> iterator emplace(const iterator& pos, Args&&... args );
    iterator erase(const_iterator pos);
    iterator erase(const_iterator first, const_iterator last);
    void push_back(const_reference v);
    void push_back(T&& v);
    template<typename... Args> reference emplace_back(Args&&...args);
    void pop_back();
    void push_front(const_reference v);
    void push_front(T&& v);
    template<typename... Args> reference emplace_front(Args&&...args);
    void pop_front();
    void resize(size_type new_size);
    void resize(size_type new_size, const_reference v);
    void swap(List& other) noexcept;

};

[b]Because if I include the definitions of the methods the content of the post will be too long I have included full program here in this online compiler:
https://onlinegdb.com/HJSKTnMjI


I have understood the basic operations of such list like insert in the front, in the middle and in the end. But the way I learned it didn't include a tail node. Because it was just those basic function, didn't have iterators and other stuff that std::list has.

Any help is welcome! Thanks!

[helios]

end() is supposed to return an iterator to "one past the end" of the container. There's many ways to represent such an iterator. For example,

template <typename T>
class Iterator{
    List<T> *list;
    Node<T> *node;
public:
    //constructor for end()
    Iterator(List<T> &list): list(&list), node(nullptr){}
    Iterator &operator--(){
        if (!this->node){
            //TODO: error out if list is empty.
            this->node = this->list->tail;
        }else{
            //TODO: error out if node is first.
            this->node = this->node->prev;
        }
        return *this;
    }
};

[hbcpp]

I have already implemented the iterator.

My problem is when setting the tail node to point to the right location.

[helios]

The tail pointer should simply point to the last node in the list. You should update the pointer when you insert or remove at the back (including push_back() and pop_back()) and when the list goes from being empty to having one element, or vice versa.

Note that your end() member functions are incorrect according to the STL convention:

iterator end() noexcept
{
    return iterator(tail);
}
const_iterator end() const noexcept
{
    return iterator(tail);
}

You're pointing them to the last element of the list, not to one past the end. If you pass these iterators to standard algorithms they will ignore the last element.

[TheToaster]

Node* new_node = new Node(std::move(args)...);

Why are you doing this? You shouldn't std::move args. The type of Args could be an lvalue reference, so you need to handle each case accordingly.

In your Node class, you only have a single constructor that takes the type by value and you provide no other constructors. This means that a copy will ALWAYS be made. This is bad because now you cannot store move-only types in your container, or your container will always make a copy even when a move constructor can be used for temporaries. Instead of std::move you need to std::forward:

Node* new_node = new Node(std::forward<T>(args));

And you need to provide constructors in the Node class that can take const lvalue references and rvalue references to the object and handle them accordingly.

[salem c]

Also here for reference -> https://www.dreamincode.net/forums/topic/419299-implement-c-stdlist-emplace-method

[hbcpp]

@helios

Note that your end() member functions are incorrect according to the STL convention:

How would I correct it?

[helios]

See my post before that one.

[TheToaster]

And also don't forget to change the std::move to use perfect forwarding instead, like I mentioned above.

[hbcpp]

@TheToaster
Sorry for the late reply, I went on to google the differences between std::forward and std::move and had to leave in the middle of it, I am just now sitting back in front of the pc.

Instead of std::move you need to std::forward:

I have read a few SO posts on the differences between them but unfortunately they made me more confused as answers differ from one another and some seem opinion based.

Edit: this article clarified a lot for me : http://bajamircea.github.io/coding/cpp/2016/04/07/move-forward.html

I understand why I need to provide the other constructors (because without those constructors either std::forward or std::move is useless there and makes no difference using them or not, right?) but I am failing to get what difference would it make when using std::forward instead.

Why are you doing this? You shouldn't std::move args. The type of Args could be an lvalue reference, so you need to handle each case accordingly.

What exactly std::move does to an lvalue reference (example with code would be a happy bonus).

[hbcpp]

@helios

See my post before that one.

I couldn't see how that related to my problem and how to incorporate it into my existing code. And didn't quite understand the code in general.

This is the cosstructor that takes an initializer_list:

template <typename T>
List<T>::List(const std::initializer_list<T>& i_list) : l_size(i_list.size())
{
    if(l_size == 0)
        return;

    Node* temp = new Node;

    head = temp;
    temp->prev = nullptr;

    for(auto it = i_list.begin(); it != i_list.end(); ++it)
    {
        temp->data = *it;
        temp->next = new Node;
        temp->next->prev = temp;

        temp = temp->next;
    }

    tail = temp; // is this correct
}

Is that tail node pointed to the right location?

[TheToaster]

@hbcpp

typename List<T>::iterator List<T>::emplace(const iterator& pos, Args&&... args )

The && you see in the constructor definition is not a regular rvalue reference (well technically it is, but I'll get to that), it's called a forwarding reference. Forwarding references are rvalue references of type parameters of templates. When you apply an rvalue reference to a type parameter in a template, that becomes a forwarding reference, and can accept both rvalue and lvalue references. This is because of a set of rules in C++ known as reference collapsing, but those details are unnecessary for now.

All you need to know is that args can either be a const lvalue reference or an rvalue reference, or a regular lvalue ref, or a CV-qualified reference, etc. It can bind to (almost) anything. You then need to take that forwarding reference and "forward" it to an appropriate function that takes the respective rvalue/lvalue reference type. In this case, that would be your Node class. So you should define a constructor that takes rvalue refs and a constructor that takes lvalue refs.

what happens when you std::move an lvalue

Surprisingly, std::move doesn't actually "move" anything. All it is is a static_cast to an rvalue reference. If you pass an lvalue reference to std::move, the result would be an rvalue reference

Here is an example from isocpp:

void overloaded( int const &arg ) { std::cout << "by lvalue\n"; }
void overloaded( int && arg ) { std::cout << "by rvalue\n"; }
 
template< typename t >
/* "t &&" with "t" being template param is special, and  adjusts "t" to be
   (for example) "int &" or non-ref "int" so std::forward knows what to do. */
void forwarding( t && arg ) {
    std::cout << "via std::forward: ";
    overloaded( std::forward< t >( arg ) );
    std::cout << "via std::move: ";
    overloaded( std::move( arg ) ); // conceptually this would invalidate arg
    std::cout << "by simple passing: ";
    overloaded( arg );
}
 
int main() {
    std::cout << "initial caller passes rvalue:\n";
    forwarding( 5 );
    std::cout << "initial caller passes lvalue:\n";
    int x = 5;
    forwarding( x );
}

[hbcpp]

@TheToaster
Thanks for explanation, I think I got it (I hope). And look the ctors I have now in Node class:

Node(const T& d) : data(d), prev(nullptr), next(nullptr) {}
Node(T&& d) : data(std::move(d)), prev(nullptr), next(nullptr) {}

And as to the tail node problem like:

This is the constructor that takes an initializer_list:

And this emplace method:

template<typename T>
template<typename... Args>
typename List<T>::iterator List<T>::emplace(const iterator& pos, Args&&... args )
{
    Node* curr = pos.node;

    Node* new_node = new Node(std::move(args)...);

    // this is where I am having a really hard time (if the iterator I pass is the end() method)
    if(curr == tail)
    {
        curr = new Node(std::forward(args)...);

        curr->next = nullptr;

        tail = curr->next;
    }
    else // here it is working fine
    {
        curr->prev = new_node;
        new_node->next = curr;

        head = new_node;
    }

}

[TheToaster]

Change it to this:
curr = new Node(std::forward<Args>(args)...);

And you also need to change line 7. You didn't get rid of the move there either

[hbcpp]

yeah I copy pasted from the code on the online compiler. I have changed it in my code?

What about the tail node problem?

[TheToaster]

The easiest way is to have the end iterator just be a nullptr. When the list is empty, begin() == end(). When it is not empty, then begin() will point to a physical element, while end() will continue to be a nullptr. You can then define your iterator classes with increment/decrement operators taking this fact into consideration.

See helios's first post. He provides example code.

Then, you will be able to use begin() and end() in, say, a for loop. It is especially easy for a linked list to use a nullptr representation for end() because the final element in a linked list (one past the last) will be a nullptr anyways:

[node] -> [node] -> [node] -> [node] -> NULLPTR
  ^                                        ^                  
begin()                                   end()

[hbcpp]

@TheToaster
I am missing something very important as I am not understanding(in means to translate it to code) what you are saying.
I don't understand the helios' code either.

I will do a more thorough search on my part and get back to you. Thank you!