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

[hbcpp]

I am trying to implement std::list in C++.

I have began by implementing one constructor (initializer list).

And I am trying to implement the emplace(const iterator& pos, Args&&... args) method because it will make it possible for me to use it in many other methods including making the one I have already implement a lot shorter.

what I have till now 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 figured 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();

    // 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);
    }

    template<typename... Args> iterator emplace(const iterator& pos, Args&&... args );

};

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?
}

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(curr == tail)
    {
        curr = new_node;

        curr->next= nullptr;

        tail = curr->next;
        //curr->next->prev = tail;
    }
    else
    {
        curr->prev = new_node;
        new_node->next = curr;

        head = new_node;
    }
}

int main()
{
    List<int> lis({1, 2, 3, 4, 5, 6});


    for(auto e: lis)
    {
        cout << e << ' ';
    }
    cout << '\n';

    lis.emplace(lis.begin(), 78); // this line work sas expected
    lis.emplace(lis.end(), 78); // this line does't

    for(auto e: lis)
    {
        cout << e << ' ';
    }

}

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!

[TheToaster]

In line 245, you should check if curr is a nullptr, not check if it is equal to tail. The user doesn't know what "tail" is. If the user wants to emplace something at the end of the list, they will pass in List.end() as the first argument to the function.

Thus, you should make the "end()" function return a nullptr in line 205.

Then, in lines 245 - 253, you should check if the given position is a nullptr. If it is a nullptr, then you should make tail equal to new_node.

Here is some pseudocode as to how you should go about doing it. I didn't check it so it might not exactly match your code

iterator node = std::make_shared<Node>(std::forward<T>(val));

node->prev = pos ? pos->prev : tail;
node->next = pos;

if(node->prev) node->prev->next = node;
if(pos) pos->prev = node;
if(!pos) tail = node;
if(pos==head) head = node;

Also, your Node constructors are incorrect. You need to accept a variadic argument list in order to initialize the internal variable data with the required constructor arguments.

[hbcpp]

@TheToaster
After doing some research I think I might have solved the problem I been having with the tail node.
I found some code here:https://www.javatpoint.com/program-to-create-and-display-a-doubly-linked-list and used it to create my emplace_back method and after using it at some constructors I was able to solve the prob in the emplace.

Thus, you should make the "end()" function return a nullptr in line 205

So my end() method will just be like this?

iterator end() noexcept
{
    return nullptr;
}

You need to accept a variadic argument list in order to initialize the internal variable data with the required constructor arguments.

I don't understand it(variadic argument list). Could you give some code example, and also what would I need it for exactly?

Here is the Node class I am currently using:

