SortedVec for Storage, maybe in a generic way

[kianenigma]

IMHO we have now reached the point where this should be abstracted. IMHO I don't see any point in copying this for every type in the std library (I know that we don't need every type). However this is mainly code copying. Which should be doable with some generic container or a macro that generates the stuff.

I don't have as strong opinion about BtreeMap and Set. On one hand they are types that we support in storage and we are a library, on the other hand we don't really use them (for good reasons) and we shouldn't overkill it. Either way I am happy with this PR.

About your comment on abstraction: I think what we do need is a next to our , because we have quite a few storage items that have the assumption that they must always be sorted. And implementation-wise I was thinking of something like this:

struct AttributeVec<T, Attr: Attribute>(Vec<T>);

/// An attribute to a container like a Vec
trait Attribute {
  fn pre_insert();
  fn post_insert();
  fn pre_delete(); 
  fn post_delete(); 
  // and some other hooks/utilities that allow an attribute to control how a container mutates.
}

/// An attribute that ensures a container's length never goes beyond a limit.
struct Bounded;
impl Attribute for Bounded {
  fn pre_insert() { /* ensure bound */}
}

/// An attribute that ensures a container is always sorted. 
struct Sorted;
impl Attribute for Sorted {
  fn post_insert() { /* do sort! */}
  fn post_delete() { /* do sort! */}
}

// and we can have other attributes, and attributes can be combined by aggregating them into a tuple. 
#[impl_trait_for_tuples(18)]
if Attribute for Tuple { /* ... */ }

/// 
type BoundedVec<T> = AttributeVec<T, Bounded>;
type SortedVec<T> = AttributeVec<T, Sorted>;
type BoundedSortedVec<T> = AttributeVec<T, (Bounded, Sorted)>;

But to be honest there are a lot of empty pieces in my brain dump above, and I am worried that this would add so much complexity that we would regret it and just go back to the simpler way of copy-pasta.

Originally posted by @kianenigma in #8750 (comment)

---

I am not sure if this idea is feasible at all yet, but I think the idea of a built-in sorted vec is worthwhile.

A much easier idea is to implement the sorted vec independently, or just use a trusted community crate, if any.

[stale]

Hey, is anyone still working on this? Due to the inactivity this issue has been automatically marked as stale. It will be closed if no further activity occurs. Thank you for your contributions.

[kianenigma]

I think this is too funky and an overkill of abstraction, I won't mind if someone closes it.

[kianenigma]

also looking at it again, the sorted vec implemented like this would likely have to sacrifice some performance.

[coriolinus]

It's a cool abstraction, particularly if we can implement it to get some fancy storage maps (i.e. no more custom CountedStorageMap, SortedStorageMap, etc; just get the right attributes on it). That said, I don't really see it happening soon.