7
\$\begingroup\$

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_ */
\$\endgroup\$
6
  • 1
    \$\begingroup\$ You should note that there's already a std::list container available. You should make your list class appear in its own namespace probably. \$\endgroup\$ Jan 2, 2017 at 19:05
  • \$\begingroup\$ Except namespace, is there another point for the code? \$\endgroup\$ Jan 2, 2017 at 19:27
  • 1
    \$\begingroup\$ Well, do you wan't to reinvent the wheel? What's the reasoning not simply to use std::deque? \$\endgroup\$ Jan 2, 2017 at 19:30
  • \$\begingroup\$ @jamal Is it really off-topic to ask for advice on how to modify the code to use STL algorithms? I see that you edited that out, but it seems like a reasonable code-review criterion to me. Maybe it was just overzealous editing when removing the off-topic "How can i create my own iterators?" question? \$\endgroup\$ Jan 3, 2017 at 6:25
  • \$\begingroup\$ Have you tried iterating a const reference? \$\endgroup\$ Jan 3, 2017 at 11:04

4 Answers 4

8
\$\begingroup\$
  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.

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ The actual overhead of virtual function calls is often overstated, but it is something to keep in mind, and I agree that in this case, it seems completely unnecessary. Clarity and simplicity are equally valid arguments for removing the virtual-ness as performance is. \$\endgroup\$ Jan 3, 2017 at 6:33
3
\$\begingroup\$

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).

\$\endgroup\$
3
\$\begingroup\$

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;
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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