STL List Implementation

Question

I've implemented a simple C++ STL like list. It's pretty simple, all the constructors and methods haven't been implemented here, but majors are.

#ifndef list_H
#define list_H

#include <iostream>
#include <stdexcept>

template <typename T>
class list {
public:
    list <T> & operator = (const list<T> &);
    ~list();
    /* Modifiers */
    void push_back(T&& data);
    void push_back(T const& data);
    void push_front(T&& data);
    void push_front(T const& data);
    void pop_back();
    void pop_front();
    void swap(list &x);
    void clear();

    /* Iterators */
    typedef T* iterator;
    typedef T* const const_iterator;

    const_iterator begin() const; // cbegin
    iterator begin();

    const_iterator end() const; //cend()
    iterator end();

    const_iterator rbegin() const;
    iterator rbegin();

    const_iterator rend() const;
    iterator rend();

    /* Capacity */
    size_t size() const;
    bool empty() const;

    /* Element Access */
    T& front();
    T const& front() const;

    T& back();
    T const& back() const;

    T& at(T const indx);
    T const& at(T const indx) const;

    T& operator[] (T const indx);
    T const& operator[] (T const indx) const;

private:
    struct node {
        int data;
        node *next, *prev;
        node(T const& data, node* next, node* prev)
            : data(data)
            , next(next)
            , prev(prev) {
        }
        node(T&& data, node* next, node* prev)
            : data(std::move(data))
            , next(next)
            , prev(prev) {
        }
    };
    int elements = 0;
    node *head = nullptr;
    node *tail = nullptr;
};

template <typename T>
list <T> & list<T>::operator = (const list<T> & that) {
    node* tmp = head;
    while(head) {
        tmp = head;
        head = head->next;
        delete tmp;
    }
    elements = that.elements;
    head = that.head;
    tail = that.tail;
}

template <typename T>
list <T>::~list() {
    node* tmp;
    while(head) {
        tmp = head;
        head = head->next;
        delete tmp;
    }
}


template <typename T>
T& list<T>:: front() {
    if(head == nullptr)
        throw std::runtime_error("Invalid Action!");
    return head->data;
}

template <typename T>
T const& list<T>:: front() const {
    if(head == nullptr)
        throw std::runtime_error("Invalid Action!");
    return head->data;
}

template <typename T>
T& list<T>:: back() {
    if(tail == nullptr)
        throw std::runtime_error("Invalid Action!");
    return tail->data;
}

template <typename T>
T const& list<T>:: back() const {
    if(tail == nullptr)
        throw std::runtime_error("Invalid Action!");
    return tail->data;
}

template <typename T>
void list<T>::push_back(T const& data) {
    node* newNode = new node(data, nullptr, tail);
    if(head == nullptr)
        head = newNode;
    if(tail != nullptr)
        tail->next = newNode;
    tail = newNode;
    ++elements;
}

template <typename T>
void list<T>::push_back(T&& data) {
    node* newNode = new node(std::move(data), nullptr, tail);
    if(head == nullptr)
        head = newNode;
    if(tail != nullptr)
        tail->next = newNode;
    tail = newNode;
    ++elements;
}

template <typename T>
void list<T>::push_front(T const& data) {
    node* newNode = new node(data, head, nullptr);
    if(tail == nullptr)
        tail = newNode;
    if(head != nullptr)
        head->prev = newNode;
    head = newNode;
    ++elements;
}

template <typename T>
void list<T>::push_front(T&& data) {
    node* newNode = new node(data, head, nullptr);
    if(tail == nullptr)
        tail = newNode;
    if(head != nullptr)
        head->prev = newNode;
    head = newNode;
    ++elements;
}

template <typename T>
void list<T>::pop_front() {
    if(head == nullptr)
        throw std::runtime_error("Invalid Action");
    node *tmp = head;
    head = head->next;
    if(head != nullptr)
        head->prev = nullptr;
    --elements;
    delete tmp;
}

template <typename T>
void list<T>::pop_back() {
    if(tail == nullptr)
        throw std::runtime_error("Invalid Action");
    node *tmp = tail;
    tail = tail->prev;
    if(tail != nullptr)
        tail->next = nullptr;
    --elements;
    delete tmp;
}

template <typename T>
bool list<T>::empty() const {
    return head == nullptr;
}

