Expand `Vec<T>` and `StorageVec<T>` with additional utility methods

[mohammadfawaz]

An example of a good method to add would be contains(). There are probably plenty of other methods that we can add from https://doc.rust-lang.org/stable/std/vec/struct.Vec.html

[Braqzen]

1. Indexing and being able to assign to a specific index
2. Inserting at specified index
3. Removing at specified index
4. Pop from the end
5. Append vectors together
6. Split into two
7. Split at
8. First element of vec
9. Last element of vec
10. Swap two elements
11. Reverse the vector
12. Fill
13. Sorting by various keys, algorithms etc
14. Resize

[SwayStar123]

mutating an already existing value at given index is also a necessary function

[mohammadfawaz]

mutating an already existing value at given index is also a necessary function

See https://github.com/FuelLabs/sway/issues/2836

[mohammadfawaz]

We should also make sure that Vec and StorageVec are in sync in terms of what methods they support.

[jtriley-eth]

Writing some notes since this was partially completed prior to assignment.

Features Requested

Note: (✅ if complete)

1. ✅ Indexing and being able to assign to a specific index
2. ✅ Inserting at specified index
3. ✅ Removing at specified index
4. ✅ Pop from the end
5. Append vectors together
6. Split into two
7. Split at
8. First element of vec
9. Last element of vec
10. ✅ Swap two elements
11. Reverse the vector
12. Fill
13. Sorting by various keys, algorithms etc
14. Resize
15. ✅ Set
16. Contains
17. Sync StorageVec / Vec methods

Blockers

The contains method is blocked by issue #3333, resolved by PR 3621, merge pending at time of writing.

[jtriley-eth]

Following up on the sort method, it would be good to sort with multiple algorithms. However, in Rust, sort uses a "Timsort inspired" algorithm while sort_unstable uses a pattern defeating quicksort. The sort_by method allows a user-defined function to be used when sorting, but at the time of writing this is not possible in Sway. Should we simply use the sort and sort_unstable algorithm or should we extend the API to implement other sorting methods?

Assuming we implement multiple sorting methods, which of the following would be best? Neither has overlap with the Rust Vec API.

Option 1:

impl<T> Vec<T> {
    // in rust api
    fn sort(ref mut self) {}
    fn sort_unstable(ref mut self) {}

    // beyond rust api
    fn bubblesort(ref mut self) {}
    fn insertionsort(ref mut self) {}
}

Option 2:

enum SortingAlgorithm {
    Bubblesort,
    Insertionsort,
}

impl<T> Vec<T> {
    // in rust api
    fn sort(ref mut self) {}
    fn sort_unstable(ref mut self) {}

    // beyond rust api
    fn sort_with(ref mut self, algorithm: SortingAlgorithm {
        match algorithm {
            SortingAlgorithm::Bubblesort => {}
            SortingAlgorithm::Insertionsort => {}
        };
    }
 }

[mohammadfawaz]

Let start by following Rust for now - this may be all we need in the foreseeable future. (So sort and sort_unstable). Eventually we'll have the ability to pass closures to functions we'll be able to implement sort_by.

Oh and you can't use recursion yet so keep that in mind when implementing quick sort.

[jtriley-eth]

In the storage vector, what would be desirable behavior for split_off and split_at?

In the memory vector, split_off(&mut self, at: u64) -> Vec<T> creates a new memory vector starting at the at argument (inclusive) to return then resizes the original vector down to the at argument (exclusive). However, in the storage vector, returning a new storage vector does not seem possible. One possible way to do this is to create a new memory vector starting at the at argument to return then clear all storage vector elements from self.len - at to self.len - 1, but this seems clunky.

In the memory vector, split_at(&self, mid: u64) -> (Vec<T>, Vec<T>) does not mutate the original vector, but returning two storage vectors does not seem possible. As with the above, we could return memory vectors, but this still seems clunky.

Thoughts on the proposed implementations? We can also await the type conversion between StorageVec and Vec mentioned in #2439 (not a guaranteed change, but this could serve as motivation to push them), or we could simply not implement them and accept API differences between the memory and storage vectors.

[jtriley-eth]

Also, the append(&mut self, other: &mut Vec<T>) method, according to the Rust implementation, clears the other vector when it is appended to self.

This is marginal to implement in memory vectors despite differences in Sway's and Rust's memory models, but in storage vectors, this would require N reads, N writes, and N clears where N is the length of the other vector. Is this the behavior we want for the storage vector as well?

[mohammadfawaz]

I think for append it's okay to deviate a bit and avoid unnecessary clearing, especially in StorageVec.

If split_off and split_at seems difficult and expensive for StorageVec, we can consider skipping them honestly. It's also reasonable to implement #2439 before we attempt these, if that makes more sense.

[K1-R1]

Can this be closed now that the PRs in https://github.com/FuelLabs/sway/pull/3935#issuecomment-1442578506 have been merged?

[Braqzen]

Can this be closed now that the PRs in #3935 (comment) have been merged?

If all features are implemented then sure otherwise I would make a list of the ones that are not implemented and potentially create individual issues for them so that this can be closed.