[-]Array::reversed(), Array::shuffle()


#1

Both of those might be quite handy to have in Array...

I would find use for them anyway.

π

PS That could be a handy forum feature, up/downvoting on possible features to get a feeling for how much in demand they are.


#2

It feels a bit like you are using the wrong data structure. The array is a data block which is aligned each item after each other. So to shuffle the items they need to be actually moved. This gives a bad performance. If you use a deque instead (double linked list), to swap positions only the links are swapped.

And the reverse you get for free, because double linked means, that each element references the next AND the previous item. Simply use the other iterator, instead of begin() use rbegin() and instead end() use rend().

See: http://en.cppreference.com/w/cpp/container/deque

and: http://en.cppreference.com/w/cpp/algorithm/random_shuffle

HTH, daniel


#3

That's pretty old-fashioned advice, actually.. On modern CPUs their caches mean that a packed structure like Array/vector is going to be faster for all but the biggest arrays or for very expensive-to-move objects. A deque is very cache-unfriendly and is really only a good choice for situations where you have enormous objects or are constantly shuffling them around.

The standard advice you'll get from C++ performance gurus nowadays is simple: always start with a vector (or an Array, which is basically the same thing) and only change to a pointer-based data structure if you really do hit a genuine (and measurable) performance problem with it.

As for adding reverse/shuffle.. Hmm. Maybe. But TBH I've written a massive amount of code over the years and don't remember ever once needing either of those functions. Not sure why that is, but I think that although they seem like fundamental operations, they're probably not actually very commonly needed in the real world.

Also the modern C++ approach would be to use external algorithms for these, which should AFAIK work fine on an Array like they would on a std::vector.


#4

I agree completely, that cache coherency most times overrule the argument not to move elements around. So it really depends, what the OP wants to achieve. If he simply wants to e.g. randomize a playlist, no ptimization effort would pay off.

Choosing the best data structure probably connot be done when you know only one piece. So take my post as further reading and choose whatever you feel to fit best. It's a matter of trying and experience.


#5

Of course, they belong as free functions!

And I see std::reverse and std::shuffle in algorithm.h which should operate over Array.

π


#6

Just to clarify some wrong information further up: a double-linked list (std::list) is a very different structure from a deque (std::deque) for very different things with very different performance. 


#7

Sorry, I just realize that the terms I learned in my study (using Smalltalk beginning that century) don't fit exactly the names in STL.

I read it up seeing my error. I'd better stop commenting on anything related to STL...

Sorry again.