IndexedMap

An IndexedMap (opens in a new tab) is a map that, apart from the usual map key K has some secondary indexes I that can be used to look up values.

💡

There's no limit to how many indexes you can have, but be careful. Using many indexes can increase the complexity of storage writes - with every write, the list of indexes is iterated over since they might need to be updated.

As always, we encourage you to explore the API reference (opens in a new tab) for a full list of available methods and more rigid definitions of the types involved.

Case study: User lookup

Imagine we have a list of users. Every user is uniquely identified by their address, so it makes sense to use that as the primary key. We'll need to look up users by their address - if Alice calls the contract, we should be able to look up her user data by the address with which she called.

💡

Every snippet on this page builds on the previous ones. Make sure you've understood the previous snippet before moving on to the next one, and feel free to go back and forth as needed.

This is easy to model with a normal Map.

use cw_storage_plus::Map;
 
type Handle = String;
 
#[cw_serde]
struct User {
    handle: Handle,
    country: String,
}
 
let _users = Map::<Addr, User>::new("u");

Great! But what if we want to look up users by their handles? Our only real option here is to iterate over all users and check if the handle matches. With a big enough user base, this could be slow and expensive.

Setting up an `IndexedMap` with a `UniqueIndex`

A better way would be to maintain a secondary index. Let's try to do this.

use cw_storage_plus::{index_list, IndexedMap, UniqueIndex};
 
use crate::users::*;
 
#[index_list(User)]
struct UserIndexes<'a> {
    handle_ix: UniqueIndex<'a, Handle, User, Addr>,
}
 
let user_indexes = UserIndexes {
    handle_ix: UniqueIndex::new(|user| user.handle.clone(), "uh"),
};
 
let _users = IndexedMap::<Addr, _, _>::new("u", user_indexes);

💡

The index_list macro is used to define a list of indexes for a given struct. This is a helper macro that generates an implementation of the IndexList (opens in a new tab) trait, with all the fields of the struct as indexes.

Here's what happens step-by-step

We define a struct UserIndexes that holds all the indexes we want to use. In this case, we only have one index - handle, indexing the handle field.
We construct our UserIndexes. Notice the UniqueIndex constructor takes two parameters:
- A function pointer (here we provide an anonymous function). This function is supposed to take the value of an entry and produce the secondary key. Without this, the IndexedMap would not know how to create the index.
- A prefix. The index needs its own storage namespace. Note the index prefix has to be distinct from the IndexedMap prefix (or any other prefix used with this contract's storage).
We construct an IndexedMap with that list of indexes.

💡

Note the UniqueIndex type has three type parameters. The order might be slightly confusing, but here it goes:

The secondary key type (Handle in our case).
The value type (User in our case).
The primary key type (Addr in our case).

⚠️

If you're using UniqueIndex (opens in a new tab), it's your responsibility to ensure that the index you've built has unique keys. If you have two users with the same handle, the index will be overwritten and only contain the last user. Be careful! If you need to store a key that is not unique, you'll want to use a MultiIndex (opens in a new tab) - see Lookup by country.

💡

Under the hood, the IndexedMap will store the data using a regular Map for the primary key, and then another Map for each secondary index. This is how efficient lookups are achieved.

Again, every update to this storage structure will have to update all the indexes - that's the price we pay for efficient lookups.

Taking advantage of the secondary index

As with a regular Map, you can load (opens in a new tab) data, save (opens in a new tab) data, remove (opens in a new tab) data, and iterate over the IndexedMap.

use cw_storage_plus::IndexedMap;
 
use crate::users::*;
 
let users = IndexedMap::<Addr, _, _>::new("u", user_indexes());
 
let alice_addr = Addr::unchecked("aaa");
let alice_user = User {
    handle: "alice".to_string(),
    country: "Wonderland".to_string(),
};
 
let bob_addr = Addr::unchecked("bbb");
let bob_user = User {
    handle: "bob".to_string(),
    country: "Bikini Bottom".to_string(),
};
 
users
    .save(&mut storage, alice_addr.clone(), &alice_user)
    .unwrap();
 
users
    .save(&mut storage, bob_addr.clone(), &bob_user)
    .unwrap();
 
assert_eq!(
    users.load(&storage, alice_addr.clone()).unwrap(),
    alice_user
);
 
assert_eq!(
    users
        .range(&storage, None, None, Order::Ascending)
        .collect::<StdResult<Vec<_>>>()
        .unwrap(),
    vec![
        (alice_addr.clone(), alice_user.clone()),
        (bob_addr.clone(), bob_user.clone()),
    ]
);

But now we can also look up users by their handle.

use cw_storage_plus::IndexedMap;
 
use crate::users::*;
 
let (_key, alice) = users
    .idx
    .handle_ix                           // access the `handle_ix` index
    .item(&storage, "alice".to_string()) // load a specific record
    .unwrap()
    .unwrap();
 
assert_eq!(
    alice,
    User {
        handle: "alice".to_string(),
        country: "Wonderland".to_string(),
    }
);

We can also iterate over records using bounds based on the secondary index. Here's how we can find all user handles starting with "a" or "b".

use cw_storage_plus::{Bound, IndexedMap};
 
use crate::users::*;
 
let found_users = users
    .idx
    .handle_ix
    .range(
        &storage,
        Some(Bound::inclusive("a")),
        Some(Bound::exclusive("c")),
        Order::Ascending,
    )
    .collect::<StdResult<Vec<_>>>()
    .unwrap();
 
assert_eq!(found_users.len(), 2);
assert_eq!(
    found_users[0],
    (
        Addr::unchecked("aaa"),
        User {
            handle: "alice".to_string(),
            country: "Wonderland".to_string(),
        }
    )
);
assert_eq!(found_users[1].1.handle, "bob");

⚠️

Note when iterating like this, the items yielded are of type (PK::Output, V), where PK is the primary key type of the IndexedMap and V is the value.

The PK::Output associated type is generally just the owned version of the PK type. For example, if PK is Addr, PK::Output will be Addr. If it's a String or a &str, PK::Output will be a String.

What's important and possibly surprising is we don't get back the secondary index. Because of that, it's sadly hard to implement anything like pagination with secondary key iteration.

If we're only interested in the addresses (primary keys in our case), we can use the keys method.

use cw_storage_plus::{Bound, IndexedMap};
 
use crate::users::*;
 
let found_keys = users
    .idx
    .handle_ix
    .keys(&storage, Some(Bound::inclusive("b")), None, Order::Ascending)
    .collect::<StdResult<Vec<_>>>()
    .unwrap();
 
assert_eq!(found_keys, [
    Addr::unchecked("bbb"),
    Addr::unchecked("ccc"),
    Addr::unchecked("ddd"),
]);

Lookup by country

Let's say we want to look up users by their country. This time, we'll use a MultiIndex instead of a UniqueIndex. This is because multiple users can be from the same country.

use cw_storage_plus::{index_list, IndexedMap, MultiIndex, UniqueIndex};
 
use crate::users::*;
 
#[index_list(User)]
struct UserIndexes<'a> {
    handle_ix: UniqueIndex<'a, Handle, User, Addr>,
    country_ix: MultiIndex<'a, String, User, Addr>,
}
 
