4 ms·

Ah, I was in a rust/c++ frame of mind here—it seems you deeply rely on a copy operation being available, but unless you use indirection and weak pointers it mig

by vladf 5y ago

Ah, I was in a rust/c++ frame of mind here—it seems you deeply rely on a copy operation being available, but unless you use indirection and weak pointers it might not be. I think with copy available this certainly works

Dylan16807 5y ago
I used copy mostly because the earlier post used it, but we can easily use moves instead. The access operator will just have to use some arithmetic to calculate which array an element is in. Moves also make it easier to have less memory overhead. If moves aren't available then a resizable array was doomed from the start.
- vladf 5y ago
  Hrm, is it really that easy? If you only have a placeholder in one of your arrays that points to the moved object in the other, then you need to do the actual move back if you have a sequence of pops/pushes which force you to delloc the moved-to array (say you have a grow sequence which gets you almost ready to make the 64 array the small one and then a series of pops back) Thought maybe in principle there’s yet another “amortization process“ which can be layered on top of what you already described that tries to keep the proportion of placeholders in both small and big arrays equal.
  - Dylan16807 5y ago
    You don't need placeholders. Can you explain why you're thinking about placeholders? For using move, the most straightforward way is: pushes and pops go directly to the big array. For every push you also move one element from small to big. For every pop you also move one element from big to small. This is slightly different from the algorithm above, but basically equivalent. Let's say you start with 32 elements in one array. If you grow into a bigger array, then by the time you add 32 more all your elements will be in the big array. If you shrink into a smaller array, then by the time you remove 16 all your elements will be in the small array. > (say you have a grow sequence which gets you almost ready to make the 64 array the small one and then a series of pops back) So let's say after the pushes we have 60/64 elements in the 64 array, almost full. There are also 2/32 in the smaller array. Then we do 10 pops. Now there are 40/64 in the bigger array, and 12/32 in the smaller array. Seems problem-free to me. If we keep doing pops we end up with 0/64 in the bigger array and 32/32 in the smaller array. At this point we could push again, or we could promote the 32 array to 'big' if we need to pop. When the arrays are size 32 and 64, the logic to access an element looks like this: n = total number of elements x = the key of element being accessed if ((x % 32) < (n - 32)) return big[x] else return small[x]

by vladf 5y ago

Dylan16807 5y ago

I used copy mostly because the earlier post used it, but we can easily use moves instead. The access operator will just have to use some arithmetic to calculate which array an element is in. Moves also make it easier to have less memory overhead. If moves aren't available then a resizable array was doomed from the start.

vladf 5y ago
Hrm, is it really that easy? If you only have a placeholder in one of your arrays that points to the moved object in the other, then you need to do the actual move back if you have a sequence of pops/pushes which force you to delloc the moved-to array (say you have a grow sequence which gets you almost ready to make the 64 array the small one and then a series of pops back) Thought maybe in principle there’s yet another “amortization process“ which can be layered on top of what you already described that tries to keep the proportion of placeholders in both small and big arrays equal.
- Dylan16807 5y ago
  You don't need placeholders. Can you explain why you're thinking about placeholders? For using move, the most straightforward way is: pushes and pops go directly to the big array. For every push you also move one element from small to big. For every pop you also move one element from big to small. This is slightly different from the algorithm above, but basically equivalent. Let's say you start with 32 elements in one array. If you grow into a bigger array, then by the time you add 32 more all your elements will be in the big array. If you shrink into a smaller array, then by the time you remove 16 all your elements will be in the small array. > (say you have a grow sequence which gets you almost ready to make the 64 array the small one and then a series of pops back) So let's say after the pushes we have 60/64 elements in the 64 array, almost full. There are also 2/32 in the smaller array. Then we do 10 pops. Now there are 40/64 in the bigger array, and 12/32 in the smaller array. Seems problem-free to me. If we keep doing pops we end up with 0/64 in the bigger array and 32/32 in the smaller array. At this point we could push again, or we could promote the 32 array to 'big' if we need to pop. When the arrays are size 32 and 64, the logic to access an element looks like this: n = total number of elements x = the key of element being accessed if ((x % 32) < (n - 32)) return big[x] else return small[x]