Struct near_sdk::store::unordered_set::UnorderedSet

pub struct UnorderedSet<T, H = Sha256>
where
    T: BorshSerialize + Ord,
    H: ToKey,
{ /* private fields */ }

👎Deprecated since 5.0.0: Suboptimal iteration performance. See performance considerations doc for details.

A lazily loaded storage set that stores its content directly on the storage trie. This structure is similar to near_sdk::store::LookupSet, except that it keeps track of the elements so that UnorderedSet can be iterable among other things.

As with the LookupSet type, an UnorderedSet requires that the elements implement the BorshSerialize and Ord traits. This can frequently be achieved by using #[derive(BorshSerialize, Ord)]. Some functions also require elements to implement the BorshDeserialize trait.

This set stores the values under a hash of the set’s prefix and BorshSerialize of the element using the set’s ToKey implementation.

The default hash function for UnorderedSet is Sha256 which uses a syscall (or host function) built into the NEAR runtime to hash the element. To use a custom function, use with_hasher. Alternative builtin hash functions can be found at near_sdk::store::key.

Performance considerations

Note that this collection is optimized for fast removes at the expense of key management. If the amount of removes is significantly higher than the amount of inserts the iteration becomes more costly. See remove for details. If this is the use-case - see ’UnorderedSet`.

Examples

use near_sdk::store::UnorderedSet;

// Initializes a set, the generic types can be inferred to `UnorderedSet<String, Sha256>`
// The `b"a"` parameter is a prefix for the storage keys of this data structure.
let mut set = UnorderedSet::new(b"a");

set.insert("test".to_string());
assert!(set.contains("test"));
assert!(set.remove("test"));

UnorderedSet also implements various binary operations, which allow for iterating various combinations of two sets.

use near_sdk::store::UnorderedSet;
use std::collections::HashSet;

let mut set1 = UnorderedSet::new(b"m");
set1.insert(1);
set1.insert(2);
set1.insert(3);

let mut set2 = UnorderedSet::new(b"n");
set2.insert(2);
set2.insert(3);
set2.insert(4);

assert_eq!(
    set1.union(&set2).collect::<HashSet<_>>(),
    [1, 2, 3, 4].iter().collect()
);
assert_eq!(
    set1.intersection(&set2).collect::<HashSet<_>>(),
    [2, 3].iter().collect()
);
assert_eq!(
    set1.difference(&set2).collect::<HashSet<_>>(),
    [1].iter().collect()
);
assert_eq!(
    set1.symmetric_difference(&set2).collect::<HashSet<_>>(),
    [1, 4].iter().collect()
);

Implementations

impl<T> UnorderedSet<T, Sha256>

where T: BorshSerialize + Ord,

pub fn new<S>(prefix: S) -> Self

where S: IntoStorageKey,

Create a new iterable set. Use prefix as a unique prefix for keys.

This prefix can be anything that implements IntoStorageKey. The prefix is used when storing and looking up values in storage to ensure no collisions with other collections.

Examples

use near_sdk::store::UnorderedSet;

let mut map: UnorderedSet<String> = UnorderedSet::new(b"b");

impl<T, H> UnorderedSet<T, H>

where T: BorshSerialize + Ord, H: ToKey,

pub fn with_hasher<S>(prefix: S) -> Self

where S: IntoStorageKey,

Initialize a UnorderedSet with a custom hash function.

Example

use near_sdk::store::key::Keccak256;
use near_sdk::store::UnorderedSet;

let map = UnorderedSet::<String, Keccak256>::with_hasher(b"m");

pub fn len(&self) -> u32

Returns the number of elements in the set.

pub fn is_empty(&self) -> bool

Returns true if the set contains no elements.

pub fn clear(&mut self)

where T: BorshDeserialize + Clone,

Clears the set, removing all values.

pub fn difference<'a>( &'a self, other: &'a UnorderedSet<T, H> ) -> Difference<'a, T, H>

where T: BorshDeserialize,

Visits the values representing the difference, i.e., the values that are in self but not in other.

Examples

use near_sdk::store::UnorderedSet;

let mut set1 = UnorderedSet::new(b"m");
set1.insert("a".to_string());
set1.insert("b".to_string());
set1.insert("c".to_string());

let mut set2 = UnorderedSet::new(b"n");
set2.insert("b".to_string());
set2.insert("c".to_string());
set2.insert("d".to_string());

// Can be seen as `set1 - set2`.
for x in set1.difference(&set2) {
    println!("{}", x); // Prints "a"
}

pub fn symmetric_difference<'a>( &'a self, other: &'a UnorderedSet<T, H> ) -> SymmetricDifference<'a, T, H>

where T: BorshDeserialize + Clone,

Visits the values representing the symmetric difference, i.e., the values that are in self or in other but not in both.

Examples

use near_sdk::store::UnorderedSet;

let mut set1 = UnorderedSet::new(b"m");
set1.insert("a".to_string());
set1.insert("b".to_string());
set1.insert("c".to_string());

let mut set2 = UnorderedSet::new(b"n");
set2.insert("b".to_string());
set2.insert("c".to_string());
set2.insert("d".to_string());

// Prints "a", "d" in arbitrary order.
for x in set1.symmetric_difference(&set2) {
    println!("{}", x);
}

pub fn intersection<'a>( &'a self, other: &'a UnorderedSet<T, H> ) -> Intersection<'a, T, H>

where T: BorshDeserialize,

Visits the values representing the intersection, i.e., the values that are both in self and other.

Examples

use near_sdk::store::UnorderedSet;

let mut set1 = UnorderedSet::new(b"m");
set1.insert("a".to_string());
set1.insert("b".to_string());
set1.insert("c".to_string());

let mut set2 = UnorderedSet::new(b"n");
set2.insert("b".to_string());
set2.insert("c".to_string());
set2.insert("d".to_string());

// Prints "b", "c" in arbitrary order.
for x in set1.intersection(&set2) {
    println!("{}", x);
}

pub fn union<'a>(&'a self, other: &'a UnorderedSet<T, H>) -> Union<'a, T, H>

where T: BorshDeserialize + Clone,

Visits the values representing the union, i.e., all the values in self or other, without duplicates.

Examples

use near_sdk::store::UnorderedSet;

let mut set1 = UnorderedSet::new(b"m");
set1.insert("a".to_string());
set1.insert("b".to_string());
set1.insert("c".to_string());

let mut set2 = UnorderedSet::new(b"n");
set2.insert("b".to_string());
set2.insert("c".to_string());
set2.insert("d".to_string());

// Prints "a", "b", "c", "d" in arbitrary order.
for x in set1.union(&set2) {
    println!("{}", x);
}

pub fn is_disjoint(&self, other: &UnorderedSet<T, H>) -> bool

where T: BorshDeserialize + Clone,

Returns true if self has no elements in common with other. This is equivalent to checking for an empty intersection.

Examples

use near_sdk::store::UnorderedSet;

let mut set1 = UnorderedSet::new(b"m");
set1.insert("a".to_string());
set1.insert("b".to_string());
set1.insert("c".to_string());

let mut set2 = UnorderedSet::new(b"n");

assert_eq!(set1.is_disjoint(&set2), true);
set2.insert("d".to_string());
assert_eq!(set1.is_disjoint(&set2), true);
set2.insert("a".to_string());
assert_eq!(set1.is_disjoint(&set2), false);

pub fn is_subset(&self, other: &UnorderedSet<T, H>) -> bool

where T: BorshDeserialize + Clone,

Returns true if the set is a subset of another, i.e., other contains at least all the values in self.

Examples

use near_sdk::store::UnorderedSet;

let mut sup = UnorderedSet::new(b"m");
sup.insert("a".to_string());
sup.insert("b".to_string());
sup.insert("c".to_string());

let mut set = UnorderedSet::new(b"n");

assert_eq!(set.is_subset(&sup), true);
set.insert("b".to_string());
assert_eq!(set.is_subset(&sup), true);
set.insert("d".to_string());
assert_eq!(set.is_subset(&sup), false);

pub fn is_superset(&self, other: &UnorderedSet<T, H>) -> bool

where T: BorshDeserialize + Clone,

Returns true if the set is a superset of another, i.e., self contains at least all the values in other.

Examples

use near_sdk::store::UnorderedSet;

let mut sub = UnorderedSet::new(b"m");
sub.insert("a".to_string());
sub.insert("b".to_string());

let mut set = UnorderedSet::new(b"n");

assert_eq!(set.is_superset(&sub), false);
set.insert("b".to_string());
set.insert("d".to_string());
assert_eq!(set.is_superset(&sub), false);
set.insert("a".to_string());
assert_eq!(set.is_superset(&sub), true);

pub fn iter(&self) -> Iter<'_, T>

where T: BorshDeserialize,

An iterator visiting all elements in arbitrary order. The iterator element type is &'a T.

Examples

use near_sdk::store::UnorderedSet;

let mut set = UnorderedSet::new(b"m");
set.insert("a".to_string());
set.insert("b".to_string());
set.insert("c".to_string());

for val in set.iter() {
    println!("val: {}", val);
}

pub fn drain(&mut self) -> Drain<'_, T, H>

where T: BorshDeserialize,

Clears the set, returning all elements in an iterator.

Examples

use near_sdk::store::UnorderedSet;

let mut a = UnorderedSet::new(b"m");
a.insert(1);
a.insert(2);

for v in a.drain().take(1) {
    assert!(v == 1 || v == 2);
}

assert!(a.is_empty());

pub fn contains<Q>(&self, value: &Q) -> bool

where T: Borrow<Q>, Q: BorshSerialize + ToOwned<Owned = T> + Ord + ?Sized,

Returns true if the set contains the specified value.

The value may be any borrowed form of the set’s value type, but BorshSerialize, ToOwned<Owned = T> and Ord on the borrowed form must match those for the value type.

pub fn insert(&mut self, value: T) -> bool

where T: Clone + BorshDeserialize,

Adds a value to the set.

If the set did not have this value present, true is returned.

If the set did have this value present, false is returned.

pub fn remove<Q>(&mut self, value: &Q) -> bool

where T: Borrow<Q> + BorshDeserialize, Q: BorshSerialize + ToOwned<Owned = T> + Ord + ?Sized,

Removes a value from the set. Returns whether the value was present in the set.

The value may be any borrowed form of the set’s value type, but BorshSerialize, ToOwned<Owned = K> and Ord on the borrowed form must match those for the value type.

Performance

When elements are removed, the underlying vector of values isn’t rearranged; instead, the removed value is replaced with a placeholder value. These empty slots are reused on subsequent insert operations.

In cases where there are a lot of removals and not a lot of insertions, these leftover placeholders might make iteration more costly, driving higher gas costs. If you need to remedy this, take a look at defrag.

pub fn flush(&mut self)

Flushes the intermediate values of the map before this is called when the structure is Droped. This will write all modified values to storage but keep all cached values in memory.

impl<T, H> UnorderedSet<T, H>

where T: BorshSerialize + BorshDeserialize + Ord, H: ToKey,

pub fn defrag(&mut self)

Remove empty placeholders leftover from calling remove.

When elements are removed using remove, the underlying vector isn’t rearranged; instead, the removed element is replaced with a placeholder value. These empty slots are reused on subsequent insert operations.

In cases where there are a lot of removals and not a lot of insertions, these leftover placeholders might make iteration more costly, driving higher gas costs. This method is meant to remedy that by removing all empty slots from the underlying vector and compacting it.

Note that this might exceed the available gas amount depending on the amount of free slots, therefore has to be used with caution.

Examples

use near_sdk::store::UnorderedSet;

let mut set = UnorderedSet::new(b"b");

for i in 0..4 {
    set.insert(i);
}

set.remove(&1);
set.remove(&3);

set.defrag();

Trait Implementations

impl<T, H> BorshDeserialize for UnorderedSet<T, H>

where T: BorshSerialize + Ord, H: ToKey,

fn deserialize_reader<R: Read>(reader: &mut R) -> Result<Self, Error>

fn deserialize(buf: &mut &[u8]) -> Result<Self, Error>

Deserializes this instance from a given slice of bytes. Updates the buffer to point at the remaining bytes.

fn try_from_slice(v: &[u8]) -> Result<Self, Error>

Deserialize this instance from a slice of bytes.

fn try_from_reader<R>(reader: &mut R) -> Result<Self, Error>

where R: Read,

impl<T, H> BorshSerialize for UnorderedSet<T, H>

where T: BorshSerialize + Ord, H: ToKey,

fn serialize<W: Write>(&self, writer: &mut W) -> Result<(), Error>

impl<T, H> Debug for UnorderedSet<T, H>

where T: BorshSerialize + Ord + BorshDeserialize + Debug, H: ToKey,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T, H> Drop for UnorderedSet<T, H>

where T: BorshSerialize + Ord, H: ToKey,

fn drop(&mut self)

Executes the destructor for this type.

impl<T, H> Extend<T> for UnorderedSet<T, H>

where T: BorshSerialize + Ord + BorshDeserialize + Clone, H: ToKey,

fn extend<I>(&mut self, iter: I)

where I: IntoIterator<Item = T>,

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<'a, T, H> IntoIterator for &'a UnorderedSet<T, H>

where T: BorshSerialize + Ord + BorshDeserialize + Clone, H: ToKey,

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.