Double-ended queue and iterators

Question

I have created a double-ended container, but I have doubts about its efficiency in terms of performance. Can you please criticize the code? What can be done extra, such as shortening it?

#ifndef EXERCISE_H_
#define EXERCISE_H_

#include <iostream>

typedef unsigned short ushort;

template <typename type_t>
class list{
    type_t data;
    ushort size_;
public:
    list<type_t> * head, * tail, * next, * prev;
    list();
    virtual ~list();

    ushort &size();

    void setData(type_t);
    type_t getData();

    virtual void push_back(type_t) = 0;
    virtual type_t pop_front() = 0;

    virtual void push_front(type_t) = 0;
    virtual type_t pop_back() = 0;
    virtual type_t front() = 0;
    virtual type_t back() = 0;
    virtual void print() = 0;

};

// DEFAULT CTOR
template <typename type_t>
list<type_t>::list() : size_(0){ this->head = this->tail = this->next = this->prev = nullptr;}

// DTOR
template <typename type_t>
list<type_t>::~list() {}

template <typename type_t>
ushort & list<type_t>::size(){
    return size_;
}


template <typename type_t>
void list<type_t>::setData(type_t value){
    this->data = value;
}

template <typename type_t>
type_t list<type_t>::getData(){
    return this->data;
}

/*********************\
*   DEQUEUE CLASS
\*********************/

template <typename type_t>
class dequeue : public list<type_t> {
public:
    void push_back(type_t);
    type_t pop_front();

    void push_front(type_t);
    type_t pop_back();

    type_t front();
    type_t back();
    void print();
};

// PUSH_BACK func
template <typename type_t>
void dequeue<type_t>::push_back(type_t value){
    list<type_t> * item = new dequeue;
    if (!item) throw std::bad_alloc();

    item->setData(value);

    if (this->tail) {
        this->tail->next = item;
        item->prev = this->tail;
    }
    this->tail = item;
    ++this->size();
    if (!this->head) this->head = this->tail;
}

// POP_BACK func
template <typename type_t>
type_t dequeue<type_t>::pop_back(){
    if(!this->head) throw std::out_of_range("List is empty");

    list<type_t> * item;
    type_t value;

    if(this->tail && this->tail != this->head){
        item = this->tail;
        value = this->tail->getData();
        this->tail = this->tail->prev;
        this->tail->next = nullptr;

        delete item;
    }
    else{
        value = this->head->getData();
        delete this->head;
        this->head = this->tail = nullptr;
    }
    --this->size();
    return value;
}


template <typename type_t>
void dequeue<type_t>::push_front(type_t value){
    list<type_t> * item = new dequeue;
    if (!item) throw std::bad_alloc();

    item->setData(value);
    item->prev = nullptr;

    if(this->head){
        item->next = this->head;
        this->head->prev = item;
    }
    this->head = item;
    ++this->size();
    if(!this->tail) this->tail = this->head;
}

template <typename type_t>
type_t dequeue<type_t>::pop_front(){
    if(!this->head) throw std::out_of_range("Empty list");

    list<type_t> * item;
    type_t value;

    if(this->head && this->head != this->tail){
        value = this->head->getData();
        item = this->head;
        this->head = this->head->next;
        this->head->prev = nullptr;

        delete item;
    }
    else{
        value = this->tail->getData();
        delete this->tail;
        this->head = this->tail = nullptr;
    }

    --this->size();
    return value;
}

template <typename type_t>
type_t dequeue<type_t>::front(){
    return this->head->getData();
}

template <typename type_t>
type_t dequeue<type_t>::back(){
    return this->tail->getData();
}

template <typename type_t>
void dequeue<type_t>::print(){
    int count = this->size();
    for(int i=0; i < count; i++)
        std::cout << pop_front() << " ";
}


#endif /* EXERCISE_H_ */

Answer 1

1. I really recommend using an explicit type for your linked-list node:

   template<typename T>
   struct linked_list_node 
   {
       T datum;
       linked_list_node<T>* next;
       linked_list_node<T>* prev;
   }
   

   Then, in your actual dequeue class you would have:

   linked_list_node<T>* head;
   linked_list_node<T>* tail;
   size_t size;
   

2. Returning the size as a reference is a no-no: the caller may assign some nonsensical value to it, which will break the invariants of your dequeue.

3. When it comes to terminology, "dequeue" is actually called deque (double-ended queue). Dequeue is a canonical name for the operation of removing and returning the head node in a FIFO queue data structure.

