7 Replies - 599 Views - Last Post: 21 May 2020 - 06:24 AM Rate Topic: -----

#1 hb_code_is_life   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 9
  • Joined: 18-April 20

Implement C++ std::list emplace method

Posted 20 May 2020 - 01:19 PM

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!

Is This A Good Question/Topic? 0
  • +

Replies To: Implement C++ std::list emplace method

#2 hb_code_is_life   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 9
  • Joined: 18-April 20

Re: Implement C++ std::list emplace method

Posted 20 May 2020 - 01:28 PM

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!
Was This Post Helpful? 0
  • +
  • -

#3 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 7509
  • View blog
  • Posts: 25,287
  • Joined: 05-May 12

Re: Implement C++ std::list emplace method

Posted 20 May 2020 - 04:52 PM

If you didn't learn how to implement a list without a tail node pointer, why start now? Just implement emplace() with how you think it best to do so.

Be aware, though that implementing the standard library containers is not simply a matter of copying the interface. You are also required to implement the performance guarantees as required for that container as determined by the C++ Language Committee. That means that if they say that a particular function on a container is supposed to have at least an O(1) or an O(n) performance characteristic, you would need to also comply. I suspect that the tail pointer is there to comply with the O(1) requirement for adding an item to the end of the list.
Was This Post Helpful? 0
  • +
  • -

#4 #define   User is offline

  • Cannot compute!
  • member icon

Reputation: 1866
  • View blog
  • Posts: 6,736
  • Joined: 19-February 09

Re: Implement C++ std::list emplace method

Posted 20 May 2020 - 07:56 PM

The tail pointer and the end iterator are different.

Here when a for loop is used to iterate over a sequence container, and when the iterator equates to the tail node the value is printed, but when the iterator equates to the end iterator the loop is exited.

  for (auto it = std::begin(container); it!=std::end(container); ++it)
    std::cout << ' ' << *it;



Sequence container (C++)
Was This Post Helpful? 0
  • +
  • -

#5 Salem_c   User is offline

  • void main'ers are DOOMED
  • member icon

Reputation: 2463
  • View blog
  • Posts: 4,614
  • Joined: 30-May 10

Re: Implement C++ std::list emplace method

Posted 20 May 2020 - 08:37 PM

Also here -> https://www.cplusplu...eginner/270616/
Was This Post Helpful? 1
  • +
  • -

#6 hb_code_is_life   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 9
  • Joined: 18-April 20

Re: Implement C++ std::list emplace method

Posted 21 May 2020 - 06:00 AM

View PostSkydiver, on 20 May 2020 - 04:52 PM, said:

If you didn't learn how to implement a list without a tail node pointer, why start now? Just implement emplace() with how you think it best to do so.

How would I implement the end() without the tail node?
Was This Post Helpful? 0
  • +
  • -

#7 hb_code_is_life   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 9
  • Joined: 18-April 20

Re: Implement C++ std::list emplace method

Posted 21 May 2020 - 06:18 AM

View PostSalem_c, on 20 May 2020 - 08:37 PM, said:


I am the one who posted the question in that forum.
Was This Post Helpful? 0
  • +
  • -

#8 hb_code_is_life   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 9
  • Joined: 18-April 20

Re: Implement C++ std::list emplace method

Posted 21 May 2020 - 06:24 AM

View Post#define, on 20 May 2020 - 07:56 PM, said:

The tail pointer and the end iterator are different.

Here when a for loop is used to iterate over a sequence container, and when the iterator equates to the tail node the value is printed, but when the iterator equates to the end iterator the loop is exited.

So how wwill I set the tail pointer in order to make it right and how would I define my end() then?
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1