Why Doesn't Std::Queue::Pop Return Value.

Why doesn't std::queue::pop return value.?

So, whats the difference, pop function could have done the same thing.

It could indeed have done the same thing. The reason it didn't, is because a pop that returned the popped element is unsafe in the presence of exceptions (having to return by value and thus creating a copy).

Consider this scenario (with a naive/made up pop implementation, to ilustrate my point):

template<class T>
class queue {
    T* elements;
    std::size_t top_position;
    // stuff here
    T pop()
    {
        auto x = elements[top_position];
        // TODO: call destructor for elements[top_position] here
        --top_position;  // alter queue state here
        return x;        // calls T(const T&) which may throw
    }

If the copy constructor of T throws on return, you have already altered the state of the queue (top_position in my naive implementation) and the element is removed from the queue (and not returned). For all intents and purposes (no matter how you catch the exception in client code) the element at the top of the queue is lost.

This implementation is also inefficient in the case when you do not need the popped value (i.e. it creates a copy of the element that nobody will use).

This can be implemented safely and efficiently, with two separate operations (void pop and const T& front()).

Why does the value returned from front() exist even after pop() from std::queue?

Because val is not a reference. Not to the front of the queue or anywhere else.

When you do

val = q.front();

you copy what's currently at the front of the queue into val.

What you do later with the queue will not affect this copy.

If you want a reference then you need to make val a reference.

And remember that by making val a reference, it will only reference one single element in the queue. Once you pop the front once, that reference becomes invalid. Adding new elements will not change your reference, it will still reference the same element in the queue, it will not reference the new front. And you can not rebind a reference once bound.

All in all, using references to elements in a queue is in most use-cases pretty useless.

Can queue::pop return a value now?

Using clever SFINAE techniques it would indeed be possible to have an atomic non-throwing pop_and_move() for just datatypes that implement no-throwing move or no-throwing copy.

There is even a noexcept() construct available to see if something might throw.

One of the new concepts in C++11 in particular that extends SFINAE is that if the body doesn't compile the function doesn't exist. Thus one could implement based on noexcept().

I would say for backward compatibility the function would need a new name, which therefore allows it to co-exist with the existing functionality of calling them separately, not breaking containers of types that do not have the semantics to allow it.

Why is return value of queue:front() valid after queue::pop()

Trying to access a destroyed object the way you do it in your code results in undefined behavior. And no, there's no language-provided way to perform a run-time check for this situation. It is entirely your responsibility to make sure things like that do not happen in your code.

The fact that "it just works" in your experiment is just an accident (with certain degree of typical computer determinism, as usual). Something completely unrelated might change in your program, and this code will no longer "work".

Why does top()'s return value change after calling pop()?

If get top value by auto & m = queue.top();, then output is also 3 2 1.

Despite it is calling undefined behavior to use m after the 1st pop() call, it is likely that the next value is moved to that dangling reference (address). That is because the default underlying type of std::priority_queue is std::vector, which guarantees a contiguous array of elements.

But as mentioned that behavior is undefined, and there are no guarantees to reproduce that result with a different compiler.

While if get top value by auto m = queue.top();, then output is 3 3 3.

The value from top is stored into m once, and never changed afterwards.

Why doesn't std::queue shrink its memory after popping elements?

Basically std::queue is an Adapter Container - it is not a container by its own, but a thin wrapper around other container.

For example, lets take a look at the queue signature:

template <class T, class Container = deque<T> > class queue;

as you can see, T is the type of the element stored in the queue, and Container is the underlying container.

and this is the answer to your question: different containers handles memory differently. the underlying deque may or may not shrink, but it is up to the deque inside to decide.

you can use std::list as your underlying container as well. in this case, each pop deletes the underlying list node memory.

you can also write your own or modify existing container to match your own memory-management patterns. your container needs to support some methods (such as push_back, pop_front) which you can read in the relevant online documentation.

Here is an example to a deque adapter which shrinks in capacity every 1024 pop calls:

template<class T>
class DequeAdapter{
    
private:
    std::deque<T> m_Deque;
    size_t m_PopCount;

public:
    DequeAdapter():
        m_PopCount(0){}
    
    bool empty() const noexcept{
        return m_Deque.empty();
    }
    
    size_t size() const noexcept{
        return m_Deque.size();
    }
    
    T& front() noexcept{
        return m_Deque.front();
    }
    
    const T& front()const noexcept{
        return m_Deque.front();
    }
    
    T& back() noexcept{
        return m_Deque.back();
    }
    
    const T& back()const noexcept{
        return m_Deque.back();
    }
    
    void push_back(const T& t){
        return m_Deque.push_back(t);
    }
    
    void push_back(T&& t){
        return m_Deque.push_back(std::move(t));
    }
    
    void pop_front(){
        m_Deque.pop_front();
        m_PopCount++;
        if (m_PopCount%1024U == 0U){
            m_Deque.shrink_to_fit();
        }
    }

}


template <class T>
using LeanQueue = std::queue<T,DequeAdapter<T>>;

Do note however, that shrinking in capacity means moving or copying the queue elements to the new lean chunk, the memory consumption will be smaller, but the performance may degrade.

---

Related Topics