179

I went through this page but I am not able to get the reason for the same . There it is mentioned that

"it is more sensible for it to return no value at all and to require clients to use front() to inspect the value at the front of the queue"

But inspecting an element from front() also required that element to be copied in lvalue. For example in this code segment

std::queue<int> myqueue;
int myint;
int result;
std::cin >> myint;
myqueue.push (myint);
/* here temporary will be created on RHS which will be assigned to
   result, and in case if returns by reference then result will be
   rendered invalid after pop operation */
result = myqueue.front();  //result.
std::cout << ' ' << result;
myqueue.pop();

on fifth line cout object first creates a copy of myqueue.front() then assigns that to result. So, whats the difference, pop function could have done the same thing.

Improve this question
11
  • 1
    Because is implemented this way (i.e., void std::queue::pop();). Commented Jul 30, 2014 at 11:37
  • 1
    Your link is to the STL documentation. But you are asking about the C++ standard library. Different things. Commented Jul 30, 2014 at 11:55
  • 7
    "But inspecting an element from front() also required that element to be copied in lvalue" - no it doesn't. front returns a reference, not a value. You can inspect the value it refers to without copying it. Commented Jul 30, 2014 at 12:10
  • 1
    @KeminZhou the model you describe requires a copy. Maybe. If you want to multiplex consumption of the queue then yes, you must make a copy before releasing the lock on the queue. However, if you only care about separating input and output, then you don't need a lock to inspect the front. You could wait to lock until you are done consuming it and need to call pop(). If you use std::queue<T, std::list<T>> then there is no concern about the reference provided from front() being invalidated by a push(). But you must know your usage pattern and should document your constraints. Commented Sep 14, 2018 at 20:23
  • 4
    the real reason: compilers used to suck. we didn't have move semantics, noexcept & copy-elision. now we do, and besides all the nonsense you can read below, we could have an API that does this correctly and safely, but it's too late to change... Commented May 11, 2021 at 20:06

6 Answers 6

Reset to default
149

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

Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

C++11 note: if T has a cheap noexcept move-constructor (which is often the case for the kind of objects put in stacks) then returning by value is efficient and exception-safe.
@RomanL: If the suggestion is that the signature of the function should change depending on the type that is contianed in the stack... that would be surprising at the very least. I don't see a problem with the current implementation (for the single threaded case) and I see no point in complicating the specification and implementations.
@DavidRodríguez-dribeas: I'm not suggesting any changes, my point was that some of the mentioned drawbacks become less of an issue with C++11.
But why is it called pop? that is quite counter-intuitive. It could be named drop, and then it's clear for everyone that it doesn't pop the element, but drops it instead...
@utnapistim: the de-facto "pop" operation has always been to take the top element from a stack and return it. When I first came across STL stacks I was surprised, to say the least, about pop not returning anything. See for example on wikipedia.
|
53

The page you have linked to answers your question.

To quote the whole section relevant:

One might wonder why pop() returns void, instead of value_type. That is, why must one use front() and pop() to examine and remove the element at the front of the queue, instead of combining the two in a single member function? In fact, there is a good reason for this design. If pop() returned the front element, it would have to return by value rather than by reference: return by reference would create a dangling pointer. Return by value, however, is inefficient: it involves at least one redundant copy constructor call. Since it is impossible for pop() to return a value in such a way as to be both efficient and correct, it is more sensible for it to return no value at all and to require clients to use front() to inspect the value at the front of the queue.

C++ is designed with efficiency in mind, over the number of lines of code the programmer has to write.

Improve this answer

1 Comment

Perhaps, but the real reason is that it is impossible to implement an exception safe version (with the strong guarantee) for a version of pop which returns a value.
7

pop cannot return a reference to the value that is removed, as it is being removed from the data structure, so what should the reference refer to? It could return by value, but what if the result of pop is not stored anywhere? Then time is wasted copying the value unnecessarily.

Improve this answer

7 Comments

The real reason is exception safety. There is no safe way to have a "transaction" with the stack (either the element stays on the stack, or it's returned to you) if pop returns and the act of returning can result in an exception. It would obviously have to remove the element before it returns it, and then if something throws the element might be irrevocably lost.
Does this concern still apply with f.i. a noexcept move constructor? (Of course 0 copies are more efficient that two moves, but that could open the door for an exception safe, efficent combined front+pop)
@peppe, you could return by value if you know the value_type has a nothrow move constructor, but the queue interface would then be different depending on what type of object you store in it, which would not be helpful.
@peppe: That would be safe, but stack is a generic library class and therefore the more it has to assume about the element type the less useful it is.
I know the STL wouldn't allow for that, but that means one can build his own queue class with blackjack and ^W^W^W with this feature :)
|
6

Starting from C++11 it would possible to achieve desired behavior using move semantics. Like pop_and_move. So copy constructor will not be called, and performance will depend on move constructor only.

Improve this answer

3 Comments

No, move semantics does not magically make pop exception safe.
@L.F. It almost certainly does. It's really, really, really hard to imagine a reasonable class with a move-constructor that throws, Still, given that this is a template, committee could have designed a new function that is enabled conditionally. And finally put a stop to an awful, boilerplate and bug-prone path of making a two calls to do a one thing.
Agreed. And for the paranoid among us, we could enable it only when certain exception guarantees are met. You can always roll your own algorithm. Here's a free function that does what you probably want: template <typename T, typename Container> [[nodiscard]] std::optional<T> pop(std::queue<T, Container>& queue) noexcept(noexcept(std::optional<T>{std::move(std::declval<T&>())}) && std::is_nothrow_destructible_v<T>); godbolt.org/z/vhPx1YnjW
3

With the current implementation, this is valid:

int &result = myqueue.front();
std::cout << result;
myqueue.pop();

If pop would return a reference, like this:

value_type& pop();

Then the following code could crash, since the reference is not valid anymore:

int &result = myqueue.pop();
std::cout << result;

On the other hand, if it would return a value directly:

value_type pop();

Then you would need to do a copy for this code to work, which is less efficient:

int result = myqueue.pop();
std::cout << result;
Improve this answer

1 Comment

int result = myqueue.pop(); wouldn't work either if pop returns a reference. It would already be dangling by the time that result is initialized. If at all pop would return by-value (if it wasn't for exception-safety).
0

You can totally do this:

std::cout << ' ' << myqueue.front();

Or, if you want the value in a variable, use a reference:

const auto &result = myqueue.front();
if (result > whatever) do_whatever();
std::cout << ' ' << result;

Next to that: the wording 'more sensible' is a subjective form of 'we looked into usage patterns and found more need for a split'. (Rest assured: the C++ language is not evolving lightly...)

Improve this answer

Comments

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.