struct Node
{
    T data;
    Node* prev = nullptr;
    Node*next = nullptr;

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

[TheToaster]

So my end() method will just be like this?

Yes. At least that's how I would do it. This way, on an empty list, begin() == end().

I don't understand it(variadic argument list). Could you give some code example, and also what would I need it for exactly?

Variadic argument lists can take a variable number of arguments. In this case, they can take any number of arguments for a user defined constructor type. For example, say a user of your linked list wants to be able to store Point objects in your list. Point has a constructor that takes both an x value and a y value. Thus, you would need your emplace_back to forward the variadic list to the Node constructors that take an argument list, and can construct a Point object with the specified values.

https://en.cppreference.com/w/cpp/language/parameter_pack

So in your Node class, consider this:
T data

What if T was Point? Its constructor requires two values, x and y, yet none of your Node constructors give it two values. The existing Node constructors only call either the move or copy constructor for a Point object, but it never calls specific user-defined constructors directly.

That's why you need a variadic template constructor for Node that can construct the data object with the given arguments that you perfect forwarded in emplace_back

[hbcpp]

@TheToaster

Variadic argument lists can take a variable number of arguments.

Do you mean something like that:

List<int> lis;
lis.emplace_back(23, 4, 5, 6, 7, 6); // this doesn't work with std::list 

I didn't understand the example with Point objects. I created a dummy Point class that takes the two values in the constructor to try to understand it but even so couldn't understand.

I tried adding this Node constructor:
template<typename... Args> Node(Args&&... args) : data({std::forward<Args>(args)...}) {}

And called it with this line of code:

List<int> lis;
lis.emplace_back(23, 4, 5, 6, 7, 6);

It throws an error:
error: cannot convert '<brace-enclosed initializer list>' to 'int' in initialization|

But I am not sure this is how the variadic argument list is meant to be used in this case.

[TheToaster]

Do you mean something like that:

No, I mean this:

struct Point
{
    Point(int x, int y);
};

//...
List<Point> list;
list.push_back(Point{2,3}); //Constructs a point with coordinates (2,3)
list.emplace_back(2,3)       //Same thing 

I tried adding this Node constructor:

You initialize data with a brace-enclosed initializer list. data in this case is an int. And int can only hold a single value. If we use the class analogy, class "int" only has a single constructor that takes an integer. It cannot take a brace-enclosed initializer list of integers.

So you should get rid of the initializer list, first of all.

Secondly,

List<int> lis;
lis.emplace_back(23, 4, 5, 6, 7, 6);

Doesn't make sense according to what I mentioned above. You aren't understanding what emplace_back is supposed to do. It is supposed to construct an element "in place" without having the user pass in a temporary object that is going to be copied/moved in. Consider this example:

struct Enemy
{
    Enemy(int HP, double percentDamage, std::string enemyName, char enemyType);
};
//...

List<Enemy> list;
list.push_back(Enemy{150, 23.5, "Zombie", 'z'}); //Uses push_back. Moves rvalue enemy into list using move ctor/copy ctor
list.emplace_back(150, 23.5, "Zombie", 'z'); //Enemy is constructed within the list, not through move/copy constructors 

Both of them, in essence, achieve the same thing. Except the latter has to take the arguments and forward it to the Enemy constructor. In order to do this, it needs to accept a variable number of arguments, because List has no idea how many parameters the Enemy constructor takes, and it needs to be determined whenever the user calls the constructor with x number of arguments.

[dutch]

Here's a simplified example of emplace.

#include <iostream>

struct Point
{
    int x, y;
    Point(int x, int y) : x(x), y(y) {}
};

std::ostream& operator<<(std::ostream& out, const Point& p)
{
    return out << '(' << p.x << ',' << p.y << ')';
}


template< class T >
class List
{
    struct Node
    {
        T     m_data;
        Node* m_next;
        
        Node(T d, Node* n=nullptr)
            : m_data(d), m_next(n)
        {}

        template<typename ...Args>
        Node(Args&& ...args)
            : m_data(std::forward<Args>(args)...), m_next(nullptr)
        {}

    };

    Node*  m_head = nullptr;
    Node*  m_tail = nullptr;
    size_t m_size = 0;

public:

    class iterator
    {
        Node* node;
    public:
        iterator(Node* n=nullptr) : node(n) {}
        bool operator!=(iterator it) { return node != it.node; }
        iterator operator++() { node = node->m_next; return *this; }
        T& operator*() { return node->m_data; }
    };

    List() = default;
    
    void push_front(const T& data)
    {
        m_head = new Node(data, m_head);
        if (!m_tail) m_tail = m_head;
        ++m_size;
    }

    template<typename ...Args>
    void emplace_front(Args&& ...args)
    {
        Node* node = new Node(std::forward<Args>(args)...);
        node->m_next = m_head;
        m_head = node;
        if (!m_tail) m_tail = m_head;
        ++m_size;
    }
    
    void push_back(const T& data)
    {
        Node* node = new Node(data);
        if (m_tail) m_tail->next = node;
        else        m_head = node;
        m_tail = node;
        ++m_size;
    }

    size_t size() const { return m_size; }

