Queue.front() and Queue.back()

[MrEARTHSHAcKER]

Hi,

There is short explanation of queue at cplusplus.com site which tells that queue should contain front() and back() functions.
As I have tested in VC++, if I use queue from <queue> and call any of these functions for an empty queue, program crashes.

Could this problem be solved by simply adding a throw, in case when queue is actually empty, so front and back would throw an exception which'd be caught by try block?

( of course I am talking about queue, one would create, as I have done)

Here is my simple solution of this problem.

struct Exception{
const char* error;
Exception(const char* a):error(a){};
};

struct elem{
    int data;
    elem* next;
};

class queue{
    elem* head;
    elem* last;
    elem* current;
    int size;

public:
    queue();
    int& front();
    int& back();
    void pop();
    void push(int);
    int Size();
    bool empty();

};
bool queue::empty(){
if(head==NULL)
    return true;
return false;
}
queue::queue(){
head=0;
size=0;
}

void queue::push(int x){
    current=new elem;
    current->data=x;
    current->next=NULL;

    if(head==NULL){
        head=current;
        last=head;
    }
    else if(head!=NULL){
    last->next=current;
    last=current;
    }
}

void queue::pop(){
    if(head!=NULL){current=head;
    head=current->next;
    }
}

int& queue::front(){
    if(head!=NULL)  
    return head->data;
    else throw Exception("Queue is empty.");
}
int& queue::back(){
    if(last!=NULL)      
    return last->data;
    else throw Exception("Queue is empty.");
}

int queue::Size(){
size=0;
current=head;

while(current!=NULL){
size++;
current=current->next;
}

return size;

}

Do you have any critics about this solution, if you do, what is it, and what's your better solution?

Thanks.

[deceptikon]

As I have tested in VC++, if I use queue from <queue> and call any of these functions for an empty queue, program crashes.

If the queue is empty, what were you expecting a reference to by calling front() or back()? This is a case of undefined behavior, which is largely why the empty() member function exists.

Could this problem be solved by simply adding a throw, in case when queue is actually empty, so front and back would throw an exception which'd be caught by try block?

Assuming we're moving away from std::queue and into your own implementation of a queue, that would be an acceptable solution.

[mike_2000_17]

It's a trade-off between speed and safety. Generally, in many places, C++ standard libraries and their implementations put the emphasis on speed. This is why many STL container functions do not have bounds checking (or they have it only as an assert condition), although there are bound-checked alternatives like the at() function in the std::vector. A good programmer, like myself, is generally able to program in such a way that out-of-bound conditions (e.g., accessing an element beyond the length of an array, or calling front() / back() on an empty queue) happen extremely rare, almost never (except for the occasional typo). This means that I would get almost no benefit from bound-checking, but I would have to suffer a strong performance penalty for it. The C++ standard committee decided that this was unacceptable, so they required that there be no bound-checking on most of the container functions (but allowing bound-checks as assert() conditions). But they could have decided otherwise (e.g., in Java and .NET frameworks you do get bound-checking on everything, but you also pay a hefty price in performance for that extra safety, but that is the design choice in these frameworks, and it does have its merits too, because safety is important).

This means, of course, that if you want bound-checking, you have to implement it yourself (or I'm sure there are libraries out there that can "replace" the STL containers with safer versions). BTW, if you want to just add bound-checks to the standard queue implementation, why don't you just wrap it instead of writing your own queue implementation, you can do this:

template <typename T, typename Container = std::deque<T> >
class safe_queue {
  private:
    std::queue< T, Container> data;
  public:
    typedef std::queue< T, Container> queue_type;
    typedef typename queue_type::value_type value_type;
    typedef typename queue_type::reference reference;
    typedef typename queue_type::const_reference const_reference;
    typedef typename queue_type::pointer pointer;
    typedef typename queue_type::const_pointer const_pointer;
    typedef typename queue_type::size_type size_type;

    safe_queue(const Container& c = Container()) : data(c) { };

    bool empty() const { return data.empty(); };
    size_type size() const { return data.size(); };

    reference front() {
      if(!data.empty())
        return data.front();
      else
        throw std::out_of_range("The queue is empty! No front element!");
    };
    const_reference front() const {
      if(!data.empty())
        return data.front();
      else
        throw std::out_of_range("The queue is empty! No front element!"); 
    };
    reference back() {
      if(!data.empty())
        return data.back();
      else
        throw std::out_of_range("The queue is empty! No back element!");
    };
    const_reference back() const {
      if(!data.empty())
        return data.back();
      else
        throw std::out_of_range("The queue is empty! No back element!"); 
    };
    void push(const_reference value) { data.push(value); };
    void pop() {
      if(data.empty())
        throw std::out_of_range("The queue is empty! Cannot pop from it!");
      data.pop();
    };
};

[MrEARTHSHAcKER]

@deceptikon

If the queue is empty, what were you expecting a reference to by calling front() or back()? This is a case of undefined behavior, which is largely why the empty() member function exists.

I was just curious about does original <queue> own any checks for such cases.

@mike_2000_17
Thanks for great explanation!

why don't you just wrap it instead of writing your own queue implementation

I was learning how to create queue following cplusplus.com documentation, and the idea from my first post was just a result of my curiosity.