Solved 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
-
@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. -
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
-
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
-
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 :)
-
@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; }
-
@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.