5
\$\begingroup\$

List.h

#pragma once
#ifndef GUARD_LIST_H
#define GUARD_LIST_H

#include "List.h"
#include <stdexcept>
#include <iostream>

template<typename T>
class List
{
    struct Node
    {
        Node* prev;
        T key;
        Node* next;

        Node(Node* p, T k, Node* n): prev{p}, key{k}, next{n} {}
    };
public:
    //default constructor creates a sentinal object
    List() : sz{ 0 }, head{ new Node(nullptr, T(), nullptr) }, tail{ head } { }
    explicit List(std::istream& is):sz{ 0 }, head{ new Node(nullptr, T(), nullptr) }, tail{ head } { read_in(is); }
    ~List();

    //types
    using iterator = Node*;
    using const_iterator = const Node*;
    using value_type = T;
    using reference = T&;
    using const_reference = const T&;
    using size_type = size_t;

    //functions
    iterator begin() { return head; }
    const_iterator begin() const { return head; }
    iterator end() { return tail; }
    const_iterator end() const { return tail; }

    reference front() { return head->key; }
    const_reference front() const { return head->key; }
    reference back() { return tail->prev->key; }
    const_reference back() const { return tail->prev->key; }


    bool empty() const { return head == tail ; }
    size_type size() const { return sz; }

    iterator operator++()   { return this->next; }
    iterator operator--() { return this->prev; }
    //std::ostream& operator<<(std::ostream& os) { os <<  }

    //modifier function
    void push_back(value_type);
    void erase(iterator);
    void pop_back();
    void push_front(value_type);
    void pop_front();

    iterator search(const value_type key) const
    {
        iterator x = head;
        while (x != end() && x->key != key)
        {
            x = x->next;
        }
        return x;
    }

    void insert(iterator pos, const value_type key)
    {
        if (empty())
        {
            iterator x = new Node(nullptr, key, tail);
            head = x;
            tail->prev = x;
        }
        else //if not empty
        {
            if (pos == head)
            {
                iterator x = new Node(nullptr, key, head);
                head->prev = x;
                head = x;
            }
            else
            {
                if (pos == tail)
                {
                    iterator x = new Node(tail->prev, key, tail);
                    tail->prev->next = x;
                    tail->prev = x;
                }
                else
                {
                    iterator x = new Node(pos, key, pos->next);
                    pos->next->prev = x;
                    pos->next = x;
                }
            }
        }
        ++sz;
    }

private:

    std::istream& read_in(std::istream& is)
    {
        if (is)
        {
            for (value_type x; is >> x; )
                push_back(x);
        }

        is.clear();
        return is;
    }

    size_type sz;
    iterator head;
    iterator tail;
};

template<typename T>
List<T>::~List()
{
    iterator tmp;
    for (;head;head = tmp) {
        tmp = head->next;
        delete head;
    }
}


template<typename T>
inline void List<T>::push_back(value_type key)
{
    insert(tail, key);
}

template<typename T>
inline void List<T>::erase(iterator pos)
{
    if (empty())
        throw std::domain_error("list is empty.");
    else
    {
        if (pos == head)
        {
            iterator x = head;
            head = head->next;
            head->prev = nullptr;
            delete x;
        }
        else
        {
            iterator x = pos;
            pos->prev->next = pos->next;
            pos->next->prev = pos->prev;
            delete x;
        }
        --sz;
    }
}

template<typename T>
inline void List<T>::pop_back()
{
    erase(tail->prev);
}

template<typename T>
inline void List<T>::push_front(value_type key)
{
    insert(head, key);
}

template<typename T>
inline void List<T>::pop_front()
{
    erase(head);
}

#endif // !GUARD_LIST_H

The above code compiled and worked fine.

I was getting the following errors when I tried to separate interface and implementation into header and source files respectively.

Error

Any sugguestions? I am just learning C++, data structures and algorithms. Thank you.

\$\endgroup\$
  • 1
    \$\begingroup\$ To be clear: is your code currently compiling or not? \$\endgroup\$ – jacwah Nov 5 '16 at 19:25
  • \$\begingroup\$ @jacwah the first block of codes "List.h" compiles and runs without errors. \$\endgroup\$ – aig Nov 5 '16 at 19:26
  • \$\begingroup\$ No compilation error when I have interface and definition (implementation) in the header file. Problem arises when i separate them \$\endgroup\$ – aig Nov 5 '16 at 19:30
  • \$\begingroup\$ Please clarify if the entirety of the code works, or remove the parts that do not work. All code posted on Code Review must be working as intended. See the on-topic page for details. \$\endgroup\$ – Phrancis Nov 5 '16 at 19:31
  • 2
    \$\begingroup\$ As it's a template class the definitions should be in the header file anyway, you don't need a .cpp file. The class is only compiled when it gets used somewhere and given a specific type. Therefore the compiler needs to see the entire implementation to generate a class for that type. \$\endgroup\$ – John Franklin Nov 6 '16 at 14:43
