Suppose we have a situation where we need FIFO data structure. For example, consume some events in the order they came in.
Additionally, we need to clear the entire queue from time to time.
std::queue
seems like the perfect fit for doing that, but unfortunately it lacks a function for clearing the container.
So at this point, we have 2 alternatives:
std::queue
- we asked the STL lib what we need. Granted, the STL lib will give us more: it will give us an
std::deque
disguised as astd::queue
- we got back only a part from what we need, namely the pop front and push back but without clear
- we will have to "emulate" clear somehow, without the naive way of looping and popping
std::deque
- we asked the STL lib what we need
- we got back what we asked for, but we've got too much: we also got push front and pop back
Overall, we either received too few or too much, never exactly what we really wanted.
Here is the thing that took me by surprise, while I was trying to provide clear functionality for using with std::queue
which is a member var of my object
struct message
{
};
struct consumer
{
std::queue<message> _pending;
void clear_ver_1()
{
auto will_be_deleted_when_out_of_scope = std::move(_pending);
}
void clear_ver_2()
{
std::queue<message> will_be_deleted_when_out_of_scope;
_pending.swap(will_be_deleted_when_out_of_scope);
}
};
I've read the specs and I can not say for sure if clear_ver_1
will leave the _pending
in a valid but unspecified
state or not. See the
CodePudding user response:
The usage of std::move
std::move
isn't meant to be used that way. You should only use std::move
, well, to move an object to somewhere else in the program when you won't be using it anymore. As you said, it is then left in a valid but unspecified state:
- Valid because it is completely safe for destruction;
- Unspecified because you should not be accessing that object anymore.
std::queue
vs std::deque
If you only plan to use FIFO functionality, I would recommend using std::queue
. It really makes it clear that you will only use std::deque
as a FIFO data structure — clarity is kind of the only reason for std::queue
to exist in the first place.
Clearing a std::queue
You can just assign it to an empty std::queue
, or as you did it, swap it for for an empty one.
// ...
struct consumer
{
std::queue<message> _pending;
void clearQueue()
{
_pending = {};
}
};
Edited according to DevSolar's comment
CodePudding user response:
we got back what we asked for, but we've got too much: we also got push front and pop back
You got exactly what you asked for, a dequeue
is a data structure that allows efficient inserts and deletes at either end point. It might not be the data structure for you, but that's your fault for choosing it.
we will have to "emulate" clear somehow, without the naive way of looping and popping
For the record, popping is extremely cheap in terms of performance, it simply decrements a number. A pop in a while loop translates to decrementing an integer until 0, which unless you have a lot of numbers is very fast. In fact, it's probably much faster than allocating memory, which brings us to:
The STL way of clearing these collection classes is to swap them with an empty collection (which is what you figured out on your own) or to just straight up re-allocate them in place (apple's answer). Both of those will (probably, the standard is vague about this point) allocate memory, which is a very expensive linear operation.
You have all the pieces to do it, though I'd suggest profiling to see which way is faster if it really matters to you. Personally I just pop the queue in a loop, it leaves the allocated memory in place for the next time I need to push more, so it saves on potentially multiple allocations and re-allocations (when compared to resetting the queue), depending on the amount of data you have.
CodePudding user response:
To clear the queue, you can also simply write
_pending = {};
Note: the first method may not work and should not be rely on, since moved-form object are in valid but unspecified state.