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



  • 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





  • 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


  • Qt Champions 2016



  • 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...



  • @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).



  • @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



  • @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.


  • Qt Champions 2016

    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.
    


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



  • @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?



  • @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.



  • @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



  • @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 :)


  • Qt Champions 2016

    @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.



  • @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;
    }
    

  • Qt Champions 2016

    @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.


Log in to reply
 

Looks like your connection to Qt Forum was lost, please wait while we try to reconnect.