    iterator begin() { return iterator(m_head); }
    iterator end()   { return iterator();       }
};

int main()
{
    List<Point> points;
    points.push_front(Point(1, 2));
    points.emplace_front(3, 4);
    for (auto& p: points) std::cout << p << '\n';
}

I'm not sure if this is right. It might be too simplistic.

[hbcpp]

oh I see, thanks for explaining, I knew that emplace_back is to construct an element "in place". However the ellipsis confused me, got me to think that it could be to add a user-defined number of elements, again, thanks for the clarification.

No, I mean this:

With this constructor
template<typename... Args> Node(Args&&... args) : data({std::forward<Args>(args)...}) {} // I am guessing the forward is not necessary there
both the code example with Point and Enemy worked greatly, is the code above correct?

Forgot to ask this question:

Yes. At least that's how I would do it. This way, on an empty list, begin() == end().

With end() defined like that wouldn't it create problems when defining rend()?
So I defined both rend() and rbegin() like this:

template<typename T>
typename List<T>::reverse_iterator List<T>::rbegin() noexcept
{
    return reverse_iterator(begin());
}
template<typename T>
typename List<T>::reverse_iterator List<T>::rend() noexcept
{
    reverse_iterator(end());
}

it crashes here:

for(auto e = lis.rbegin(); e != lis.rend(); ++e)
{
    cout << *e << ' '; // when debugging this is where the program crashes
}

I am not sure about the cause of crash.
I am thinking that maybe I in rend() I should return begin() and in rbegin() return end().

[TheToaster]

With this constructor

That should be good. However you should probably remove either the parenthesis or the curly braces. Don't put both of them. Remember, you are passing the arguments themselves to the constructor. Not through a brace enclosed initializer list.

The forward IS necessary there, because otherwise the arguments wouldnt forward perfectly to T's constructor.

You're jumping the gun. First worry about const_iterators and iterators before trying to implement other iterator types. You havent even got the first two working.

Though reverse iterators will be exactly the same as iterators except the begin and end mechanic will be flipped, thus rbegin will return nullptr and rend will return the beginning of the container, and operator++ will actually be a decrement operation and so on. So first figure out how to implement regular iterators before trying to do more complicated stuff.

[mbozzi]

I think you're having trouble with iterators because the representation of your list isn't ideal. In general, try to design data structures and algorithms to avoid special cases.

I took a few minutes to roughly sketch one interesting representation for a doubly-linked list, below. This link contains more complete (albeit untested) code
http://coliru.stacked-crooked.com/a/ce5a3df4bc8c3321

Also keep in mind that std::list::end() is decrementable, therefore it can't be a singular iterator.

#include <iterator>
#include <new>
#include <memory>
#include <type_traits>

////////////////////////////////////////////////////////////////////////
struct list_node_base 
{
  list_node_base* next_;
  list_node_base* prev_;    
};

template <typename T>
  using naturally_aligned_storage =
    std::aligned_storage_t<sizeof (T), alignof (T)>;

template <typename T>
class list_node: public list_node_base
{
  naturally_aligned_storage<T> buf_;
  
public:
  T* ptr_value()
  {
    return std::launder(reinterpret_cast<T*>(&buf_));
  }
  
  T const* ptr_value() const 
  { 
    return static_cast<T const*>(const_cast<list_node*>(this)->ptr_value());
  }
};

template <typename... Args, typename T>
  void construct_value(list_node<T>& within, Args&&... args) 
  {
    new (within.ptr_value()) T(std::forward<Args>(args)...);
  }

template <typename T>
  void destroy_value(list_node<T>& within)
  {
    within.ptr_value()->~T();
  }

////////////////////////////////////////////////////////////////////////
template <typename T> class list;

template <typename T>
  class list_iterator
  {
    list_node_base* node_ = nullptr;
    
  public:
    using difference_type = std::ptrdiff_t;
    using iterator_category = std::bidirectional_iterator_tag;
    using value_type = T;
    using pointer = value_type*;
    using reference = value_type&;

    list_iterator() = default;
    explicit list_iterator(list_node_base* node)
      : node_{node}
    {}

    reference      operator*()     const noexcept;
    pointer        operator->()    const noexcept;
    list_iterator& operator++()    noexcept;
    list_iterator  operator++(int) noexcept;
    list_iterator& operator--()    noexcept;
    list_iterator  operator--(int) noexcept;

