is there a stack with fixed capacity, dropping old elements when we reach it?

mbruel

Hi,
I'd like to use a stack with fixed capacity and when I reach the capacity drop the old elements and continue to to add the new ones on the top.
Is there such object to do that?
I've seen there is QCircularBuffer that could do the job but it is 3dcore...
do I need to implement it myself or is there an already made solution?
Cheers

VRonin

http://doc.qt.io/qt-5/qcache.html

mbruel

well QCache is interesting but I really would like a stack with a push pop functionality...
so using a key indexed base structure is maybe not the best way to go

mrjj

@mbruel
http://doc.qt.io/qt-5/qstack.html#details
Might be candidate?

Update:
sorry, its not fixed.
Nor is
http://en.cppreference.com/w/cpp/container/queue

mbruel

In fact, I'm going to go for easy way, just use a QStack and in my function that pushes, I'll do manually a pop if I exceed my desired fixed capacity. It sounds faster than implementing a circular buffer...

peteritv

@mbruel
A circular buffer is nothing more than a linked list with it's tail tied to it's head.
So you could subclass QLinkedList, and override the end() methods.

You can also create a FIFO (first in first out) or LIFO (last in first out == stack) from a fixed array...

Circular buffers are normally used in "asynchronous communication" applications, where the sender and the receiver are out of sync, sometimes the sender is faster, sometimes the receiver is faster, but in the end they will catch up...

FIFO and LIFO have their own specialties, so it kinda depends on ur application wich is the most sensible...

In your case I guess the subclassed QLinkedList makes most sense, because it already has pop and push (and much more).

VRonin

@mbruel said in is there a stack with fixed capacity, dropping old elements when we reach it?:

drop the old elements

I'll do manually a pop

a manual pop from a stack would delete the new element, not the old one, a manual take on QVector is probably better for you

mbruel

@VRonin said in is there a stack with fixed capacity, dropping old elements when we reach it?:

@mbruel said in is there a stack with fixed capacity, dropping old elements when we reach it?:

drop the old elements

I'll do manually a pop

a manual pop from a stack would delete the new element, not the old one, a manual take on QVector is probably better for you

wow yeah true...
I may implement a circular buffer with a fixed sized array and 2 pointers to mark the start and the last slots but for now, as peteritv suggested, I'll just use a QLinkedList where I can push_front, pop_front and when my capacity is reached use removeLast.

kshegunov

What is there to implement for a circular buffer? Any vector will do, you just renormalize the index, e.g.:

QVector<qreal> data; // The data buffer
qint32 i;            // Some index we use to access the element

// Be sure you aren't going out of bounds, and voila the index is circular all of a sudden
i %= data.size();

// This last operation greatly benefits if the vector is the size of a power of 2
// because it reduces to a (very) simple bitwise AND.

VRonin

Why implementing it yourself when it's there already?! http://www.boost.org/doc/libs/1_62_0/doc/html/circular_buffer.html

mbruel

@kshegunov

hum... I'm not sure this would work and I find it more complicated than just having a fixed size array and 2 pointers for the start and the end of the stack so basically a circular buffer.

With your example, I guess the index is the next slot available where we would push an Item. If we go over the limit, then we start again from the start, ok but now if we want to pop all the Items, we need to remember where to stop after arriving to the start and starting back from the end. Do you see what I mean?

When I pop from position Index, I want to get buffer[Index-1] .. buffer[0] then buffer[buffer.size()] ... buffer[Index+1]. How do I remember Index if I only use one pointer?

mbruel

@VRonin
Well I don' want to link an external library for something simple that I can just implement quite rapidly...
I had to do it for a job interview last January but not in a stack mode and I think it would be even easier as the push is never an issue.

VRonin

@mbruel said in is there a stack with fixed capacity, dropping old elements when we reach it?:

Well I don' want to link an external library

99% of Boost is header only, no link and this includes circular_buffer