4. Your print function is a bit ad-hoc. There are two better options:

   1. Override template<typename T> std::ostream& operator<<(std::ostream&, deque<T>&)

   2. Add iterators. After doing that, you can use:

      std::copy(dec.begin(), dec.end(), std::ostream_iterator<T>(cout, ", "));
      

5. In your deque type, don't forget to delete all elements in its destructor.

Answer 2

I have created a double-ended container, but I have doubts about its efficiency in terms of performance.

If you care about performance, then the use of virtual functions should be avoided. They add overhead to your code in three main ways:

• The derived class will have an implicit pointer to the base vtable, so you always get a small memory overhead per object;
• Calling a virtual method from a pointer to the base class is an indirect call that is likely to be an instruction cache miss;
• The compiler may not be able to inline a virtual function—and this is by far the worst pessimization introduced by virtual functions, since inlining is the basis of most other compiler optimizations.

I see very little gain in having the virtual base class in your case, so you should probably nuke it. All it serves is to give the (C++) code a very Java-ish look-and-feel, but little practical purpose.

The second thing to be aware of when it comes to performance is sparse memory allocations with operator new. The problem with linked data structures is that each node is allocated as a separate block of memory, which is likely to not be adjacent to any other block in the same structure, especially when a program is running multiple threads that allocate and free memory concurrently. You should consider a pooling strategy to group multiple elements in the same memory block. Ditching the linked structure altogether and using a plain std::vector might well prove to be more efficient when it comes to iteration and sequential accesses.

Answer 3

In c++ we have std::deque available, and it can be based on various base container types like std::vector or another default type.

You should note that std::list only supports forward iteration and therefore isn't an appropriate base for std::deque probably (see here also please).

Answer 4

Design

You need to split the members of your container from the container. There should be separate classes for each. Each item in the list does not need a head/tail. The list it-self does not need prev/next/value.

Your use of this-> is not standard practice in C++. It is also more error prone. Prefer not to use it and tell your compiler to not allow shadowed variables and you will get fewer errors.

Effeciency

Bad.

Each element in your list uses up much more space than is needed. Thus reducing memory efficiency.

Only storing one element per node is a very inefficient way of building a deque. The standard version places multiple value elements into each node.

Code Comments

Generic types are usually just T.

template <typename type_t>

One line per variable please.

    list<type_t> * head, * tail, * next, * prev;

Remember you are trying to write code that is readable. Putting this on one line makes it less readable in general.

Const correctness.

    ushort &size();

Methods that do not change the state of the class should be marked as const. That way the compiler has more information for debugging. Also if you must return a reference here then it should be a const reference as I would not expect you want the user to be able to change the size of the list via this value.

I would expect:

    ushort size() const;

Normally getters/setters break encapsulation. But since this is a container its less bad (but I think unnecessary). To prevent excessive copying though you should be passing values and return results by reference (type_t might be very expensive to copy).

    void setData(type_t);
    type_t getData();

The ordering of these methods is not very logical. Take some time to make the interface for your developer users easy to understand.

    virtual void push_back(type_t) = 0;
    virtual type_t pop_front() = 0;

    virtual void push_front(type_t) = 0;
    virtual type_t pop_back() = 0;

If I am printing something normally you would provide where you are printing it as an argument (some ouput stream maybe). You can always default it for the terminally lazzy user.

    virtual void print() = 0;

Also note that serialization (printing/streaming) is normally done with operator<< in C++.

Stop this one liner stuff. It just makes it hard to read.

list<type_t>::list() : size_(0){ this->head = this->tail = this->next = this->prev = nullptr;}

Also prefer initializer lists rather than doing it in the body. This will keep initialization consistent across all members.

Really no clean up in the constructor? I am sure I see a bunch of calls to new in the code when I ran it.

list<type_t>::~list() {}

You may want to look at move construction. It is at least as efficient as copy construction and can be considerably more efficient.

void list<type_t>::setData(type_t value){
    this->data = value;
}

New never returns a null value. So the subsequent test is not valid.

    list<type_t> * item = new dequeue;
    if (!item) throw std::bad_alloc();

    item->setData(value);

Declare local variables as close to the first point of use as possible (and initialize them at the same time.

    list<type_t> * item;

Your type_t better be default constructible. Otherwise this line will fail.

    type_t value;

This feels like it was already done in the constructor.

    item->prev = nullptr;