Hello
Pursuing my journey on Rust i tumble on a pickle.
I need to make insertion on a very large array at a spectif index (to keeps the array sorted).
In c i would have proceed as such
int64 array[612352];
int size; // representing how much the array is flled yet
// ...
// index is where we will, after shifting, add the new item
memmove(&array[index + 1], &array[index], (size - index * sizeof(array[0]));
Knowing that speed is important, how can i perform a similar operation in rust ?
Also, for an array that long you probably don't want to have it on the stack, and thus the better answer is probably https://doc.rust-lang.org/std/vec/struct.Vec.html#method.insert.
Thanks for the answer,
I've checked the doc but can't figure out how to use in my case ?
Somehing in the line of (keeping the same variable name as in the C example ?
array.copy_within(index.., index + 1);
The aim is an executable that will build a binary file, so the program won't live long (juste the generation time)
Since array/stack allow faster manipulation than Vec/heap, if i've understand correctly will it really be an issue?
It doesn't allow faster manipulation; once you have it it's just memory.
Stack is just cheaper to acquire and release -- and that makes a big difference for something like a short-lived [u8; 3]. But you have a 4 MiB array that's (presumably) long-lived. In comparison, the default stack size for a thread in Windows looks like it's 1 MiB. So saving one heap allocation for something that big is not at all worth it when you're massively increasing your chances of panicking for stack exhaustion.
(And, as a bonus, Vec has methods for exactly the "insert at this position" that you're trying to do.)
Thank you 
If you need to maintain a sorted order efficiently, you should consider using BTreeSet rather than Vec. BTreeSet is a much better data structure for this, it doesn't need to move everything in memory just to insert one element.
I think you only wanted to move index..size -- if you tried to move all index.. forward then the last entry would move out of bounds, which is a panic condition.
Didn't klnow about it thanks, but won'y be able to use it since I need acces to the indexes and it seems i can't do that with BTreeSet's.
With vector you are moving hundreds of thousands elements just to add one. That's extremely inefficient and allocation speed is not a problem compared to that.
Technically rope should be able to do what you want, but I'm not sure any implementations for Rust.
Learning a lot but i think Vec is the solution
I need both be able to retrieve indexes and to insert at a specific index (keep it sorted as i fill the array)
Keeping in mind that you mentioned the program is run infrequently and doesn't live long, and O(n²) over half a million elements just isn't that big a deal - around a minute worst case.
If you do find the input to it growing and speed becoming an issue, "roll a rope type" sounds about right. Even a single level "vec of vecs of 512-1024 elements, which are split down the middle on overflow and - if relevant - coalesced with half/all of an adjacent vec on underflow" should put tight bounds on number of bytes shifted on insert, and you can convert to/from usize abstract indices by summing over component vec lengths.
(Optionally maintaining a cumulative-sum array as you shift things, possibly in a weird shape like "for every index multiple of 1024 which vec does it end up in", depending on what the index-retrieving inner loop wants.)
This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.