    bool operator==(list_iterator const&) const noexcept;
    bool operator!=(list_iterator const&) const noexcept;

    friend class list<T>;
    
  private:
    list_node<T>* value_node() const;
  };

////////////////////////////////////////////////////////////////////////
template <typename T>
  class list
  {
    // TODO(mbozzi): address exception safety requirements within list<T>
  public:
    using value_type       = T;
    using allocator_type   = std::allocator<T>;
    using pointer          = T*;
    using const_pointer    = T const*;
    using reference        = value_type&;
    using const_reference  = value_type const&;
    using size_type        = std::size_t;
    
    using iterator         = list_iterator<T>;
    using reverse_iterator = std::reverse_iterator<iterator>;

  private:
    // NOTE(mbozzi): The representation of this list is pretty clever
    // (not necessarily a good thing), but it's also a reasonably
    // accurate sketch of how a real implementation might approach
    // things. 
    // 
    // Firstly, the representation is actually circular: the last
    // element in the list links to root_.
    // Keeping this in mind, list iterators are defined in terms of a
    // pointer-to-node.  By definition, begin() refers to root_.next_
    // and end() refers to static_cast<list_node_base*>(&root_).
    // 
    // Given this representation, when the list is empty, begin() ==
    // end().  if the list is nonempty, the tail node is always
    // root_.prev_.
    // 
    // Because root_ is the end node -- a node whose buffer space
    // would otherwise be unused, that buffer is used to maintain the
    // size of the list.
    list_node<size_type> root_;
    
  public:
    ~list();
    
    list();

    // TODO(mbozzi): Implement these + moves
    list(list const& other) = delete;
    list& operator=(list const& rhs) = delete;

    iterator begin() noexcept;
    iterator end() noexcept;
    
    reverse_iterator rbegin() noexcept;
    reverse_iterator rend() noexcept;
    
    [[nodiscard]] bool empty() const noexcept;
    size_type size() const noexcept;
    
    reference front();
    reference back();

    template <typename... Args>
      reference emplace(iterator pos, Args&&...);

    void push_front(T const& x);
    void push_back (T const& x);

    iterator erase(iterator pos);
    
    void pop_front();
    void pop_back();

    void clear(); 