On top of that Boost is probably the closest thing to the standard you can find, and in a job interview I'd value an answer that takes 6 seconds to implement and has no effective restriction on the final product licensing. If you don't know Boost and you are looking for a C++ programmer job that's an handicap in itself.

I'm part of the team that to the usual "how can you count the number of set bits in an unsigned int32?" considers std::bitset as the only acceptable answer

mbruel

@VRonin

I've to admit I've never had a look at boost yet and it is also pretty recent I started to check and use the STL... and now QT! :)

Sure it is useful but it depends on your field of application and the resources you can have.

For that basic question of the number of bit set, thanks to you I'll now talk about std::bitset but I would rather consider a more C implementation shifting the number :)

kshegunov

@mbruel said in is there a stack with fixed capacity, dropping old elements when we reach it?:

hum... I'm not sure this would work and I find it more complicated than just having a fixed size array and 2 pointers for the start and the end of the stack so basically a circular buffer.

Absolutely! Doing pointer arithmetic is very much simpler and faster!
Here's what a stack is:

qint32 top = 0, maxSize = 20;
QVector<qreal> stack(maxSize);

// Push to the stack
stack[top] = 567; //< Inserts at the top of the stack
top = ++top % maxSize;

// Pop from the stack
qreal elementAtTop = stack[top];
top = (--top + maxSize) % maxSize; // No branching without an if

@VRonin said in is there a stack with fixed capacity, dropping old elements when we reach it?:

On top of that Boost is probably the closest thing to the standard you can find

In all probability because the boost bunch sits on the standards committee as well ... and on more than one occasion I've made my opinion of it known.

in a job interview I'd value an answer that takes 6 seconds to implement and has no effective restriction on the final product licensing. If you don't know Boost and you are looking for a C++ programmer job that's an handicap in itself.

Non omne quod nitet aurum est (not all that glitters is gold).
Thankfully for the lazymen like me, programming isn't just knowing a bunch of classes. And by the way the "header only" policy of boost makes the binaries swell beyond epic proportions ... just saying.

I'm part of the team that to the usual "how can you count the number of set bits in an unsigned int32?" considers std::bitset as the only acceptable answer

I'd use __builtin_popcount[1] or __popcnt[2], but you know me, I'm old-fashioned to a fault.

VRonin

@kshegunov Sorry for going OT, I'll censor myself, this is the last post, I promise.

Yes the boost people are on the standard board but not every idiot can get to that board so I wouldn't discount them so fast.
My backgound is economics and between bigger exe (and slower compilation) but requiring just an #include and spending time writing a whole class and having to maintain its code for the opposite advantages I take the first every day
I was referring to the byteshift solutions or the math genius version below. your compiler specific work more than fine for me, bitset was just the generic version

int NumberOfSetBits(int i)
{
     i = i - ((i >> 1) & 0x55555555);
     i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
     return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

kshegunov

@VRonin said in is there a stack with fixed capacity, dropping old elements when we reach it?:

Sorry for going OT

I don't mind. And I think there's plenty up to now to consider the question answered anyway, so a bit of arguing won't hurt anyone.

not every idiot can get to that board so I wouldn't discount them so fast

Of course not, you have to be a very special one ... ;)
Joke aside, they're most certainly not idiots, only misguided. :)

My backgound is economics and between bigger exe (and slower compilation) but requiring just an #include and spending time writing a whole class and having to maintain its code for the opposite advantages I take the first every day

Well that's the thing, sometimes bigger is slower. When I run something on the cluster I don't want the loader to take forever. I'm not saying boost is bad, it's fine (most of it anyway) but it ain't only sunshine and roses.

I was referring to the byteshift solutions or the math genius version below. your compiler specific work more than fine for me, bitset was just the generic version

I'd just use a byte lookup table (256 bytes of size) and sum it all up. The complexity then goes to O(m) where m is the number of bytes for the datatype, i. e. 4 for a regular 32 bit int. There's a general algorithm for counting bits but I'd say a small trade of CPU time for a bit more memory is just as regular solution. The code you posted I haven't seen, but it does look cryptic.