1
\$\begingroup\$

Iterator and nodes

I would decouple the linked list nodes from the iterators. As of now, in order to iterate over your list, a person must write

for (auto i = lst.begin(); i != lst.end(); i = i ->next)
{
    cout << i->key << " ";
}

which is not quite idiomatic C++. So. What you could do is to manipulate the data in terms of Node s and leave the iterators what they are supposed to do. Also, what comes to the iterators, you could declare something like

struct Node_iterator {
    Node_iterator(Node* node) : current_node(node) {}
    Node* current_node;

    void operator++() { current_node = current_node->next; }
    void operator--() { current_node = current_node->prev; }
    T operator*() { return current_node->key; }
    bool operator!=(Node_iterator&& other)
    {
        return current_node != other.current_node;
    }
};

Taking the above, and rewriting the list algorithms in terms of nodes and not iterators, may lead to a more idiomatic iteration construct:

for (auto i = lst2.begin(); i != lst2.end(); ++i)
{
    cout << *i << " ";
}
\$\endgroup\$
0
\$\begingroup\$
#include <stdexcept>
#include <iostream>
#include "Lish.h"

template<typename T>

class List
{
    struct Node
    {
        Node* prev;
        T key;
        Node* next;

        Node(Node* p, T k, Node* n) : prev{ p }, key{ k }, next{ n } {}
    };


    struct Node_iterator {
        Node* current_node;
        Node_iterator(Node* node) : current_node{ node } {};

        void operator++() { current_node = current_node->next; }
        void operator--() { current_node = current_node->prev; }
        T operator*() { return current_node->key; }
        bool operator!=(const Node_iterator& other) {
            return current_node != other.current_node;
        }
        bool operator==(const Node_iterator& other) {
            return current_node == other.current_node;
        }
    };

public:
    //default constructor creates a sentinal object
    List();
    explicit List(std::istream& is);
    ~List();

    //copy, move constructors and assignments
    List(const List<T>& rhs);
    List<T>& operator=(const List<T>& rhs);
    List(List<T>&& rhs);
    List<T>& operator=(List<T>&& rhs);

    //member types
    using iterator = Node_iterator;
    using const_iterator = const Node_iterator;
    using value_type = T;
    using reference = T&;
    using const_reference = const T&;
    using size_type = size_t;

    //Iterators
    iterator begin() {
        iterator node(head);
        return node;
    }
    const_iterator begin() const {
        iterator node(head);
        return node;
    }
    iterator end() {
        iterator node(tail);
        return node;
    }
    const_iterator end() const {
        iterator node(tail);
        return node;
    }

    //Element access
    reference front() { return *begin(); }
    const_reference front() const { return *begin(); }
    reference back() { return *end()-- }
    const_reference back() const { return *end()--; }
    bool empty() const { return begin().current_node == end().current_node; }
    size_type size() const { return sz; }

    //modifier function
    void insert(iterator, const value_type); //insert an element to a given position
    void erase(iterator); //delete a node in a given iterator
    void push_back(const value_type); //inserts an element to the end
    void pop_back(); //removes the last element
    void push_front(const value_type); //inserts an element to the beginnning
    void pop_front(); //removes the first element
    iterator search(const value_type) const; //searches for the position of an element

private:
    size_type sz;
    Node* tail;
    Node* head;

    std::istream& read_in(std::istream& is);
};
#endif // !GUARD_LIST_H

template<typename T>
List<T>::List() : sz{ 0 }, tail{ new Node(nullptr, T(), nullptr) }, head{ tail }
{
}

template<typename T>
List<T>::List(std::istream & is) : sz{ 0 }, tail{ new Node(nullptr, T(), nullptr) }, head{ tail }
{
    read_in(is);
}

template<typename T>
List<T>::~List()
{
    auto x = head;
    auto y = x;
    while (x != nullptr)
    {
        y = x->next;
        delete x;
        x = y;
    }
}

