Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 3 down vote accepted

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
}
share|improve this answer
    
+1. Yes, I noticed later that it's a list with a doubly linked list as underlying data-structure. Can you give me some hints how to avoid shallow copy inside destructor? –  Kaidul Islam Aug 25 at 13:55
    
The destructor doesn't copy, so you have to avoid it in the assignment operator and the copy constructor. How to write something? I'll add it to the answer. –  Conclusio Aug 25 at 13:58
    
yes. its inside copy constructor. Typo! –  Kaidul Islam Aug 25 at 14:01
    
"Your iterators are wrong in general since the memory isn't consecutive. You have to implement your own." - can you check my edit? –  Kaidul Islam Aug 25 at 14:17
1  
@KaidulIslam They still are. First of all, reverse_iterator is a class template, so you have to specify the template argument. Furthermore pointers doesn't suffice as iterators since the steps from an object to it's adjacent objects is not as easy as an increase / decrease of the adress. You have to access the underlying nodes next and prev pointers. Hence the iterator type must an own class. –  Conclusio Aug 25 at 14:25

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.
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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