let user_indexes = UserIndexes {
    handle_ix: UniqueIndex::new(|user| user.handle.clone(), "uh"),
    country_ix: MultiIndex::new(|_pk, user| user.country.clone(), "u", "uc"),
};
 
let _users = IndexedMap::<Addr, _, _>::new("u", user_indexes);

Note that the MultiIndex constructor (line 13) takes three parameters:

A closure that produces the secondary key. This is similar to the UniqueIndex constructor's first parameter.
A namespace for the map. This is supposed to be the same value as the prefix used for the IndexedMap.
A prefix for the index. This is supposed to be distinct from the prefix used for the IndexedMap, and is similar to the UniqueIndex constructor's second parameter.

Let's take advantage of the new index. We'll find all users from the USA. The call chain is a bit different here, so hang on tight.

use cw_storage_plus::{Bound, IndexedMap};
 
use crate::users::*;
 
let us_users = users
    .idx
    .country_ix
    .prefix("USA".to_string())
    .range(&storage, None, None, Order::Ascending)
    .collect::<StdResult<Vec<_>>>()
    .unwrap();
 
assert_eq!(us_users, [
    (
        Addr::unchecked("bbb"),
        User {
            handle: "bob".to_string(),
            country: "USA".to_string(),
        }
    ),
    (
        Addr::unchecked("ddd"),
        User {
            handle: "dave".to_string(),
            country: "USA".to_string(),
        }
    ),
]);

Due to technical limitations, the MultiIndex does not support bounded iteration over the secondary key for dynamically sized types (like Addr or String). For example, this means we can't find out all the entries for countries starting with "U". If your secondary index is something with a fixed size (like u32 or [u8; 32]), bounds should work just fine.

💡

The technical reason for this is that the MultiIndex is implemented as a Map<(IK, PK), _> under the hood, where IK is the secondary key and PK is the primary key. This means it's subject to the same limitations as compound keys in general.

If you're interested in iterating over all the entries in a MultiIndex, you can use the range method without bounds. As before, there's also the keys (opens in a new tab) method for when values don't matter to you.

Deque SnapshotItem

IndexedMap

Case study: User lookup

Setting up an IndexedMap with a UniqueIndex

Taking advantage of the secondary index

Lookup by country

Setting up an `IndexedMap` with a `UniqueIndex`