template<typename T>
std::istream& List<T>::read_in(std::istream& is)
{
    if (is)
    {
        for (value_type x; is >> x; )
            push_back(x);
    }

    is.clear();
    return is;
}

template<typename T>
void List<T>::insert(iterator pos, const value_type key)
{
    if (empty())
    {
        auto x = new Node(nullptr, key, tail);
        head = x;
        tail->prev = x;
    }
    else //if not empty
    {
        if (pos == begin())
        {
            auto x = new Node(nullptr, key, head);
            head->prev = x;
            head = x;
        }
        else
        {
            if (pos == end())
            {
                auto x = new Node(tail->prev, key, tail);
                tail->prev->next = x;
                tail->prev = x;
            }
            else
            {
                auto x = new Node(pos.current_node, key, pos.current_node->next);
                pos.current_node->next->prev = x;
                pos.current_node->next = x;
            }
        }
    }
    ++sz;
}

template<typename T>
void List<T>::erase(iterator pos)
{
    if (empty())
        throw std::domain_error("list is empty.");
    else
    {
        if (pos == begin())
        {
            auto x = head;
            head = head->next;
            head->prev = nullptr;
            delete x;
        }
        else
        {
            auto x = pos;
            pos.current_node->prev->next = pos->next;
            pos.current_node->next->prev = pos->prev;
            delete x;
        }
        --sz;
    }
}

template<typename T>
void List<T>::push_back(const value_type key)
{
    iterator node(tail->prev);
    insert(node, key);
}

template<typename T>
inline void List<T>::pop_back()
{
    iterator node(tail->prev);
    erase(node);
}

template<typename T>
void List<T>::push_front(const value_type key)
{
    insert(begin(), key);
}

template<typename T>
void List<T>::pop_front()
{
    erase(begin());
}

template<typename T>
typename List<T>::iterator List<T>::search(const value_type key) const
{
    iterator x(head);
    while (x != end() && x->key != key)
    {
        x = x++;
    }
    return x;
}

template<typename T>
inline List<T>::List(const List<T>& rhs) : sz{ 0 }, tail{ new Node(nullptr, T(), nullptr) }, head{ tail }
{
    if (!rhs.empty())
    {
        head = new Node(nullptr, rhs.head->key, nullptr);
        iterator x(rhs.head->next);
        iterator y(head);
        auto counter = 1;

        while (x != rhs.end())
        {
            Node* z = new Node(y.current_node, x.current_node->key, nullptr);
            y.current_node->next = z;
            x = x.current_node->next;
            y = z;
            ++counter;
        }

        tail->prev = y.current_node;
        tail->prev->next = tail;
        sz = counter;   //number of objects copied
    }
}

template<typename T>
inline List<T>& List<T>::operator=(const List<T>& rhs)
{
    if (this == &rhs)
        return *this;

    //delete old members
    auto a = head;
    auto b = a;
    while (a != nullptr)
    {
        b = a->next;
        delete a;
        a = b;
    }

    //assign new members from rhs
    head = new Node(nullptr, rhs.head->key, nullptr);
    iterator x(rhs.head->next);
    iterator y(head);
    auto counter = 1;

    while (x != rhs.end())
    {
        Node* z = new Node(y.current_node, x.current_node->key, nullptr);
        y.current_node->next = z;
        x = x.current_node->next;
        y = z;
        ++counter;
    }

    tail = new Node(nullptr, T(), nullptr); //because older tail would have been deleted.
    tail->prev = y.current_node;
    tail->prev->next = tail;
    sz = counter;   //number of objects copied

    return *this;
}

template<typename T>
inline List<T>::List(List<T>&& rhs) : sz{ rhs.sz }, tail{ rhs.tail }, head{ rhs.head }
{
    rhs.sz = 0;
    rhs.tail = nullptr;
    rhs.head = nullptr;
}

template<typename T>
inline List<T>& List<T>::operator=(List<T>&& rhs)
{
    if (this == &rhs)
        return *this;

    //delete old members
    auto a = head;
    auto b = a;
    while (a != nullptr)
    {
        b = a->next;
        delete a;
        a = b;
    }

    sz = rhs.sz;
    tail = rhs.tail;
    head = rhs.head;

    rhs.sz = 0;
    rhs.tail = nullptr;
    rhs.head = nullptr;

    return *this;
}

Here is an improvement to my above question with a few improvements.

  • separated nodes from iterators
  • added copy and move constructors
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.