  private:
    void increment_size();
    void decrement_size();
  };

[hbcpp]

@TheToaster
Sorry for the late reply again. I'm happy to say that only 5 methods and reverse iterators are left for me to define. Your help has been immense since the very beginning. I wish I could do more than just say Thank You!
Anyway...

That should be good. However you should probably remove either the parenthesis or the curly braces. Don't put both of them. Remember, you are passing the arguments themselves to the constructor. Not through a brace enclosed initializer list.

The forward IS necessary there, because otherwise the arguments wouldn't forward perfectly to T's constructor.

All done thank you.

So first figure out how to implement regular iterators before trying to do more complicated stuff.

Regular iterators are working as expected for now. I did try messing around with the code to get the reverse ones workings, they worked but not 100%:

template<typename T>
typename List<T>::reverse_iterator List<T>::rbegin() noexcept
{
    return reverse_iterator(tail);
}

template<typename T>
typename List<T>::reverse_iterator List<T>::rend() noexcept
{
    return reverse_iterator(head); // the problem is here
}

When I iterate the list using them in a for loop, they work but with a problem, the last element will not be reached thus not printed.

https://onlinegdb.com/S1s8_fjiI -> this is what I have got so far.

by mbozzi

Note that std::list::end() is not dereferenceable but it is decrementable,...

By defining end() to return nullptr it will not be decrementable.

[mbozzi]

By defining end() to return nullptr it will not be decrementable.

Yes, I'm pointing out this difference between your list and the standard one. *(--std_list.end()) is a synonym for std_list.back().

The sentence I wrote was

Also keep in mind that std::list::end() is decrementable, therefore it can't be a singular iterator.

An iterator is singular when it's a sentinel not associated with any underlying sequence. An iterator represented by the null pointer is a singular iterator, as is (for example) std::istream_iterator end{} and std::regex_token_iterator end{}.

You'd need to change the representation of your iterator if you want feature parity with std::list.

[hbcpp]

@mbozzi

I think you're having trouble with iterators because the representation of your list isn't ideal. In general, try to design data structures and algorithms to avoid special cases.

Yeah I noticed that, but when I did I was far ahead in the implementation so I decided to leave it as it is, for now. I think I will be implementing std::list again with a different approach. The reason I am doing this implementation is to understand how a doubly linked list works better. I have to say it's being really tricky(specially keeping track of all the node, it has my program crashing a lot), but I am learning so much.

I took a few minutes to roughly sketch one interesting representation for a doubly-linked list...

Thanks, it will be useful when starting the new implementation from scratch. But the link is stating No such file or directory.

A question, is there any reason to place the Node and iterator classes outside list class like in the code you gave me? What changes when I place them inside like in mine and what happens when placed outside like in yours?

...therefore it can't be a singular iterator.

What does it mean for a iterator to be singular?

[TheToaster]

What does it mean for an iterator to be singular?

Consider std::istream_iterator. A default constructed istream_iterator refers to the end of the istream. Thus, it is a singular iterator because it is, like mbozzi says, merely a sentinel value and not associated with the underlying sequence.

I only suggested nullptr for simplicity, however this does bring complications when comparing iterators of different types (all end iterators will compare as equal, which is obviously incorrect). In any case, using the nullptr method is very clean aside from that if you just want a simple linked list. Obviously it seems you are trying to implement std::list yourself, but given the fact that the standard library containers have been tested multiple times by experts for efficiency, I don't think you will be able to reproduce std::list's efficiency exactly.

[mbozzi]

Is there any reason to place the Node and iterator classes outside list class?

Mostly, that's just my preference. I dislike nested classes in general because they're a pain to use out-of-line.

Here's a working link.
http://coliru.stacked-crooked.com/a/ce5a3df4bc8c3321

Edit: If we were considering a version of list with extra template parameters - e.g., for the allocator type -- making iterator a nested class would cause the iterator type to incorrectly depend on the allocator type of the container. See:
https://wg21.link/n2911

[TheToaster]

template <typename T>
  void list<T>::push_front(T const& x)
  {
    emplace(begin(), x);
  }

template <typename T>
  void list<T>::push_back(T const& x)
  {
    emplace(end(), x);
  }

Wouldn't it be better to make these forwarding references if they are going to call emplace (which takes a forwarding reference) anyways?

[mbozzi]

Wouldn't it be better to make these forwarding references if they are going to call emplace (which takes a forwarding reference) anyways?

I tried to follow the synopsis of std::list from the standard document, but I didn't have the desire to implement all the boilerplate. std::list<T>::push_back isn't a member function template (so no forwarding references are possible), but it is overloaded for rvalue T - e.g.:

namespace std
{ 
  template <typename T /* ... */>
    void list<T>::push_back(T&& x) { emplace(end(), std::move(x)); }
}

[hbcpp]

@TheToaster

I don't think you will be able to reproduce std::list's efficiency exactly.

I don't mean to, it is merely for learning purposes, as a CS student who is currently taking Algorithm and Data Structures classes it is being very useful implementing this list, as I'm understanding how it works and a lot about aspects of C++ in the discussions from questions I have been posting.

Wouldn't it be better to make these forwarding references if they are going to call emplace (which takes a forwarding reference) anyways?

I guess you're right.

@mbozzi
Taking in consideration the approach I used in my implementation: https://onlinegdb.com/S1s8_fjiI
Do you have any suggestion on how I would make my end() decrementable. I am still trying to make it so ever since you pointed out this fact.

[TheToaster]

You are using a singular iterator approach for end(). So the best way is to check in your operator-- implementation whether the node is a nullptr. If it is a nullptr, then return an iterator to tail. If not, then just use the normal implementation.

[hbcpp]

How would I do that?

Tried something like this:

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

                return iterator(tail);
            }

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

But threw errors.