template <typename T>
size_t list<T>::size() const {
    return elements;
}

template <typename T>
T& list<T>::operator[] (T const indx) {
    int cont = 0;
    node *curr = head;
    while(curr) {
        if(cont == indx)
            return curr->data;
        curr = curr->next;
        ++cont;
    }
    return nullptr;
}

template <typename T>
T const& list<T>::operator[] (T const indx) const {
    int cont = 0;
    node *curr = head;
    while(curr) {
        if(cont == indx)
            return curr->data;
        curr = curr->next;
        ++cont;
    }
    return nullptr;
}

template <typename T>
T& list<T>::at(T const indx) {
    int cont = 0;
    node *curr = head;
    while(curr) {
        if(cont == indx)
            return curr->data;
        curr = curr->next;
    }
    return nullptr;
}

template <typename T>
T const& list<T>::at(T const indx) const {
    int cont = 0;
    node *curr = head;
    while(curr) {
        if(cont == indx)
            return curr->data;
        curr = curr->next;
    }
    return nullptr;
}

template <typename T>
typename list<T>::const_iterator list<T>::begin() const {
    return head;
}

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


template <typename T>
typename list<T>::const_iterator list<T>::end() const {
    return tail;
}

template <typename T>
typename list<T>::const_iterator list<T>::rbegin() const {
    return tail;
}
template <typename T>
typename list<T>::iterator list<T>::rbegin() {
    return tail;
}
template <typename T>
typename list<T>::const_iterator list<T>::rend() const {
    return head;
}

template <typename T>
typename list<T>::iterator list<T>::rend() {
    return head;
}

template <typename T>
typename list<T>::iterator list<T>::end() {
    return tail;
}

template <typename T>
void list<T>::swap(list &that) {
    std::swap(head, that.head);
    std::swap(tail, that.tail);
    std::swap(elements, that.elements);
}

template <typename T>
void list<T>::clear() {
    node* curr = head;
    while(head) {
        curr = head;
        head = head->next;
        delete curr;
    }
    head = tail = nullptr;
    elements = 0;
}

#endif // list_H

I would appreciate all criticism relevant to code, style, flow and so forth.

Answer 1

Why does your node hold an int as data when there is a template argument T?

It is more of a linked list, therefore a std::list, not a std::deque.

Your assignment operator creates a so called flat copy, so that the two objects afterwards refer to the same piece of memory. That will at the latest crash if they're getting destructed.

Some of your functions contain the same code twice. You may solve that with private methods.

You may specify the exceptions text to find the affected method easier.

You return nullptr inside the operator[] case of the index being outside the valid range. The same goes for at. Why don't you check the index beforehand with the member elements, throw an exception in case of it being to big and then just proceed? You can skip the checking part in the operator[] since it's usually known as the unchecked version.

If you name your methods rbegin and so on, you also have to return a std::reverse_iterator.

Inside the class list<T>, you don't have to write the template arguments out in full. list means inside the class' body the same.

Your iterators are wrong in general since the memory isn't consecutive. You have to implement your own.

A possible implementation of deep copy (though I didn't test it):

list(list const& Rhs)
    : elements(Rhs.size())
{
    if(!Rhs.empty())
    {
        node* RhsIt = Rhs.head;
        node* It = new node(RhsIt->data, nullptr, nullptr);
        head = It;
        while((RhsIt = RhsIt->next) != Rhs.tail)
        {
            try
            {
                node* Next = new node(RhsIt->data, It, nullptr);
                It = It->next = Next;
            }
            catch(std::bad_alloc& Exception)
            {
                for(node* Last; head != nullptr; delete Last)
                {
                    Last = head;
                    head = head->next;
                }
                throw;
            }

        }
        tail = It;
    }
}

list& operator= (list Rhs) // Call by value
{
    swap(Rhs); // Copy and swap idiom to guarantee exception safety
}

Answer 2

Things I immediately note:

• You handle assignment but not copy-constructor. You handle moving of items but not of the entire list. Assignment should probably be implemented as copy and swap. You might make the list copyable iff the T is copyable.
• Too much repeated code in similar implementations. Would be better to try to reduce.
• Unnecessary inclusion of iostream
• Ideally invalid actions should assert not throw. In particular pop actions should never throw
• Every node requires a call to new. Can work better with some kind of pool although it is more complex to implement.